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.
Software:
* OS: Linux (RedHat distributie)
RedHat Homepage
* Java SDK: 1.4.2 (Sun MicroSystems)
Sun MicroSystems Homepage
* Java IDE: Eclipse
Eclipse IDE Homepage
Hardware:
* Dell Optiplex GX280 (P4 2.8GHz, 512MB RAM, lokaal P124)
Dell Nederland Homepage
|
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:
Rik Tobi Homepage
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
Software:
* OS: Linux (RedHat distributie)
* Java SDK: 1.4.2 (Sun MicroSystems)
* Java IDE: Eclipse
Hardware:
* Dell Optiplex GX280 (P4 2.8GHz, 512MB RAM, lokaal P124)
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:
* ?
* ?
* ?
|