Wij zijn drie eerste jaars studenten Kunstmatige Intelligentie aan de UvA. Deze site is bedoeld voor het project, Zoeken Sturen en Bewegen.

Hieronder vindt u onze gegevens:

Rik Tobi (04 48710)
rtobi@science.uva.nl)

Aksel Ethembabaoglu (01 54644)
aethemba@science.uva.nl

Erik van den Hooven (03 23268)
ahooven@science.uva.nl

Voor ons project hebben we gebruik gemaakt van de volgende software.

* OS: Linux (RedHat distributie)
RedHat Homepage

* Java SDK: 1.4.2 (Sun MicroSystems)
Sun MicroSystems Homepage

* Java IDE: Eclipse
Eclipse IDE Homepage

Hardware:

In de vierde week van ons project waren we vrij om zelf een onderwerp te onderzoeken. We besloten om de verschillen tussen MiniMax en Alpha Beta Pruning te illustreren aan de hand van het spelletje Teeko. Dit omdat bij Teeko de zoekboom voor speloplossingen aanzienlijk groter is dan bijvoorbeeld bij Boter Kaas en Eieren. Verder leek het ons leuk om daar een mooie GUI in Java bij te maken.

In het spelletje Teeko zetten twee spelers om en om een symbool, kruisje danwel rondje, op een 5x5 bord. Elke speler moet vier symbolen plaatsten. Daarna moeten de symbolen worden rongeschoven. Het uiteindelijke doel is om vier op een rij te krijgen. Dat kan horizontaal, verticaal danwel diagonaal. Een andere mogelijkheid om te winnen is om een blok te vormen. Dus een 2x2 formatie.

Hypothese:

Met Alpha Beta Pruning kan aanzienlijk meer tijd bespaart worden in zoektijd dan bij MiniMax omdat de zoekboom velen malen groter is.

Werkwijze:

Het idee is om het spel Teeko te implementeren in Java. Ook MiniMax en Alpha Beta Pruning worden geimplementeerd in Java. De GUI is ook ontwikkeld in Java. Om de hypothese te ondersteunen willen we de verschillen meten in rekentijd. Alle tests worden op dezelfde apparatuur uitgevoerd voor een accuraat resultaat.

TAKEN

Samenvatten de taken voor de week:

Implementatie Teeko

Implementatie MiniMax en Alpha Beta Pruning

Implementatie van GUI

De implementatie van het MiniMax en Alpha Beta Pruning algrotime verliep deze week erg stroef. Het is ons niet gelukt de code goed aan het werk te krijgen. Daarom hebben we geen geteste resultaten van de verschillen tussen MiniMax en Alpha Beta op de zoekboom.

Voor een accurater beeld van onze bezigheden afgelopen week verwijzen wij u naar het labbook. Daar staan onze dag tot dagresultaten.

Mocht de implementatie toch slagen dan kunnen we de winst met Alpha Beta al vrij snel aantonen omdat in de eerste van het spel, waar de symbolen worden geplaatst, al vrij snel een enorme explosie aan successorstates gegenereerd word. Als gekeken word naar een zoekdiepte van drie ply, dan heeft het algoritme al 24x23x22x21x20x19 successorstates om af te zoeken. Daarin kan Alpha Beta al een duidelijk verschil maken ten opzichte van MiniMax.

Voor deze week is de volgende planning gemaakt:

Maandag 27 juni:

- Implementeren van Teeko (Aksel en Rik)
- Voor MiniMax successorstates genereren (Aksel en Rik)
- Beginnen aan GUI implementatie (Erik)

Dinsdag 28 juni:

- Implementatie afmken van MiniMax en Alpha Beta Pruning (Aksel en Rik)
- Verder aan GUI implementatie (Erik)

Woensdag 29 juni:

- Een goede heuristieke functie bedenken en implementeren (Aksel en Rik)
- Verschillen tussen de twee algoritmen meten en noteren (Aksel en Rik)
- Verder aan GUI implemenatie (Erik)
- (Indien nodig) Alpha Beta Pruning implementatie afmaken (Aksel en Rik)

Donderdag 30 juni:

- Resultaten verzamelen (Aksel en Rik)
- GUI implemenatie afmaken (Erik)
- Afmaken labbook en voorbereiden van presenatie (allen)

Vrijdag 31 juni:

- Presentatie (Aksel)

Helaas is niet alles volgens de planning verlopen. De resultaten daarvan kunt u teruglezen in het labbook.

AANNAMES

Voor ons onderzoek hebben we de volgende aannamen gedaan:

- De programmeertaal van de implementatie maakt geen verschil op de relatieve verbeteringen van een algoritme

- Onze huidige programmeerkennis is voldoende om de algoritmen succesvol te implementeren

DE BRONCODE

De broncode van ons project is te downloaden van de volgende locatie:

De relevante bestanden zijn:

AI.java

Grid.java

Teeko.java

Hieronder vindt u het dagboek wat we gedurende de week hebben bijgehouden.

Labbook Zoeken, Sturen en Bewegen
Juni 2005

Rik Tobi (04 48710, rtobi@science.uva.nl)
Aksel Ethembabaoglu (01 54644, aethemba@science.uva.nl)
Erik van den Hooven (03 23268, ahooven@science.uva.nl)

Inleiding

Ons project gaat over het spelletje Teeko. Teeko is een variant op het overbekende Tic-Tac-Toe (BK&E). Het wordt gespeeld op een 5x5 bord waarbij beide spelers elk eerst om en om 4 symbolen op het bord plaatsen. Vervolgens worden de symbolen ook weer om en om verschoven tot 1 van hen, ofwel een vier-bij-een rij(horizontaal, vertikaal of diagonaal), ofwel een twee-bij-twee blok gevormd heeft. De hypothese is dat het grotere speelveld en de afwezigheid van remise-situaties de zoekruimte dusdanig opblaast dat het voordeel van AlphaBeta pruning ten opzichte van MiniMax duidelijk naar voren treedt.

Om deze hypothese te toetsen wordt het spel en eerdergenoemde algoritmes in Java geimplementeerd en worden statistische gegevens als benodigde rekentijd en het aantal ge-expandeerde states verzameld. Zowel MiniMax als AlphaBeta pruning worden gebaseerd op de pseudo-code gegeven in Russell & Norvig's Artificial Intelligence: A Modern Approach. Met de enorme expansie van het aantal states is het interessant om het verschil tussen MiniMax en AlphaBeta pruning te zien. Omdat AlphaBeta delen van de zoekboom afsnijdt is het misschien zelfs mogelijk een paar dieptes verder te zoeken dan met MiniMax.

Software en apparatuur

Planning en uitvoering

-Maandag 27 Juni:
* Taak: Genereren van succesor-states

Het eerste agendapunt was de representatie van het bordrooster en het spel. Om de symbolen op het bord te representeren gebruiken we strings. Een andere mogelijkheid was om integers te gebruiken. Echter waren strings eenvoudiger te visualiseren en het spel leek hierdoor beter vertegenwoordigd in de code. Voor het bordrooster waren er verder ook verscheidene mogelijkheden, maar de twee beste opties waren representatie via arrays of representatie via vectoren. Er is gekozen voor arrays omdat de eerder gekozen strings beter werkten in arrays. Verder was het verschil puur implementatie-technisch. Rik heeft vervolgens de bord-representatie en de basis-methoden geimplementeerd. Onder basis-methoden verstaan we onder andere het verkrijgen van wie er aan zet is, welke zetten een speler mag doen en een licht grafische weergave van de spelsituatie.

(Een onverwachte bijkomstigheid was dat de teamgenoot van Erik ermee ophield en Erik zonder groepje zat. Na overleg sloot hij zich aan bij ons groepje. Er werd als tegenprestatie wel verwacht dat er extra werk werd verricht. Het plan was dat het mooi zou zijn als het spel een grafische front-end zou krijgen zodat het verschil tussen MiniMax en AlphaBeta goed zichtbaar werd. Erik nam het ontwikkelen van de GUI op zich, Rik en Aksel begonnen met de implementatie van MiniMax en AlphaBeta).

Verloop van dag:

Maandagochtend werd vooral gewerkt aan het afmaken van het in te leveren oefententamen. In de middag startte we ons eigen project. Tot dan toe was er slechts een bord representatie en konden er zetten gedaan worden, dus werd het tijd om de intelligentie van de computer te implementeren. Ons onderzoek richtte zich daarbij op het verschil tussen MiniMax en AlphaBeta Pruning. Zoals gezegd bestaat Teeko uit twee spelfasen: een 'placement' fase, waar de symbolen op het bord worden geplaatst, en een 'movement' phase, waar de stukken worden verschoven. Dit gebeurt op een 5x5 bord. In de eerste fase krijgen we al een interessant grote boom voor ons experiment. Als x, de speler, zijn symbool plaatst dan zijn er op diepte 1 al 24 successor-states, een diepte (ply) verder zijn dat er al 24x23, enz. De boom van slechts de eerste spelfase is dus al problematisch groot.

De volgende taak was de implementatie van het genereren van successor-states. Dit was lastig omdat er telkens een unieke nieuwe 'grid' moest worden gegenereerd, wat ivm. de gebruikte bordrepresentatie voor problemen zorgde. Dit is uiteindelijk opgelost door een counter variabele door te geven die bijhield welke states eerder gegenereerd waren.

Achievements:
* Implementeren spel/bord representatie
* Generenen van succesor-states
* Java GUI kennis opgedaan

-Dinsdag 28 Juni:
* Taak: Implementatie van MiniMax, Alpha-Beta

Verloop van dag:

MiniMax hadden was al eerder succesvol geimplementeerd in Prolog, dus er werden geen problemen voorzien vandaag de MiniMax code geimplementeerd te hebben. De successor-states werden gegenereerd, nu moest de rest van het algoritme geimplementeerd worden. De MiniMax kennis was een beetje weggezakt, dus er werd begonnen met documentatie lezen over MiniMax en Alpha-Beta. Ook hoopten we op internet losse MiniMax en AlphaBeta modulen te vinden voor Java, immers implementeren was niet het doel van het onderzoek. Die modulen waren helaas niet beschikbaar. Taak was om de MiniMax code zelf te implementeren.

Na de successor-state generatie werd er begonnen met implementeren aan de hand van pseudo code. Dat kostte tijd en er werd vastgelopen op het ontbreken van een depth-check. Allereerst werd er getest op de eerste fase van het spel, de placement fase. Het programma bleef 'loopen' en koos geen successor-state. Hoewel er een depth-check ontbrak moest er wel een successor-state uitkomen. Er werd niet ingezien wat het probleem veroorzaakte. Om dit te overkomen werd een depth-check geimplementeerd, met de hoop meer te weten te komen wat er fout liep in MiniMax. Met depth-check loop-te het programma echter alsnog. De reden van deze bug kwam niet boven water. Omdat het ondertussen al half zes was werd besloten te stoppen.

Thuis is er verder gewerkt. Na lang debuggen werkte het programma nog steeds niet. Toen is de MiniMax code herschreven met behulp van de MiniMax pseudo-code uit R&N's AI:AMA. Dat werkte goed, in ieder geval beter want de code was nog niet succesvol geimplementeerd. Erik was bezig met de GUI en dat schoot goed op. Het grootste probleem bij de implementatie van de GUI was dat er een koppeling moest worden gemaakt tussen een 2D array van buttons(die de hokje representeren) en de 2D grid-array. Door de knoppen van iconen te voorzien kon een link worden gemaakt tussen een kruisje en een rood appeltje, een nulletje en een groen appeltje en verder nog een de "nil" string (die een lege plaats in de 2D grid-array representeert) en een wit plaatje. Ook moest de GUI het verschil weten tussen de placement en de movement fase. Om dat verschil te kunnen maken moesten ook alvast wat zetten door de computer worden gegenereerd. Erik heeft hiervoor een zgn. placeholder functie geschreven die ervoor zorgt dat in ieder geval geen bezette plaatsen in worden genomen.

Achievements:
* MiniMax kennis opgefrist
* Gedeeltelijke implementatie van MiniMax
* Veel debug-ervaring opgedaan
* Eerste fase van implementatie van GUI

-Woensdag 29 Juni:
* Originele plan: Heuristieke functie en AlphaBeta afmaken, verschillen meten en noteren.
* Nieuw plan: MiniMax en AlphaBeta succesvol implementeren.

Verloop van dag:

De depth-check was geimplementeerd. Dingen die nu verkeerd liepen waren het plaatsen van symbolen en het switchen van beurt tijdens MiniMax. Na een tijdje waren die opgelost. Toch raakte ons programma constant in een loop. Het bleek dat de depth-check het toch niet goed deed, en, omdat met een diepte van drie de succesor-states in de miljarden liepen begrepen we waarom het programma dus leek te loopen. De depth-check werd aangepast. MiniMax was nog niet af maar er was behoefte aan een 'succesje'. 's Avonds is daarom AlphaBeta nog geimplementeerd. Erik vorderde een stuk meer dan Rik en Aksel. Inmiddels begon de GUI ergens op te lijken. Ook de tweede fase van het spel werd geimplementeerd in de GUI. In deze fase zijn de moves van de tegenstander niet meer zo belangrijk, als je maar kunt schuiven. Het was Erik nog niet duidelijk hoe die verschuiving grafisch moest worden maken. In eerste instantie was de bedoeling dat de speler kon schuiven door van het ene naar het andere hokje te slepen. Rik kwam met het idee om eerst te klikken op het plaatje dat je wilt verschuiven en vervolgens op het hokje waar je wilt neerzetten. Behalve dat dit veel prettiger speelt was het ook veel makkelijker te implementeren. Voor het oog vond Erik het leuk om het appeltje dat je wilt verschuiven grijs zou worden. Verder was het belangrijk om er voor te zorgen dat je niet het appeltje op een bezette plaats kon neerzetten, en dat je niet meerdere appeltjes grijs zou kunnen maken. Ook wilde Erik dat als je een grijs appeltje weer op zichzelf neer zou zetten er geen beurt verloren zou gaan.

Verschillen meten Achievements:
* MiniMax gedebugged
* Depth-check geimplementeerd
* Bovenste 'laag' van AlphaBeta geimplementeerd
* Verdere implementatie van GUI

-Donderdag 30 Juni:
* Originele plan: Resultaten verzamelen, GUI afmaken
* Nieuw plan: MiniMax succesvol laten lopen, MM laten aansluiten op AB, evalutiefunctie afmaken


Verloop van dag:

MiniMax doet correcte zetten. Nu moest er een heuristieke functie gemaakt worden om ook goede zetten te doen. De implementatie daarvan verliep gesmeerd. Echter MiniMax gebruikt de waarde van de heuristieke functie niet. AlphaBeta kan wel gebruikt worden maar aangezien die ook de heuristieke functie (en MM zelf) gebruikt werkt die ook niet goed. Wat betreft de GUI leek het ons mooi als er ook een klein menu balk bij zou komen. In die balk wilden we een nieuw spel kunnen beginnen, we wilden tussen MiniMax en AlphaBeta kunnen kiezen en de zoekdiepte kunnen instellen. Ook het afsluiten van het spel kan nu netjes in het hoofdmenu. Als extraatje leek het ons leuk om ook een help te maken met de spelregels en wat info over ons, de makers. Deze info kunnen we in de vorm van een html pagina bewerken die wordt ingeladen op het moment dat de help-menu-items worden geraadpleegd. Nog een belangrijke bug in het programma was de mogelijkheid om illegale zetten te doen, dit is nu ook opgevangen. De GUI is nu zo goed als af en moet enkel nog gekoppeld worden aan het hoofdprogramma.

Achievements:
* MiniMax opnieuw herscheven
* AlphaBeta gedebugged
* GUI af
* Eclipse een beetje geleerd

-Vrijdag 1 Juli:
* Taak: Presentatie geintegreerde GUI en spelcode


Verloop van dag:

Question mark.

Achievements:
* ?
* ?
* ?