Problem with Boardgame AI (Minimax Algorithm)

BlitzMax Forums/BlitzMax Programming/Problem with Boardgame AI (Minimax Algorithm)

maverick69

(Posted 2011) [#1]

Hi,

I'm currently trying to do a simple 2-Player board game, with very simple rules:

- 8x8 board play field
- each player has his own color (red gems, blue gems)
- each player's aim is to making 2x2 squares of his color to remove them
- the game is won when all gems of one colour are removed

I wanted to implement a simple minimax algorithm, but run into problems, so I've done a small test/debug app that renders all my nodes the shows me what is the best next move.

With a click on a node I can show / hide the childs of it.

When I press "M" the best move the player can do is becoming the new root node.

When the mouse pointer is over a node and you press "Q" this will become the new root node (this way you can checkout how the KI reacts to several board states).

So I can watch the ki playing against itself, by clicking M and can surf through the nodes to see why a decision for the best move was made.

However, the AI seems to do very dumb moves very often, and I can't figure out whats wrong with my code.

Probably you can have a look at my demo app and give me a hint. Or is everthing fine with the code and the algorithm doesn't fit my game so well??


Global mh:Int
Const DEPTH:Int = 4

Graphics 1024, 768
SetBlend(ALPHABLEND)

Type BoardNode
	Const RED:Int = -1
	Const BLUE:Int = 1
	
	Global nodes:TList
	
	Field grid:Int[8,8]
	Field childs:TList
	Field player:Int = -1
	Field renderChilds:Byte = False
	
	Method CreateNewNode:BoardNode()
		Local b:BoardNode = New BoardNode
		For Local x:Int = 0 To 7
			For Local y:Int = 0 To 7
				b.grid[x,y] = grid[x,y]
				b.player = -player
			Next
		Next
		Return b
	End Method
	
	Method InitGrid()
		grid = New Int[8,8]
		For Local x:Int = 0 To 7
			For Local y:Int = 0 To 7
				grid[x,y] = 0
			Next
		Next
		grid[3,3] = RED
		grid[4,3] = BLUE
		grid[3,4] = BLUE
		grid[4,4] = RED
	End Method
	
	Method RenderNode(offX:Int, offY:Int)
		If (w = 0) Then w = GraphicsWidth()
		SetColor(255,255,255)
		SetAlpha(0.3)
		DrawRect(offX, offY, 32, 32)
		SetAlpha(1)
		For Local x:Int = 0 To 7
			For Local y:Int = 0 To 7
				If (grid[x,y] = -1)
					SetColor(255,0,0)
					DrawRect(offX + x*4, offY + y*4, 4, 4)
				Else If grid[x,y] = 1
					SetColor(0,0,255)
					DrawRect(offX + x*4, offY + y*4, 4, 4)
				End If
			Next

			SetColor(0,255,0)
			SetAlpha(0.2)
			Local s:String = alpha+"/"+GetScore()
			DrawText(s, offX + 7, offY + 20)
			SetAlpha(1)
		Next
		SetColor(255,255,255)
				
		If (MouseX() > offX And MouseY() > offY And MouseX() < offx+32 And MouseY() < offY+32) 
			If mh Then renderChilds = Not renderChilds
			If KeyDown(KEY_Q)
				rootNode = Self
				rootNode.MiniMax(DEPTH)
			End If
		End If
		
		If (renderChilds And childs)
			Local ox:Int = offX - (CountList(childs)/2 * 40)
			For Local n:BoardNode = EachIn childs
				DrawLine(offX + 20, offY + 32, ox + 20, offY + 40)
				n.RenderNode(ox, offY + 40)
				ox :+ 40
			Next
		End If
		
	End Method
	
	Method GetScore:Int()
		'some simple heuristics
		
		Local score:Int = 0
		Local c1:Int = 0, c2:Int = 0
		For Local x:Int = 0 To 7
			For Local y:Int = 0 To 7
				If (grid[x,y] = -1) Then c1 :+ 1
				If (grid[x,y] = 1) Then c2 :+ 1
				score :+ grid[x,y]
			Next
		Next
		
		' a player has won
		If (c1 = 0) Then Return 1000
		If (c2 = 0) Then Return -1000
		
		'check for neighboring tiles (this is better then sepearted tiles)
'		For x:Int = 0 To 6
'			For y:Int = 0 To 6
'				If (grid[x,y] = grid[x+1,y]) Then score :+ grid[x,y]
'				If (grid[x,y] = grid[x, y+1]) Then score :+ grid[x,y]
'			Next
'		Next
		
		For x:Int = 0 To 6
			For y:Int = 0 To 6
				Local c:Int = 0
				c :+ grid[x,y]
				c :+ grid[x+1,y]
				c :+ grid[x,y+1]
				c :+ grid[x+1,y+1]
				If (c = 3) Then score :- 1
				If (c = -3) Then score :+ 1
			Next
		Next
		
		
		Return score
	End Method
	
	Method SetIfFieldNotEmpty:Byte(x:Int, y:Int, player:Int)
		If (x > 0 And y > 0 And x < 8 And y < 8 And grid[x,y] = 0)
			grid[x,y] = player
			Return True
		End If
		Return False
	End Method
	
	Method CalculateChilds()
		childs = CreateList()
		Local b:BoardNode
		For Local x:Int = 0 To 7
			For Local y:Int = 0 To 7
				If grid[x,y] = player
					b = CreateNewNode()
					If b.SetIfFieldNotEmpty(x-1, y, player) Then ListAddLast(childs, b) ; b.RemoveMatches()

					b = CreateNewNode()
					If b.SetIfFieldNotEmpty(x+1, y, player) Then ListAddLast(childs, b) ; b.RemoveMatches()

					b = CreateNewNode()
					If b.SetIfFieldNotEmpty(x, y-1, player) Then ListAddLast(childs, b) ; b.RemoveMatches()

					b = CreateNewNode()
					If b.SetIfFieldNotEmpty(x, y+1, player) Then ListAddLast(childs, b) ; b.RemoveMatches()
				End If
			Next
		Next
		DebugLog CountList(childs) + " childs calculated"
	End Method
	
	Method RemoveMatches()
		For Local x:Int = 0 To 6
			For Local y:Int = 0 To 6
				If grid[x,y] <> 0 And grid[x,y] = grid[x+1,y] And grid[x,y] = grid[x,y+1] And grid[x,y] = grid[x+1,y+1]
					grid[x,y] = 0
					grid[x+1,y] = 0
					grid[x,y+1] = 0
					grid[x+1,y+1] = 0
				End If
			Next
		Next
	End Method
	
	Field alpha:Int

	Method MiniMax:BoardNode(depth:Int = 0)
		If (player = -1) Then alpha = -99999
		If (player = 1)  Then alpha =  99999
		
		If (depth = 0)
			alpha = GetScore()
			Return Self
		Else
			CalculateChilds()
			For Local node:BoardNode = EachIn childs
				node.MiniMax(depth - 1)
				node.alpha = GetScore()
				If (player = -1)
					If (node.alpha > alpha) Then alpha = node.alpha ; bestMove = node
				Else
					If (node.alpha < alpha) Then alpha = node.alpha ; bestMove = node
				End If
			Next
		End If
	End Method	
	
	Method GetBest:BoardNode()
		Local b:BoardNode
		If (player = -1) Then a =  99999
		If (player = 1)  Then a = -99999
		For Local node:BoardNode = EachIn childs
			If b = Null Then b = node
			If (player = -1 And node.GetScore() >= 1000) Then Return node
			If (player = 1 And node.GetScore() <= -1000) Then Return node
			If (player = 1 And node.alpha < a) Then b = node
			If (player = -1 And node.alpha > a) Then b = node
			If (node.alpha = b.alpha)
				If (player = 1 And node.GetScore() < b.GetScore()) Then b = node
				If (player = -1 And node.GetScore() > b.GetScore()) Then b = node
			End If
		Next
		Return b 
	End Method
	
	Method RenderNodeBig(offX:Int, offY:Int)
		If (w = 0) Then w = GraphicsWidth()
		SetColor(255,255,255)
		SetAlpha(0.3)
		DrawRect(offX, offY, 16*8, 16*8)
		SetAlpha(1)
		For Local x:Int = 0 To 7
			For Local y:Int = 0 To 7
				If (grid[x,y] = -1)
					SetColor(255,0,0)
					DrawRect(offX + x*16, offY + y*16, 16, 16)
				Else If grid[x,y] = 1
					SetColor(0,0,255)
					DrawRect(offX + x*16, offY + y*16, 16, 16)
				End If
			Next

			SetColor(0,255,0)
			SetAlpha(0.2)
			Local s:String = alpha+"/"+GetScore()
			DrawText(s, offX + 7, offY + 20)
			SetAlpha(1)
		Next
		SetColor(255,255,255)
	End Method
End Type

Global rootNode:BoardNode = New BoardNode
rootNode.InitGrid()
rootNode.MiniMax(DEPTH)

While (Not KeyDown(KEY_ESCAPE))
	Cls
	mh = MouseHit(1)
	rootNode.RenderNode(GraphicsWidth() / 2, 5)
	
	rootNode.RenderNodeBig(0,0)
	DrawText("CurrentNode", 0,0)

	rootNode.GetBest().RenderNodeBig(0,140)
	If (rootNode.player = -1)
		DrawText("Best Move (Player RED )", 0, 140)	
	Else
		DrawText("Best Move (Player BLUE )", 0, 140)	
	End If
	If (KeyHit(KEY_M)) Then rootNode = rootNode.GetBest() ; rootNode.MiniMax(DEPTH)
	
	If KeyDown(KEY_P)
		DebugStop
		rootNode.GetScore()
	End If
	
	Flip
Wend

Last edited 2011

maverick69

(Posted 2011) [#2]

Okay, I've fixed a few bugs in scoring the current board state node.

I also added, that if serveral "bestMoves" are available because of the same alpha value, the one with the best Score will be returned.

At first sight, it now seems to work quite good. I've updated the code above!