Springen naar inhoud

Alpha-beta algoritme


  • Log in om te kunnen reageren

#1

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 01 mei 2011 - 20:15

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) :

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
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Xenion

    Xenion


  • >1k berichten
  • 2609 berichten
  • Moderator

Geplaatst op 01 mei 2011 - 20:36

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.

#3

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 01 mei 2011 - 20:50

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.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#4

Xenion

    Xenion


  • >1k berichten
  • 2609 berichten
  • Moderator

Geplaatst op 01 mei 2011 - 21:09

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.)

#5

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 01 mei 2011 - 21:18

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://chessprogramm...ative 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
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#6

317070

    317070


  • >5k berichten
  • 5588 berichten
  • Moderator

Geplaatst op 01 mei 2011 - 21:47

Ik heb ooit nog een AI geschreven voor een 4-op-een-rij op de Ti-83+ :P 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. ;)
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#7

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 02 mei 2011 - 08:16

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.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#8

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 02 mei 2011 - 12:06

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:
| | | | | | | |
| | | | | | | |
| | | |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):
| | | | | | | |
| | | | | | | |
| | | |o|x| | |
| | | |x|o| | |
| | | |x|o| | |
|x| |x|o|o| | |

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

Zet van X maakt nu niet uit maar ik zou een blokkering verwachten:
| | | | | | | |
| | | | | | | |
| | | |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):
| | | | | | | |
| | | | | | | |
| | | |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)

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

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

...
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#9

Xenion

    Xenion


  • >1k berichten
  • 2609 berichten
  • Moderator

Geplaatst op 02 mei 2011 - 16:42

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?

#10

Xenion

    Xenion


  • >1k berichten
  • 2609 berichten
  • Moderator

Geplaatst op 02 mei 2011 - 16:50

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.

#11

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 02 mei 2011 - 17:18

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!
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#12

317070

    317070


  • >5k berichten
  • 5588 berichten
  • Moderator

Geplaatst op 02 mei 2011 - 18:30

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 :P

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.

| | | | | | | |
| | | | | | | |
| | | |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:
| | | | | | | |
| | | | | | | |
| | | |o|x| | |
| | | |x|o| | |
| | |x|x|o| | |
| | |x|o|o| | |
| | | | | | | |
| | | | | | | |
| | | |o|x| | |
| | |x|x|o| | |
| | |x|x|o| | |
| |o|x|o|o| | |
| | | | | | | |
| | | | | | | |
| | |o|o|x| | |
| | |x|x|o| | |
| | |x|x|o| | |
| |o|x|o|o| |x|
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#13

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 02 mei 2011 - 18:52

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:

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()
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures