Problem with Boardgame AI (Minimax Algorithm)
BlitzMax Forums/BlitzMax Programming/Problem with Boardgame AI (Minimax Algorithm)
| ||
| 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 |
| ||
| 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! |
   |