% % $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{}\\ \\ 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}