Zoekdiepte en rekentijd bij Boter, Kaas en Eieren

Niels Out (0435899)
Dennis Roof (0490474)
Wes Oldenbeuving (0435880)

Eerstejaars Studenten AI aan de UvA

25 januari 2005

Abstract

Dit artikel zal aantonen dat door het gebruik van het minimax-algorithme, bij grotere zoekdiepten een voor beide spelers optimaal spel gespeeld zal worden; de meeste spellen zullen gelijk eindigen.

Introductie

In dit artikel zullen wij het effect van de zoekdiepte op de verhouding tussen de winkans en de benodigde resources, zoals rekentijd en het aantal geopende states, voor een boter-kaas-en-eieren agent, die gebruik maakt van minimax, onderzoeken.

Idee

Doordat beide spelers bij een voldoende grote zoekdiepte zeer sterk spelen, zal een toename aan zoekdiepte en resourcegebruik leiden tot een optimaal spel van beide spelers, ook bekend als remise.

Aanpak

Eerst hebben wij gekeken hoe mensen het boter-kaas-eiren probleem oplossen. Het blijkt dat mensen een aantal zetten diep erover nadenken, maar niet alle mogelijkheden afgaan, en ook niet elke situatie evalueren. Mensen kijken vooral naar eindsituaties. 

Voor de computer is dit minder makkelijk, omdat het voor de computer lastig is om te beslissen welke situatie wel, en welke niet geevalueerd dient te worden, en welke situatie beter is dan een andere.
Daarom hebben wij gekozen om een heuristiek in te bouwen, die een stelling globaal kan beoordelen aan de hand van de meest waardevolle posities. Deze posities zijn beoordeeld op mogelijkheden om te winnen. Een situatie die al gewonnen is heeft dus een hoge waarde.

Om het beste resultaat te krijgen gebruiken we het minimax algoritme om in de diepte te zoeken en de meest waardevolle zetten terug te geven. In de diepte wordt door middel van de heuristiek een waarde toegekend.
Minimax geeft altijd het beste resultaat, omdat alle zetten en opvolgers worden bekeken binnen de zoekdiepte. Minimax geeft voor z'n eigen speler de hoogste waarde uit de vertakking, en als de tegenstander in de zoekboom aan de beurt is, de laagste waarde, dit varieert per vertakking.

We hebben voor de implementatie gebruik gemaakt van Prolog, omdat het een logische taal is, die de implementatie op een natuurlijke wijze makkelijk maakt. Via deze implementatie hebben we berekend hoeveel states en computer resources benodigd zijn om per zoekdiepte een volledig spel tegen twee minimax agents te spelen. Deze gegevens zijn in een tabel verwerkt die leiden tot de oplossing van de vraagstukken.

Methode om Boter-Kaas-Eieren door computer te laten spelen.

In onze methode is minimax gebruikt, dit systeem rekent eerst alle zetten uit tot een bepaalde diepte, en afhankelijk van wie er aan zet is, kiest het de maximale of de minimale score. Als je zelf aan zet bent, zal het de beste zet kiezen, waarbij ook rekening gehouden wordt met de zetten die de tegenstander daarna kan doen (tot op bepaalde diepte). Minimax zorgt er voor dat altijd de beste zet gedaan wordt, voor zover dat uitgerekend kan worden tot een zekere diepte.

De code is bij ons geimplemeteerd in het doezet predikaat, waar het minimax predikaat wordt aangeroepen, welke een lijst met goeie zetten geeft. Uit deze zetten wordt er vervolgens in doezet 1 random uitgekozen. 

Minimax krijgt een evaluatie als het spel in een bepaalde state klaar is, of als de maximale zoekdiepte bereikt is. Als dit beiden niet het geval is, dan wordt er een lijst van opvolgers gegenereerd via het predikaat moves. Deze opvolgers kunnen direct gemaakt worden uit een bepaalde spel-state. 

Door middel van het predikaat bestmove3 wordt uit de lijst met opvolgens de beste uitgekozen. Bestmove3 roept daarvoor minimax aan, om een evaluatie van de states te krijgen, om vervolgens de beste hieruit te kunnen kiezen. 

Het klaar predikaat kijkt in een bepaalde spel-state of er geen leeg vakje is, of dat er ergens een rij van 3 dezelfde dingen bestaan, anders zal het falen.
Het predikaat evalueer geeft afhankelijk van de gebruikte heuristiek een numerieke waarde die aangeeft hoe goed een stelling is.

We hebben hier met het predikaat meer_keer een schil omheen gemaakt die meerdere keren een spel door de computer laat uitvoeren, waarbij telkens het predikaat sp aangeroepen wordt. In sp wordt een spel voor 0 en X bij een ingestelde zoekdiepte en heuristiek uitgevoerd, en wordt teruggegeven de winnaar, hoeveel states er bekeken zijn en hoe lang de cpu er over deed.

Hieronder staat een kort overzicht van de werking van de belangrijkste predikaten.

meer_keer 	x aantal keren sp uitvoeren, uitkomsten optellen en weergeven 	
sp 		een zet doen voor 0/X, zichzelf opnieuw aanroepen totdat spel afgelopen is 
evalueer 	geef evaluatie van stelling y 
klaar 		als spel is afgelopen -> return true 
minimax 	als klaar of zoekdiepte bereikt -> evalueer en return evaluatie 
		anders moves en roep bestmove3 aan 
bestmove3 	geef van lijst z evaluties uit minimax, en return lijst met hoogsten 
moves 		creeer lijst met mogelijke opvolgers 

Evaluatie

In het nu volgende stuk zal de speler met de laagste zoekdiepte de domste speler worden genoemd en de speler met de hoogste zoekdiepte zal de slimste speler worden genoemd. Even slimme spelers hebben eenzelfde zoekdiepte. 

In theorie zal bij gelijke intelligentie ook een meerderheid van de gespeelde spellen in remise moeten eindigen, dit is echter niet het geval gebleken. Bij het testen van alle zoekdieptes tot op 7 plies diep, bleek dat 60% van de spellen remise werd. Van de overige spelsituaties won de beginnende speler er ongeveer een keer zoveel als de tweede speler, met 27% winst tegen 13% winst. Voor de het aantal gewonnen spellen per speler, zie Tabel III en Figuur 1.

Het verschil in het aantal gegenereerde spelstates per speler is bij gelijke intelligentie-spellen niet altijd even significant. Voor alle zoekdieptes tot op 4 plies genereert de beginnende speler 1.27 tot 1.87 keer zo veel states als de tweede speler. De toename lijkt kwadratisch of zelfs exponentieel te zijn.

Bij een zoekdiepte van 5 en 6 plies, neemt de groei sterker toe, naar een factor van 3.1. De zoekdiepte van 7 plies heeft zelfs een factor 5.2! Deze sterke toename sluit kwadratische groei uit, dus zal de groei waarschijnlijk exponentieel zijn. Voor het aantal gegenereerde states, zie Tabel II. Figuur 2 toont alle verschilfactoren.

De domste speler eerst laten spelen resulteert in een spel dat veel minder states genereert dan een spel waarbij de slimste speler eerst speelt. Bij een zoekdiepte van 7 plies is het verschil tussen de domste of de slimste speler eerst laten spelen een factor 5.25, wat neerkomt op ruim 37 miljoen zetten verschil. 

De eerste zet tot op een grote diepte doorrekenen genereert heel veel zetten. Zelfs bij twee even intelligente spelers is het verschil in zetten gegenereerd tussen de beginnende speler en de tweede speler, zoals eerder al vermeld, een factor 2 tot 31.

Na voor alle mogelijke wedstrijden, met twee spelers met zoekdiepte 1 t/m 7, de overwinningen per speler en de remises geteld te  hebben, blijkt dat de beginnende speler ruim een derde (36%) van alle wedstrijden wint, dat ongeveer de helft (48%) van de spellen in remise eindigt en dat de tweede speler geen schijn van kans heeft (16% gewonnen.) De statistieken staan in figuur 3.

Opvallend is dat op de hogere zoekdiepten de zoektijd enorm toeneemt. Dit komt doordat de hoeveelheid gegenereerde zetten exponentieel groeit met de zoekdiepte en de zoektijd direct afhangt van het aantal gegenereerde zetten. Vooral in het begin stijgt de zoektijd relatief snel, beginnend met een factor 6 per diepte. Bij hogere diepten is de relatieve groei met een factor 3 laag, maar de absolute groei in seconden is wel zeer hoog. Voor het uitspelen van 200 spellen met twee spelers met zoekdiepte 7 was 45 minuten en 40 seconden nodig.

Als laatste volgt hier nog de relatie tussen de zoekdiepte van beide spelers en de daadwerkelijke winkans. De conclusies zijn gebaseerd om Tabel IV, waarin alle win-uitslagen sterk vereenvoudigd zijn weergegeven.

Voor diepte 1 is de speler met de hoogste zoekdiepte de grootste kanshebber op de overwinning. Op zoekdiepte 2 heeft de beginnende speler de grootste winkans, ongeacht de intelligentie van z'n tegenstander. Vanaf zoekdiepte 3 is de uitslag overheersend remise, afgewisseld met een overwinning voor de beginnende speler.

Conclusie en discussie

Uit dit onderzoek kan worden geconcludeerd dat, hoewel er op grotere zoekdiepten voornamelijk gelijk gespeeld wordt, de winkans niet duidelijk gerelateerd kan worden aan de benodigde resources. Bij een gemiddeld gebruik van resources kan de beginnende speler vaak winnen of spelen beide spelers gelijk. Een toename aan resourcegebruik en zoekdiepte leidt eerder tot een grotere remisekans, dan tot een grotere winkans.
Appendices

Alles statistieken zijn per 200 spelletjes gespeeld, de tabellen hebben links de zoekdiepte van de eerste speler (rondje) en boven de zoekdiepte van de tweede speler (kruisje.) De statistieken per cel geven dus de statistieken van 200 spellen tussen de twee spelers.

Tabellen: Alleen beschikbaar in het KWord document.
Tabel I: Tijdsgebruik (sec)
Tabel II: States gegenereerd (O/X)
Tabel III: Speluitkomst
Tabel IV: Sterkste speler (O/X/Remise)

Figuur 1: Winkans gelijke intelligentie
De onderstaande waarden zijn verkregen door bij alle zoekdiepten alle overwinningen, bij spellen tussen spelers van gelijke intelligentie, op te tellen.

O Wint / X Wint / Remise (Totaal aantal spellen): 383/179/838 (1400)
O Wint / X Wint / Remise (Totaal aantal spellen): 27%/13%/60% (100%)
Figuur 2: Verschil gegenereerde zetten gelijke intelligentie
De onderstaande waarden zijn de verschilfactoren tussen het aantal gegenereerde zetten van de eerste speler en de tweede speler, bij gelijke intelligentie.

De toename in de toename is niet gelijk, de groei is dus niet kwadratisch. Vanwege de steeds sneller toenemende groei, vermoeden wij echter wel een exponentiele groei.

1.27 (1 diep)	
1.38 (2 diep)	(+0.11)
1.6 (3 diep)	(+0.22)	(+0.11)
1.87 (4 diep)	(+0.27)	(+0.05)
2.5 (5 diep) 	(+0.63)	(+0.36)
3.1 (6 diep)	(+0.6)	(-0.03)
5.2 (7 diep)	(+1.9)	(+1.3)

Figuur 3: Effect van eerst spelen op winkans
De onderstaande waarden zijn de totalen van alle gespeelde wedstrijden tussen alle spelers met zoekdiepte 1 t/m 7.

Winst O / Winst X / Remise (Totaal): 3557/1508/4735 (9800 spellen totaal)
Winst O / Winst X / Remise (Totaal): 36%/16%/48% (100% totaal)

Figuur 4: Totale tijdsduur metingen
33760 seconden. Dit is gelijk aan 9 uur, 22 minuten en 40 seconden.

Figuur 5: Tijdstoename bij gelijke intelligentie

Formaat:
Diepte X: Seconden	(Factor meer ten opzichte van diepte X-1)

Diepte 1: 0.27
Diepte 2: 1.66	(Factor 6.14)
Diepte 3: 8.38	(Factor 5.04)
Diepte 4: 45.17	(Factor 5.39)
Diepte 5: 208	(Factor 4.60)
Diepte 6: 861	(Factor 4.13)
Diepte 7: 2720	(Factor 3.15)