[C++] Game Tree praktijk met 4 op een rij

[CU2morO]

Wat begonnen is als een onschuldig school projectje is inmiddels uit de hand gelopen tot een groots project vanwege mijn ongezonde nieuwsgierigheid Aanvankelijk was de opdracht om bekend te raken met een 3D omgeving zoals Glut (openGL), waar ik een 4-op-een-rij game in heb gemaakt die 2 spelers kunnen spelen en volledig functioneel is (win conditions e.d. functioneren ook). Nu ben ik zelf wat verder gegaan en leek mij dit een goeie kans om het principe Game Tree's wat beter te gaan begrijpen door een A.I. in deze applicatie te bouwen.

Wat een game tree inhoud is, in het kort gezegd, een boom structuur met x aantal childs per nodes als dat er mogelijke zetten zijn. Bij 4 op een rij is dit dus nooit groter dan 7 (Een 4 op een rij veld is 7 breed en 6 hoog). Naarmate de kolommen vol raken neemt het mogelijk aantal zetten af en zal de tree minder complex worden.

De praktische haalbaarheid daargelaten, wil ik als eerste een volledige game tree (in tegenstelling tot een gedeeltelijke game tree) implementeren. Nu is mijn vraag hoe ik hier, vanuit een praktisch oogpunt het beste mee kan beginnen. Het speelveld bestaat uit een vector van vectoren van het type bool die aangeeft welke speler het betreft. Ik heb ook al een aansluiting naar de 'AI' klasse waar een referentie naar deze matrix gegeven wordt, en er is ook al een functie die kijkt hoe lang de langst mogelijke aaneengesloten reeks is binnen het veld, gezien vanuit de laatst gedane zet.

Nu moet het opbouwen van de tree niet zo heel veel problemen geven met een recursief algorithme, alleen vraag ik me af hoe ik de data op moet slaan. Is het enkel mogelijk door in iedere node het volledige matrix te copieren? En stel dat ik vervolgens een goede boom heb weten te maken met alle mogelijke zetten er in, hoe bepaal ik specifiek voor 4 op een rij de 'beste' zet? Kijk ik naar het percentage van childs die in een win / loss eindigt? Kijk ik naar hoe diep de eerste win / loss zit vanaf mijn huidige positie, etc.

Ik ben dus op zoek naar wat tips met betrekking tot de praktische aanpak. Meeste sites met informatie over dit onderwerp beperken zich alleen tot vrij droge theorie, welke inmiddels wel duidelijk is.

[Harmsen]

Ik neem aan dat je de theorien over het min-max/alfa-beta algortimen gelezen hebt?
Anders staan er bij de link die jezelf geeft bij 'See also' er wel linkjes naar.

De opslag van het bord... Ik denk dat je daar zelf een efficiente oplossing voor moet gaan vinden. Het hangt allemaal een beetje af van het systeem waar je op gaat draaien.
Kort gezegd:
Je hebt de beginsituatie bordmatrix, en daarvanuit bepaal je alle mogelijke zetten en per zet het nieuwe matrix. De zet en matrix sla je op in de gametree. Dan ga je alle nieuwe matrixen af en per matrix bepaal je weer nieuwe zetten en matrixen en deze sla je weer op enz, enz.

Stel je hebt een beperkt intern geheugen dan zou je er voor kunnen kiezen om alleen de zetten op te slaan. Maar als je dan van die zet de bijbehorende matrix nodig hebt dan moet je die eerst maken. Dit kan processing power kosten.
Stel je hebt genoeg intern geheugen en dan sla je per zet ook de bijbehorende matrix op. Dan gaat het doorlopen en gebruiken van de game tree sneller.

Hoe je een ze evalueert hangt af van hoe de strategie van je AI gaat worden. Aan welke zetten ken je meer waarde toe? Is een zet maken die 3 blokjes op een rij zet beter dan een zet waarbij de tegenstander geen 3 blokjes op een rij kan maken in de zet erna? Dit zal je met waardes kunnen doen met een bijbehorende evalueer functie. Deze functie geef je de zet en nieuwe matrix mee en de functie geeft terug wat de waarde van deze zet is.
Door die waardes in aparte variabelen te zetten kan je deze eenvoudig aanpassen zodat je je AI kan fijntunen.

Ik heb de site gevinden van het AI vak van mijn oude school. In de link sheets staat meer informatie en simpele voorbeelden. Misschien heb je er iets aan.

http://www.engineering.tech.nhl.nl/engineering/vakken/hi/ki/

[SpiceWorm]

Je kan één speelbord in 32 bit opslaan (4x7=28, 4 bits over)
In totaal heb je 28*26*24*22*20*18*16*14*12*10*8*6*4*2 zetten die de AI kan doen.
Het totaal aantal mogelijke zetten (van beide partijen) in de tree is 28! (!). Dat zijn vrij veel mogelijkheden: 3*10^29. Alleen qua geheugengebruik 10^21 GB. Niet te doen dus. Je zou natuurlijk de eerste paar zetten volgens een ander algoritme kunnen doen, en pas na zoveel zetten dat de tree door te rekenen is hem daadwerkelijk door te laten rekenen.

[ Voor 202% gewijzigd door SpiceWorm op 17-01-2008 10:10 ]

[schoene]

SpiceWorm schreef op donderdag 17 januari 2008 @ 09:57:
Je kan één speelbord in 32 bit opslaan (4x7=28, 4 bits over)
In totaal heb je 28*26*24*22*20*18*16*14*12*10*8*6*4*2 zetten die de AI kan doen.
Het totaal aantal mogelijke zetten (van beide partijen) in de tree is 28! (!). Dat zijn vrij veel mogelijkheden: 3*10^29. Alleen qua geheugengebruik 10^21 GB. Niet te doen dus. Je zou natuurlijk de eerste paar zetten volgens een ander algoritme kunnen doen, en pas na zoveel zetten dat de tree door te rekenen is hem daadwerkelijk door te laten rekenen.

een spelbord is 6*7 groot, en per vak heb je 3 toestanden: leeg, kleur 1 en kleur 2. Hoe je dit in 32 bits zal opslaan is mij een raadsel.
Verder hou je er geen rekening mee dat veel zetten een gelijk spelbord als resultaat hebben, waardoor het uiteindelijke resultaat veel kleiner is.

Edit: en het moment dat iemand 4 op een rij heeft, moet je ook niet verder zoeken, dus daardoor verkleinen ook het aantal resultaten

[ Voor 57% gewijzigd door schoene op 17-01-2008 10:23 ]

[Harmsen]

SpiceWorm schreef op donderdag 17 januari 2008 @ 09:57:
Je kan één speelbord in 32 bit opslaan (4x7=28, 4 bits over)
In totaal heb je 28*26*24*22*20*18*16*14*12*10*8*6*4*2 zetten die de AI kan doen.
Het totaal aantal mogelijke zetten (van beide partijen) in de tree is 28! (!). Dat zijn vrij veel mogelijkheden: 3*10^29. Alleen qua geheugengebruik 10^21 GB. Niet te doen dus. Je zou natuurlijk de eerste paar zetten volgens een ander algoritme kunnen doen, en pas na zoveel zetten dat de tree door te rekenen is hem daadwerkelijk door te laten rekenen.

True, maar om de AI de goede zetten te laten rekenen zal je zetten die de user kan doen ook moeten meenemen... Omdat je de AI ook de mogelijk moet laten bereken om de gebruiker bepaalde zetten te forceren zodat hij daarna in een betere uitgangspositie zit.
Dan wordt het aantal zetten 28 faculteit, oftewel te groot om alle zetten op te slaan.


Nog een manier van optimaliseren is de van de eerste 5 zetten de boom te maken. Daar het beste pad van zoeken en het het bijbehorende matrix te gebruiken om de boom verder op te bouwen. Zo sla je niet alles op en kan je de boom dieper bereken. Nadeel is wel dat je mogelijk niet de beste zet kiest omdat je eerst maar tot 5 zetten diep rekent.

Je zal ergens het compromis tussen snelheid en nauwkeurigheid moeten vinden.

[SpiceWorm]

schoene schreef op donderdag 17 januari 2008 @ 10:19:
een spelbord is 6*7 groot, en per vak heb je 3 toestanden: leeg, kleur 1 en kleur 2. Hoe je dit in 32 bits zal opslaan is mij een raadsel.
Verder hou je er geen rekening mee dat veel zetten een gelijk spelbord als resultaat hebben, waardoor het uiteindelijke resultaat veel kleiner is.

Edit: en het moment dat iemand 4 op een rij heeft, moet je ook niet verder zoeken, dus daardoor verkleinen ook het aantal resultaten

Idd, ik was ff wat te snel. Conclusie is iig dat domweg de hele tree in één keer uitrekenen niet te doen is (met hedendaagse faciliteiten).
Nu is het inderdaad waar dat een aantal zetten hetzelfde speelbord tot resultaat hebben. Hoe wou je dat gaan uitvinden in een boom van 28! ?

[schoene]

Volgens mij is 4 op een rij al volledig opgelost. Ik weet echter niet of het gebeurt door het volledige spelverloop op te slaan, of door een bepaalde strategie te volgen.

[SpiceWorm]

Wat je misschien wel kan doen, is niet voor elke node een volledig speelbord op te slaan, maar enkel de wijziging.

ff rekenen.
Elke node heeft 2 32 bit pointers (op een 32 bit systeem), of referenties (behalve natuurlijk de laatste rij, dat scheelt). Voor elke zet/verandering op het speelbord moet je de positie van de nieuwe steen opslaan. Dit kan in 8 bits. 7 bits om de positie te definiëren en 1 bit voor de kleur.
Dus in ieder geval heb je per node 8 + 64 bit nodig. Dat scheelt al wat in het geheugen gebruik.
Dan kun je nog steeds niet de gehele tree uit rekenen.
Dan kun je voor elke node die je wel hebt uitrekenen hoeveel winsituatie er zijn, en daar misschien een gewicht aan hangen of de situatie voor de menselijke speler makkelijk te voorkomen is.

[prototype]

De hele gametree berekenen, dat is trouwens wel een mogelijkheid icm b.v. een relationele database he? Je zou vooraf dus alles al kunnen berekenen en het op kunnen slaan in een database.

Maar nu even zonder ongein, een hele gametree in 't geval van zo'n zerosum game berekenen is niet zo bijster handig om redenen die reeds genoemd zijn in dit topic. Ook is minimax al genoemd met alfabeta pruning, en ik raad je aan om naar dit algoritme te kijken. Bij minimax komt het er op neer dat er sprake is van een minimaliserende stap en een maximaliserende stap, net als dat je bij een spelletje 4 op een rij bij jouw beurt je kansen probeert te vergroten om te winnen (maximaliseren) en die van de tegenstander te minimaliseren. Bij alfabeta komt het er op neer dat je heuristiek ook moet betrekken bij je AI: er zijn bepaalde plekken misschien op het speelveld waarvan de regels al bepalen wat de mogelijkheden zijn. Bij dammen is het bijvoorbeeld zo dat je de spelstukken die aan de rand van het bord zitten niet kan winnen, en het is dan ook niet zo handig om daar rekenkracht aan uit te besteden. Ook weet je dat je bij bepaalde zetten misschien meteen verliest en ook dan is het niet interessant om de boom vanaf dat punt verder te bepalen: je snijdt de subboom op dit punt af, en om deze reden wordt het ook wel 's alfa beta cuttoff genoemd.

Hier zijn iig meer dan genoeg artikelen over geschreven en ik raad je dan ook aan om even google hiervoor erbij te pakken (of een vak over A.I.)

[ Voor 22% gewijzigd door prototype op 17-01-2008 10:56 ]

[SpiceWorm]

schoene schreef op donderdag 17 januari 2008 @ 10:51:
Volgens mij is 4 op een rij al volledig opgelost. Ik weet echter niet of het gebeurt door het volledige spelverloop op te slaan, of door een bepaalde strategie te volgen.

Nu je het zo zegt, ligt mij daar idd ook iets van bij.

[leuk_he]

SpiceWorm schreef op donderdag 17 januari 2008 @ 10:53:
[...]


Nu je het zo zegt, ligt mij daar idd ook iets van bij.

http://en.wikipedia.org/wiki/Connect_Four

Daar staan wat linkjes naar 2 "oplossingen"