source: liacs/ai/bridge/report.tex@ 144

%
% $Id: report.tex 525 2008-03-18 15:38:34Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}

\author{Rick van der Zwet, Universiteit Leiden}
\title{Kunstmatige Intelligentie  2008 --- opdracht 1 \\
\large{simpleBridge}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}\\
  \\
  LIACS\\
  Leiden University\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}

\begin{document}

\maketitle

\section{Inleiding}

Dit verslag gaat over de eerste programmeer-opgave van het vak
kunstmatige intelligentie\cite{bridge-opdracht}. Welke als opdracht heeft het kaartspel
\emph{simpleBridge} te onderzoeken. Tijdens dit onderzoek zal
uitgezocht worden of met simpele regels te voorspellen is wat de uitslag
wordt van een spelletje \emph{simpleBridge}.
Als tweede wordt gekeken of het mogelijk is om met behulp van een aantal
simpele regels een zeer eenvoudige reflex-agent te construeren die
winnend speelt tegenover zijn willekeurige tegenhangers.

\section{Uitleg probleem}

\emph{simpleBridge} is zeer versimpelde versie bridge\footnote{Kijk voor
de volledige spelregels van bridge op Bridge pagina van Wikipedia\cite{bridge-wiki}}
met 4 spelers die in 2 teams tegen elkaar spelen.
\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=1]{speelbord}
\end{center}
\caption{
Voor de duidelijkheid zijn in het verslag heten de spelers
Noord, Oost, Zuid en West. En speelt Noord samen met Zuid in team
\emph{NZ} en bevat team \emph{OW} de spelers Oost en West.
}
\end{figure}
Er wordt gespeeld met een normaal kaartspel, dit bestaat uit 52 unieke
kaarten, welke een kleur hebben (Schoppen, Harten, Klaveren, Ruiten) en
een van de 13 unieke oplopende waardes. Er zijn van elke kleur dus 13
uniek oplopende kaarten in het spel. \cite{kaartspel-wiki}

Elke speler krijgt willekeurig 13 kaarten toegewezen en heeft geen zicht
op de kaarten van de andere spelers, nu wordt er willekeurig een team
toegewezen die de \emph{troefkleur} mag kiezen en het aantal slagen dat
ze denken te gaan halen, dit wordt het \emph{contract} genoemd. Tijdens
deze keuze hebben ze zicht op alle kaarten van het team, maar niet op de
kaarten van het andere team. Na het maken van het contract wordt er
afgespeeld, hierbij is voor elke speler niet meer bekend wat de andere
spelers voor kaarten in handen hebben.

Het \emph{afspelen} gaat als volgt:

Er wordt willekeurig een speler gekozen die een kaart naar keuze
opgegooid. De rest van de spelers gooien om de beurt (met de klok mee) een
kaart mee, welke van dezelfde kleur is als de eerste kaart die
opgegooid is. Als deze niet in bezit is volstaat een het willekeurige
andere kaart.

Nadat alle vier de spelers een kaart hebben gespeeld wordt er gekeken
welke kaart de winnaar is. De hoogst gespeelde troef wint en als deze
niet present zijn dan is de hoogste kaart van de kleur die als eerste
kaart gespeeld is de winnaar en heeft het team van de speler die deze
kaart gespeeld heeft een \emph{slag}

De speler van de winnende kaart is nu aan de beurt en mag een kaart
naar keuze opgooien en wordt het spel weer hetzelfde afgespeeld als
hierboven. Dit gaat door tot alle kaarten gespeeld zijn en er dus 13
slagen verdeeld zijn tussen de 2 teams.

Het aantal verwachte slagen (het contract) wordt nu vergeleken met het
aantal daadwerkelijk gehaalde slagen. Als deze gelijk zijn levert dit 20
punten op, elk slag te weinig kost 20 punten en elk slag teveel kost 10
punten.

Het meeste aantal punten zijn dus te halen door het beste te bieden en
daarop het slimste te spelen. Als extra randvoorwaarde zal er geprobeerd
worden zoveel mogelijk slagen te halen, dit komt echter niet terug in de
punten aantallen.

\section{Theorie}

Als het kiezen van het bod en het afspelen volledig willekeurig gebeurt zal
het contract zelden behaald worden door de grote hoeveelheid kaart
mogelijkheden. 

Tijdens de keuze van het contract word gebruik gemaakt van de informatie
die beschikbaar is en van de regels die gesteld zijn.  Er wordt niet in
het het `geheim' het spel afgespeeld om ervoor te zorgen dat een goed
contract gemaakt wordt. Aan ditzelfde gedrag voordoet de kaartspeel
agent. Dit gedrag is ook te zien bij een simpele reflex agent (zie
Figuur~\ref{fig:agent}, bron figuur
Wikipedia~\footnote{\url{http://en.wikipedia.org/wiki/Image:IntelligentAgent-SimpleReflex.png}}).


\begin{figure}[!ht]
\begin{center}
\includegraphics[height=60mm]{simple-agent.eps}
\end{center}
\caption{
De simpele reflex agenten kan je vergelijken met een simpele actie en
reactie mechanisme als het menselijke instinct. Zonder dat er bij
nagedacht wordt over het doel/nut wordt er overgegaan tot actie na
invoer van de buitenwereld}
\label{fig:agent}
\end{figure}

\section{Aanpak}
Voor zowel de contract agent en de afspeel agent zijn simpele regels
verzonnen die respectievelijk het bieden of het afspelen proberen te
voorspellen.

\subsection{Contract agent}
Troef levert de meeste slagen op, dus de kleur waar de meeste kaarten
van beschikbaar zijn wordt troef en levert een slag op. Als volgende
zijn de hoogste kaarten aan de beurt. Eerst wordt er bijvoorbeeld
gekeken of de aas present is, dan de heer, enzovoort. Dit wordt
gekeken per bepaalde kleur. Alle aansluitende hoge kaarten leveren ook
een slag op.

\subsection{Afspeel agent}
De tactiek wordt om zo snel mogelijk de hoge kaarten uit het spel te
krijgen. Dit wordt tewerkstelligd door op moment dat de speler uit mag
komen de hoogste kaart uit zijn kaarten te spelen, bij gelijke waarden
heeft een troef de voorkeur. Als er bijgespeeld moet worden (dus niet als
eerste aan de beurt) dan de hoogste kaart van de kleur meespelen, of de
laagste (troef)kaart bij het niet in handen hebben van de meespeel kleur.

\section{Implementatie}

Er is gekozen om als basis het aangeboden skelet
programma\cite{bridge-skelet} te gebruiken welke in de programmeertaal
C$\stackrel{++}{}$ versie 4.0.1 geschreven is.
De structuur/werking van de code is niet veranderd, maar de opzet van
bijvoorbeeld de uitvoer code wel.

\section{Experimenten}
Om de experimenten zo eerlijk mogelijk te laten verlopen is ervoor
gekozen om de randvoorwaarden gelijk te houden. Onder de randvoorwaarden
valt het aantal kaarten dat zichtbaar is tijdens contract keuze en het
niet kunnen zijn van de kaarten op tafel. Verder zijn de opstellingen
10000 keer gespeeld om uitersten te elimineren. De opstellingen speelden
met dezelfde random begin seed om zo de kaarten die gegeven worden
hetzelfde te laten zijn.

Elke opstelling is in de code ingevoerd en daarna is de code opnieuw
gecompileerd en uitgevoerd. Tijdelijke (object) bestanden zijn
tussentijds weggegooid.

De resultaten van de experimenten zijn te vinden in
Tabel~\ref{tab:resultaten}.
\begin{center}
\begin{table}[h]
\caption{Opstelling is gecodeerd als Noord,Oost,Zuid,West welke Random
of Slim zijn. De contract agent is Random of Slim. Tekort, Correct en
Teveel en Score zijn de uitkomsten na 10000 spel rondes, met random seed
getal 1203969568. Hoe hoger de Score hoe beter}
\begin{tabular}{l|l|l|l|l|l}
Opstelling  & Contract agent & Tekort & Correct & Teveel & Score\\
\hline
$R,R,R,R$ & $R$ & $5020$ & $793 $ & $4187$ & $-545350$ \\
$S,R,R,R$ & $R$ & $5072$ & $741 $ & $4187$ & $-554260$ \\
$S,R,S,R$ & $R$ & $5020$ & $770 $ & $4210$ & $-551230$ \\
$S,S,S,S$ & $R$ & $5039$ & $756 $ & $4205$ & $-567600$ \\
$R,R,R,R$ & $S$ & $6075$ & $1751$ & $2174$ & $-297840$ \\
$S,R,R,R$ & $S$ & $6127$ & $1686$ & $2187$ & $-307010$ \\
$S,R,S,R$ & $S$ & $6031$ & $1651$ & $2318$ & $-319270$ \\
$S,S,S,S$ & $S$ & $5889$ & $1497$ & $2614$ & $-339580$
\end{tabular}
\label{tab:resultaten}
\end{table}
\end{center}

\section{Conclusie}
De score is enkel afhankelijk van het type contract agent gebruikt. De
random agent levert een score van $-56760$ t/m $-545350$, de random
afspeel agent een betere score dan de slimme agent. De slimme agent
levert een score van $-339580$ t/m $-297840$ en ook hier geld weer hoe
de random afspeel agent een betere score dan de slimme agent.

Nader onderzoek aan de code wijst uit dat er twee factoren aangewezen
kunnen worden die dit gedrag kunnen verklaren. Tijdens het maken van het
contract wordt het paar volledig random gekozen en hiervan wordt de
score bepaald. Het kan dus zijn dat tijdens de combinatie $S,R,S,R$
waarbij de $NZ$ dus slim spelen een contract keuze $R$ toegewezen
krijgen. Deze mogelijkheid is onderzocht door het slimme contract altijd
voor paar $NZ$ te laten gelden en leverde de waardes op $6215,
1549, 2236, -342270$. De score is zelfs nog slechter.

Of de slimme speler is te `dom' of het slimme contract is te hoog
ingeschat. Dit laatste is het meest aannemelijk want tijdens het bepalen
van het contract word er geen rekening gehouden met verschillende
feiten. Als speler $A$ een hoge kaart heeft van een bepaalde kleur en
speler $B$ ook. Dan zullen ze tijdens het spelen van dit slag beiden hun
hoge kaart tegelijk moeten opgooien en zal er maar een slag gehaald
worden. Verder wordt een hoge troefkaart twee keer geteld als slag.
Zowel in de troef ronde als in de hoge kaarten ronde.

Verder heeft de slimme speelagent geen gebruikt gemaakt van het contract
wat geboden is in het geval van de random contract agent en zijn er in
bijna 40\% van de gevallen teveel slagen gehaald.

Als laatste is de score niet geheel betrouwbaar, omdat elk gemaakt
contract even zwaar telt, terwijl beide agenten van het meeste aantal
slagen uitgaan. Een score factor bij een gehaald contract van $aantal
gehaalde slagen * 10$ zou dit beter reflecteren.

\begin{thebibliography}{XX}

\bibitem{bridge-opdracht}
W.A.~Kosters, Kunstmatige intelligentie Programmeer-opgave 1 van 2008
-- Bridge, \url{http://www.liacs.nl/~kosters/AI/bridge.html}

\bibitem{bridge-skelet}
W.A.~Kosters, Kunstmatige intelligentie Programmeer-opgave 1 van 2008
-- Bridge -- skelet programma, \url{http://www.liacs.nl/~kosters/AI/bridge.cc}

\bibitem{bridge-wiki}
Wikipedia, the free Encyclopedia, Bridge, latest version
\url{http://nl.wikipedia.org/wiki/Bridge}

\bibitem{kaartspel-wiki}
Wikipedia, the free Encyclopedia, Speelkaart, as of 25 Februari 2008,
\url{http://nl.wikipedia.org/wiki/Speelkaart}

\bibitem{collegeboek}
S.J. Russell en P. Norvig, Artificial Intelligence, A Modern Approach,
Second ediion, Prentice Hall, 2003.
\end{thebibliography}

\section*{Appendix}
Het programma gebruikt voor de experimenten ziet er als volgt uit:
\tiny
\advance\textwidth by 8cm
\advance\oddsidemargin by -3cm
\advance\evensidemargin by -3cm
\advance\topmargin by -2cm
\advance\textheight by 2cm
\advance\footskip by -2cm
\marginparwidth 0cm
\twocolumn
%c++ input preformatted with `source-highlight -n -f latex bridge.cc`
\include{bridge.cc}
\onecolumn
\end{document}