EDIT - Most recent version is here: http://twolivesleft.com/Codea/Talk/discussion/comment/7445#Comment_7445
I wanted to try to implement a MCTS (monte carlo tree search) function that could play Connect 4 and Mancala, which would highlight the flexibility of the technique.
MCTS is a simple type of probabilistic search. It can serve as an AI for games. It works by splitting the current board’s state off into several possibilities: one for each possible move the computer could make. Then it simulates a bunch of random games for each of the possibilities and records the percentage of times that the computer won. It then actually makes the move with the best probability.
I started off by implementing Connect4 with generality: it works for a variable number of rows, columns, and connections necessary to win (making it ConnectN, basically ). I then implemented the MCTS in main. After hunting down some stupid logic errors, both seem to work. I have not made Mancala yet.
Main
red = color(255, 0, 0, 255)
blue = color(0, 0, 255, 255)
black = color(0, 0, 0, 255)
white = color(255, 255, 255, 255)
gray = color(127, 127, 127, 255)
function setup()
-- number of playouts is EXPONENTIAL. therefor: 0 -> 1, 1 -> 10, 2 -> 100, 3 -> 1 000, 4 -> 10 000.
-- keep in mind the time delay is proportional to the number of playouts
parameter("Playouts", 0, 4, 2.5)
-- rows, columns, (player starts = 0, ai starts = 1), number of connections to win
board = ConnectFour(4, 4, 0, 3)
strokeWidth(5)
end
function draw()
playouts = math.floor(10^Playouts)
background(40, 40, 50)
if board.turn == board.ai then
board:mcts()
end
board:draw()
if gameOver ~= nil then return end
gameOver = board:gameOver()
if gameOver == board.ai then
print("ai wins!")
return
elseif gameOver == board.player then
print("player wins!")
return
end
end
--allows the human player to play.
function touched(t)
if board:gameOver() ~= nil then
print("The game is over, you can no longer play.")
return
end
if t.state == ENDED and board.turn == board.player then
print("move acknowledged. please wait...")
board:touched(t)
end
end
function mcts()
possibleMoves = {}
searchResults = {}
local count = 0
-- determine the number of possible moves, and create arrays which hold each valid move,
-- and probability of winning by playing that move
for i = 1, board.numberOfColumns do
if board:validMove(i) == true then
count = count + 1
table.insert(possibleMoves, count, i)
table.insert(searchResults, count, 0)
end
end
print("number of possible moves is "..count)
if count == 0 then return end
-- creates a copy of the board. this single copy will run all of the playouts.
local temp = ConnectFour(board.numberOfRows, board.numberOfColumns, board.turn, board.goal)
for i = 1, count do
local sum = 0
for j = 1, playouts do
-- resets the board, by copying the original.
temp:copy(board)
temp:move(possibleMoves[i])
local playoutResult = playout(temp)
sum = sum + playoutResult
end
sum = sum / playouts
searchResults[i] = sum
print("probability for move "..possibleMoves[i].." is "..sum)
end
-- we should want to maximize the search result
bestResult = -99
bestIndex = -99
for i,r in pairs(searchResults) do
if bestResult < r then
bestResult = r
bestIndex = i
end
end
print("bestResult is "..bestResult)
print("bestIndex is "..bestIndex)
print("bestMove is "..possibleMoves[bestIndex])
board:move(possibleMoves[bestIndex])
end
-- simulates a game using random moves. wins (for the ai) return 1, losses 0, draws 0.5
-- **this code is the performance bottleneck**
function playout(b)
local result = b:gameOver()
while (result == nil) do
moves = b:numberOfMoves()
if moves == 0 then
return 0.5
end
b:randomMove( moves )
result = b:gameOver()
end
return result
end
board:move(possibleMoves[bestIndex])
end
– simulates a game using random moves. wins (for the ai) return 1, losses 0, draws 0.5
– this code is the performance bottleneck
function playout(b)