Alpha-beta algoritme

[jhnbk]

Ik ben bezig met het schrijven van een AI voor een bordspel. Om wat met de gangbare technieken te testen besloot ik het eerst eenvoudig aan te pakken en een vier-op-een-rij AI te schrijven.

Momenteel heb ik het zodanig voor elkaar gekregen dat alpha-beta werkt zoals zou moeten. (M.a.w. ik krijg de correcte scores terug bij gebruik van een eenvoudige quotering van de posities)

Nu zou ik graag de volledige variant verkrijgen (tot maxdepth) en niet enkel de beste zet (depth=0) om meer inzicht te krijgen in de werking van quotering/zoeken.

Ik heb volgende code in python(bevat uiteraard veel meer maar ik geef enkel het essentiële) :

Code: Selecteer alles

01 def alphabeta(node, depth, maxdepth , alpha, beta, player, maxplayer):

02 	global bestmove

03 	if depth == maxdepth:

04 		return node.value(player)

05 	if player == maxplayer:

06 		for child in node.legalMoves():

07 

node.makeMove(child,player)

08 

score = alphabeta( node, depth+1, maxdepth, alpha, beta, 3-player, maxplayer) 

09 

node.undoLastMove()

10 

if score> alpha:

11 

if depth==0:

12 

bestmove = child

13 

alpha = score

14 

if beta <= alpha:

15 

break

16 		return alpha

17 	else:

18 		for child in node.legalMoves():

19 

node.makeMove(child,player)

20 

score = alphabeta( node, depth+1, maxdepth, alpha, beta, 3-player, maxplayer) 

21 

node.undoLastMove()

22 

if score<beta:

23 

beta = score

24 

if beta <= alpha:

25 

break

26 		return beta

Iemand enig idee?

Noot:

- spelers worden gesymboliseerd door getallen 1 & 2 dus geeft 3-player de andere speler

- regel 11-12 slaat de beste zet op maar dus zonder de volledige variant

[Xenion]

Het algoritme heet alfa-beta pruning. Dat betekent dus dat je snoeit in de zoekboom. Het is dus normaal dat niet alle mogelijkheden bekeken worden.

Als je de volledige zoekboom wil, dan moet je de gewone minimax toepassen.

Ik heb het niet in detail bekeken, maar op het eerste zicht denk ik dat je de return statements moet 'uitstellen'.

Zoals je het algoritme nu hebt geschreven geeft de methode de 'beste' waarde terug van zodra het die tegenkomt. Om de volledige boom te krijgen zou je die waarde even moeten opslaan in een variabele en dan nog de volgende mogelijkheden berekenen. Pas wanneer je het laatste child berekend heb return je die waarde.

Op die manier zou je de volledige boom moeten verkrijgen.

[jhnbk]

Ik denk dat je mij verkeerd hebt begrepen. Ik ben niet geïnteresseerd in de boom maar in de beste variant. M.a.w. zoals bij schaak computers na analyse van een welbepaalde positie ben ik niet geïnteresseerd in dat het feit dat 25. Qh6+ de beste zet is maar in de volledige lijn die zou volgen bv. 25. Qh6+ Kg8 26. Bg6 Bxf3 27. Qh7+ Kf8 28. Qh8#

Andere, slechtere varianten, heb ik niet nodig.

(Volledige boom opslaan is mogelijk maar nutteloos aangezien het enorm veel geheugen zal vragen. Nu niet voor 4-op-een-rij uiteraard)

Ik heb het niet in detail bekeken, maar op het eerste zicht denk ik dat je de return statements moet 'uitstellen'.

Dan komt de recursiviteit in het gedrang vrees ik.

[Xenion]

Ah, je hebt gelijk, ik dacht inderdaad dat je iets anders bedoelde.

Volgens mij moet je het zoeken op de plaatsen waar je de recursieve aanroep doet en dus een waarde gereturned krijgt.

Als je bij elke

for child in node.legalMoves():

Het child met de beste waarde (die je gaat returnen) opslaat, krijg je dan niet dat beste pad?

(Ik heb zelf het algoritme nooit moeten toepassen, enkel eens op papier moeten toepassen voor TicTacToe.)

[jhnbk]

Zou moeten werken. Ga ik straks/morgen eens naar kijken.

Ik heb ondertussen ook niet stil gezeten en naar ik de verzamelde internet info begrijp werkt het bij schaken als volgt:

iterative deepening + alpha-beta pruning e.a. + move ordening

Principe:

- zoek eerst 1 ply deep

- 'sorteer de zetten'

- zoek 2 ply

- sorteer

- zoek 3 ply

- ...

Blijkbaar is er door goed te sorteren en een transposition table te gebruiken het even snel en zelfs beter als zonder iterative deepening.

It has been noticed, that even if one is about to search to a given depth, the iterative deepening is faster than searching for the given depth immediately. It happens due to dynamic move ordering techniques, such as using PV-, hash- and refutation moves determined in previous iteration(s), as well the history heuristic.

Bron: http://chessprogramming.wikispaces.com/Iterative+Deepening

Valt uiteraard te bekijken voor mijn toepassing maar vermoedelijk overkill.

Een ander optie is de volgende denk ik: aangezien het depth first is kan ik twee variabelen aanmaken, namelijk current_variant en best_variant. Indien er ergens een betere gevonden wordt kan ik dan altijd stellen dat best_variant = current_variant

[317070]

Ik heb ooit nog een AI geschreven voor een 4-op-een-rij op de Ti-83+ Maar dat ging niet meer dan 2 zetten diep. Wat ik deed (ook in andere bord-AI) was de volledige onderzochte tree (sinds het begin van het spel!) opslaan in een object en hem steeds automatisch optimaal gesorteerd houden. Wat je dan enkel moet doen is de niet-gebruikte en slechte takken wegsnijden en bijhouden in welke 'node' het spel zich momenteel bevindt. Alle bewerkingen doe je op die boom en worden automatisch opgeslagen en bijgehouden. Communicatie tussen verschillende delen van je algoritme gebeurd dan enkel door de positie in je boom door te geven en de boom te bewerken.

In mijn ervaring met AI is dat een eenvoudige manier van werken. Alle informatie zit gecentreerd, er is nergens informatie dubbel opgeslagen en je kunt goed de informatie scheiden van de bewerking ervan. Er verdwijnt ook nooit relevante informatie die dan moet gereconstrueerd worden.

Een andere manier is om niet met 'zetten'-objecten te werken, maar met 'varianten'-objecten. Al ben ik de ene keer dat ik dat geprobeerd ben vastgelopen in mijn Shogi-AI.

[jhnbk]

An sich een goed idee maar voor spelletjes met een grote branching factor gaat dat enorm veel geheugen operaties vragen en zal dat traag zijn. Limiteren tot diepte = 2 is nu niet echt wat ik voor ogen heb

Een techniek zoals zou kunnen staat hier maar lijkt mij niet eenvoudig in python vanwege memcpy.

[jhnbk]

Bon, ondanks mijn wens om de beste variant ook te verkrijgen loopt er nu al iets mis.

Functie node.value(player) geeft scores van respectievelijk 100, -100 en 0 terug. 100 indien 4-op-een-rij voor player, -100 indien voor tegenstander en anders gewoon nul.

(Deze aanpak is nog vrij dom aangezien er niet echt aan planning gedaan wordt. 3 en 2 op een rij zou ook geëvalueerd moeten worden, enz. )

Nu heb ik een test positie met X aan zet:

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

| | |x|o|o| | |

Deze positie is X aan zet en moet duidelijk een bedreiging blokkeren maar doet dat niet (fout):

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

|x| |x|o|o| | |

O vindt correct de beste zet om een 4-op-een-rij te forceren:

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

|x| |x|o|o| |o|

Zet van X maakt nu niet uit maar ik zou een blokkering verwachten:

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

|x|x|x|o|o| |o|

Nu gaat O eerst blokkeren in plaats van direct een 4-op-een-rij te scoren (fout):

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | |o|x|o| | |

|x|x|x|o|o| |o|

Iemand enig idee hoe dat zou kunnen komen?

Als ik de legal moves in de omgekeerde volgorde meegeef lukt het blokkeren alvast wel (met achteraf domme moves wegens de povere evaluaties)

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

| | |x|o|o| | |

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

| | |x|o|o| |x|

...

[Xenion]

Bij "Zet van X maakt nu niet uit maar ik zou een blokkering verwachten":

Welke minimax waarden krijg je voor de blokkerings-zet en voor de zet die winst zou opleveren?

Berekent het die winst-waarde nog of stopt het algoritme bij die blokkering?

Je zei eerder dat je algoritme de correcte minimax teruggaf:

Kan ik hier dan uit opmaken dat het algoritme wel werkt, maar dat je het "verwachte verwachte" spelverloop er nog niet juist kan uithalen?

Of is dit het reëele spelverloop?

[Xenion]

100 indien 4-op-een-rij voor player, -100 indien voor tegenstander en anders gewoon nul.

Vergeet je hier niet te controleren of player==maxplayer?

Als player==maxplayer dan moet de minimax 100 geven bij 4 op een rij, maar als player==minplayer dan moet er -100 uit komen.

Maxplayer streeft naar de hoogste waarde en minplayer naar de laagste waarde.

[jhnbk]

return node.value(player) geeft de score vanuit het oogpunt player.

Ik ga hier eind deze week mee verder. (Voorlopig was het even een intermezzo tijdens het thesis programmeerwerk ) Alvast bedankt!

[317070]

An sich een goed idee maar voor spelletjes met een grote branching factor gaat dat enorm veel geheugen operaties vragen en zal dat traag zijn. Limiteren tot diepte = 2 is nu niet echt wat ik voor ogen heb

Maar zetten van jezelf die slecht zijn verwijder je uit je boom, en zetten van de andere die voor jou te goed zijn ook. En oude varianten met bordposities die niet meer kunnen voorkomen kun je ook uit je boom verwijderen. Als je het goed implementeert heb je hoogstens evenveel geheugen nodig alsof je gewoon zetten doorgeeft, meer zelfs, het grote voordeel is dat het zo weinig geheugen(operaties) vergt omdat alles slechts 1x opgeslagen wordt en nooit moet gekopieerd worden naar ergens anders. (tenminste in pass-by-reference talen)

Die diepte=2 was dan ook omdat het op de Ti-83+ was

Ook is veel geheugen gebruiken niet hetzelfde als traag zijn. Als je dat geheugen netjes kunt bewerken zonder de rest ervan te verplaatsen, maakt het zelfs niet echt uit hoeveel geheugen je gebruikt.

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | | |x|o| | |

| | |x|o|o| | |

Deze positie is X aan zet en moet duidelijk een bedreiging blokkeren maar doet dat niet

Hij moet helemaal geen bedreiging blokkeren, hij kan bijvoorbeeld net zo goed zo spelen:

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | | |x|o| | |

| | |x|x|o| | |

| | |x|o|o| | |

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | | |o|x| | |

| | |x|x|o| | |

| | |x|x|o| | |

| |o|x|o|o| | |

Code: Selecteer alles

| | | | | | | |

| | | | | | | |

| | |o|o|x| | |

| | |x|x|o| | |

| | |x|x|o| | |

| |o|x|o|o| |x|

[jhnbk]

Correct zo kan het ook. Conclusie: twee mogelijkheden; geen van beide genomen => er zit ergens een foutje in.

Wordt vervolgt ...

EDIT:

Overigens: ik heb voorlopig alles geïmplementeerd met bitboards (mogelijk niet efficient geprogrammeerd maar zeker sneller als geknoei met arrays)

Voor de geïnteresseerden:

Code: Selecteer alles

class Bitboard:

def __init__(self):

self.player1 = 0

self.player2 = 0

self.moves=[]

def clear(self):

self.player1 = 0

self.player2 = 0

self.moves=[]

def legalMoves(self):

o = self.player1 | self.player2

m = [i for i in xrange(7) if o & (2**41 >> i) ==0]

#m.reverse()

return m

def undoLastMove(self):

#make correct column

c= 2**41 >> self.moves.pop()

o = self.player1 | self.player2

if c & o == c:

self.player1 = self.player1 & (~c)

self.player2 = self.player2 & (~c)

else:

for i in xrange(5):

c = c >> 7

if c & o == c:

self.player1 = self.player1 & (~c)

self.player2 = self.player2 & (~c)

break

def makeMove(self,column,player):

o = self.player1 | self.player2 # occupied squares

if column<0 or column>6:

return False

#make correct column

c= 2**41 >> column

for i in range(6):

if o & c == c:

break

c = c >> 7

if i==0:

return False

if c !=0:

#shifted to far

if player==1:

self.player1+=(c << 7)

else:

self.player2+=(c << 7)

self.moves.append(column)

return True

else:

# if c = 0 shifted out of board => bottom row was empty

if player==1:

self.player1+=(1 << (6-column) )

else:

self.player2+=(1 << (6-column) )

self.moves.append(column)

return True

def value(self,player=1):

v = (0,0)

p1 = self.player1

p2 = self.player2

o = p1 | p2

# check horizontal win

horizontal = 15 # 0b1111

while horizontal<2**41:

if o & horizontal == horizontal:

if p1 & horizontal == horizontal:

v = (100,-100)

if p2 & horizontal == horizontal:

v = (100,100)

horizontal = horizontal << 1

#check vertical win

vertical = 2113665 # 1000000100000010000001

while vertical<2**41:

if o & vertical == vertical:

if p1 & vertical == vertical:

v = (100,-100)

if p2 & vertical == vertical:

v = (-100,100)

vertical = vertical << 1

#check diagonal win 134744072

for i in xrange(4):

diagonal = 16843009 << i

for i in xrange(3):

if o & diagonal == diagonal:

if p1 & diagonal == diagonal:

v = (100,-100)

if p2 & diagonal == diagonal:

v = (-100,100)

diagonal = diagonal << 7

for i in xrange(4):

diagonal = 2130440 << i

for i in xrange(3):

if o & diagonal == diagonal:

if p1 & diagonal == diagonal:

v = (100,-100)

if p2 & diagonal == diagonal:

v = (-100,100)

diagonal = diagonal << 7

return v[player-1]

def __str__(self):

p1 = self.player1

p2 = self.player2

o = p1 | p2

b = '|'

for i in xrange(1,43):

if o&1 ==1:

if p1&1==1:

b='|O'+b

if i%7==0 and i!=42:

b='|\n'+b

else:

b='|X'+b

if i%7==0 and i!=42:

b='|\n'+b

else:

b='| '+b

if i%7==0 and i!=42:

b='|\n'+b

o=o>>1

p1=p1>>1

p2=p2>>1

return b.lower()