# MCTS, one AI playing 3 games!

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

ConnectFour()

``````ConnectFour = class()

function ConnectFour:init(rows, cols, turn, goal)
self.empty = -1
self.player = 0
self.ai = 1
self.tie = 2

self.moveHistory = {} -- not implemented yet

self.turn = turn
self.numMoves = cols

self.columns = {}
self.numberOfRows = rows
self.numberOfColumns = cols
self.goal = goal

for i = 1, self.numberOfColumns do
local temp = {}
for j = 1, self.numberOfRows do
table.insert(temp, j, self.empty)
end
table.insert(self.columns, i, temp)
end
end

-- used in the mcts() to theorize about safely create copies of the 'real' board.
-- this is based the instance of the real board, and is called by 'fake' boards created
-- by the mcts() search.
function ConnectFour:copy(original)
for i = 1, self.numberOfColumns do
for j = 1, self.numberOfRows do
self.columns[i][j] = original.columns[i][j]
end
end

self.numMoves = original.numMoves
self.turn = original.turn
end

function ConnectFour:draw()
local dx = WIDTH/(self.numberOfColumns)
local dy = HEIGHT/(self.numberOfRows)
ellipseMode(CORNER)

for i,col in pairs(self.columns) do
pushMatrix()
for j,disc in pairs(col) do
if disc == self.player then
fill(red)
elseif disc == self.ai then
fill(blue)
else
fill(gray)
end
ellipse(0,0,math.min(dx, dy))
translate(0, dy)
end
popMatrix()
translate(dx, 0)
end
end

-- returns true or false
function ConnectFour:validMove(col)
if self.columns[col][self.numberOfRows] == self.empty then
return true
else
return false
end
end

-- implemented as a function for historical reasons.
-- might remove this after i implement Mancala.
function ConnectFour:numberOfMoves()
return self.numMoves
end

-- do not pass this function 0.
-- this function is passed the knowledge that n possible moves exist.
-- it will then pick an integer m = [0, n)
-- it will go through each column, and play the m'th valid column
function ConnectFour:randomMove(numberOfPossibleMoves)
local myMove = math.random(numberOfPossibleMoves)
for i = 1, self.numberOfColumns do
if self.columns[i][self.numberOfRows] == self.empty then
myMove = myMove - 1
if myMove == 0 then
self:move(i)
end
end
end
end

function ConnectFour:changeTurn()
if self.turn == self.player then self.turn = self.ai
else self.turn = self.player end
end

--will add an appropriate colored token to the selected column
function ConnectFour:move(selection)
local done = false
for i,disc in pairs(self.columns[selection]) do
if done == false and disc == self.empty then
self.columns[selection][i] = self.turn
done = true
if i == self.numberOfRows then
-- Keeping track of the number of valid moves as they change is
-- better than recalculating it all the time.
self.numMoves = self.numMoves - 1
end
end
end
self:changeTurn()
end

-- allows the human to play! called from main:touched()
function ConnectFour:touched(t)
local selection = t.x/(WIDTH/self.numberOfColumns)
selection = math.ceil(selection)
if self.validMove(selection) == false then
print("That is not a valid move.")
return
end
self:move(selection)
end

-- returns nil if no winner, 0 (self.player) if the player wins, and 1 (self.ai) if the ai wins.
function ConnectFour:gameOver()
-- this variable is intentionally misspelled because during debugging I
-- made sure it was not interfering with another variable of the same name.
local daWinner = nil
--checks for vertical wins
for i = 1, self.numberOfColumns do
self:resetChain()
for j = 1, self.numberOfRows do
daWinner = self:countChain(i, j)
if daWinner ~= nil then return daWinner end
end
end

--checks for horizontal wins
for j = 1, self.numberOfRows do
self:resetChain()
for i = 1, self.numberOfColumns do
local daWinner = self:countChain(i, j)
if daWinner ~= nil then return daWinner end
end
end

--diagonals are tricky. they end up checking some empty space, but because
--of how things are set up, it doesnt break anything. this is possible because the
--function countChain() returns nil  when you try to access an array element that
--doesnt exist.
--i COULD make the next two loops prettier, though.

--up and to the right (slope of 1)
for i = (-self.numberOfRows + self.goal), (self.numberOfColumns - self.goal + 1) do
self:resetChain()
for j = 1, self.numberOfRows do
daWinner = self:countChain(i+j, j)
if daWinner ~= nil then return daWinner end
end
end

--up and to the left (slope of -1)
for i = (self.numberOfRows - self.goal), (self.numberOfColumns + self.goal + 1) do
self:resetChain()
for j = 1, self.numberOfRows do
daWinner = self:countChain(i-j, j)
if daWinner ~= nil then return daWinner end
end
end
return nil
end

-- this function used exclusively in gameOver()
-- counts number of consecutive same-color discs
function ConnectFour:countChain(i, j)
if i < 1 or self.numberOfColumns < i then return nil end
if self.type ~= self.columns[i][j] then
self.type = self.columns[i][j]
self.count = 0
end
if self.type ~= self.empty and self.type == self.columns[i][j] then
self.count = self.count + 1
if self.count == self.goal then
return self.type
end
end
return nil
end

-- this function used exclusively in gameOver()
-- resets the count used in countChain()
function ConnectFour:resetChain()
self.count = 0
self.type = self.empty
end
``````

This post used to contain my asking for help. I figured it out, and instead reserve this space for future code-posting.

Thank you SciQuest for posting this!

Thanks! Ive enjoyed working on it. Its playable, but its not even close to being done. In fact, I just made a simple change (max search depth) that greatly increases the AI’s time-performance, while appearing to simultaneously increase its play-strength.

Though I have obsoleted the original code, I’ve decided to leave it up, mostly for my own reference.

Contained below is the current iteration of my code. It works much better for Connect Four. Mancala works with the AI off. With the AI on, it sees every move as equally good and thus plays poorly. To make matters worse, the code isn’t even pretty!

Ill fix this, but not soon. Life is about to get interesting again.

Its my long term goal to have the code work with any normal form two player game, as long as that code implements a few basic functions. I’d really love it if I could get my code clean enough so that it was one of the default examples! (I have a ways to go)

The difficulty slider means that there is 10^x playouts per move made. Calculating a response to the first move Connect4, on a standard 7x6 board, Difficulty 4, unlimited search depth, takes ~200 seconds to run on my iPad. Difficult 3, unlimited depth, takes ~20 seconds. Difficulty 3, depth 20 takes ~16 seconds. Difficulty 3, depth 10 takes ~11 seconds. Difficulty 2.5, depth 10 takes <5 seconds. All settings returned the same move!

You may want to decrease the difficulty, and increase the depth for the first few moves (since noone is winning the game in a few number of moves). However, unlimited search depth is kind of overkill: it treats each playout win equally favorably, regardless of its depth in the search tree. The sweet spot for standard connect4 appears to be ~2.5 difficulty, any lower than that and the AI seems to make stupid moves with some regularity.

``````--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 setupParams()
iparameter("Game", 0, 2)
iparameter("AIonline", 0, 1)
iparameter("AIstarts", 0, 1)
parameter("Difficulty", 0, 4)
iparameter("MaxSearchDepth", 0, 20)

end

function saveParams()
saveProjectData("game", Game)
saveProjectData("aiOnline", AIonline)
saveProjectData("aiStarts", AIstarts)
saveProjectData("difficulty", Difficulty)
saveProjectData("maxSearchDepth", MaxSearchDepth)
end

function setup()
setupParams()
strokeWidth(5)
prevGame = 0
end

function startGame()
clearOutput()
print("Game 1: Connect")
print("Game 2: Mancala")
if Game == 1 then
ConnectFour:setupParams()
board = ConnectFour()
sim = ConnectFour()
elseif Game == 2 then
Mancala:setupParams()
board = Mancala()
sim = Mancala()
end
end

function draw()
background(40, 40, 50)
saveParams()

if Game ~= prevGame then
clearParameters()
clearOutput()
setupParams()
startGame()
prevGame = Game
end

if board==nil then return end
board:saveParams()
board:draw()

if fin == true then return end
if board.gameWon == board.ai then
print("ai wins!")
fin = true
return
elseif board.gameWon == board.player then
fin = true
print("player wins!")
return
end

if board.turn == board.ai and AIonline == 1 then
mcts()
end
end

function touched(t)
if t.state == ENDED and board.gameWon == nil then
board:touched(t)
end
end

function mcts()
local playouts = math.floor(10^Difficulty)
possibleMoves = {}
searchResults = {}
local count = 0
interval = board:possibleMovesInterval()
for i = interval.x, interval.y 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
for i = 1, count do
local sum = 0
for j = 1, playouts do
sim:copy(board)
sim:move(possibleMoves[i])
local playoutResult = playout(sim)
sum = sum + playoutResult
end
sum = sum / playouts
searchResults[i] = sum
print("probability for move "..possibleMoves[i].." is "..sum)
end
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("bestMove is "..possibleMoves[bestIndex])
if bestIndex == -99 then
print("oops! mcts failed? (thats not good)")
else
board:move(possibleMoves[bestIndex])
end
end

function playout(b)
local result = b:gameOver()
local searchDepth = 0
while (result == nil) do
local movesLeft = b:numberOfMoves()
if MaxSearchDepth == 0 then searchDepth = -99 end
if movesLeft == 0 or MaxSearchDepth <= searchDepth then
return 0.5
end
b:randomMove( movesLeft )
searchDepth = searchDepth + 1
result = b:gameOver()
end
return result
end

function flipTurn(b)
if b.turn == b.player then
b.turn = b.ai
else
b.turn = b.player
end
end
``````
``````ConnectFour = class()

function ConnectFour:setupParams()
iparameter("ConnectColumns", 1, 7)
iparameter("ConnectRows", 1, 7)
iparameter("ConnectChain", 1, 7)

end

function ConnectFour:saveParams()
saveProjectData("connectCol", ConnectColumns)
saveProjectData("connectRows", ConnectRows)
saveProjectData("connectChain", ConnectChain)
end

function ConnectFour:init()
self.empty = -1
self.player = 0
self.ai = 1

self.gameWon = nil

self.turn = AIstarts
self.numMoves = ConnectColumns

self.columns = {}
self.numberOfRows = ConnectRows
self.numberOfColumns = ConnectColumns
self.goal = ConnectChain

for i = 1, self.numberOfColumns do
local temp = {}
for j = 1, self.numberOfRows do
table.insert(temp, j, self.empty)
end
table.insert(self.columns, i, temp)
end
end

function ConnectFour:copy(original)
for i = 1, self.numberOfColumns do
for j = 1, self.numberOfRows do
self.columns[i][j] = original.columns[i][j]
end
end

self.numMoves = original.numMoves
self.turn = original.turn
self.gameWon = original.gameWon
end

function ConnectFour:draw()
local dx = WIDTH/(self.numberOfColumns)
local dy = HEIGHT/(self.numberOfRows)
ellipseMode(CORNER)

for i,col in pairs(self.columns) do
pushMatrix()
for j,disc in pairs(col) do
if disc == self.player then
fill(red)
elseif disc == self.ai then
fill(blue)
else
fill(gray)
end
ellipse(0,0,math.min(dx, dy))
translate(0, dy)
end
popMatrix()
translate(dx, 0)
end
end

function ConnectFour:validMove(col)
if self.columns[col][self.numberOfRows] == self.empty then
return true
else
return false
end
end

function ConnectFour:numberOfMoves()
return self.numMoves
end

-- do not pass this func 0.
function ConnectFour:randomMove(numberOfPossibleMoves)
local myMove = math.random(numberOfPossibleMoves)
for i = 1, self.numberOfColumns do
if self.columns[i][self.numberOfRows] == self.empty then
myMove = myMove - 1
if myMove == 0 then
self:move(i)
return
end
end
end
end

function ConnectFour:changeTurn()
if self.turn == self.player then self.turn = self.ai
else self.turn = self.player end
end

function ConnectFour:move(selection)
local done = false
for i,disc in pairs(self.columns[selection]) do
if done == false and disc == self.empty then
self.columns[selection][i] = self.turn
self:updateWinner(selection, i)
done = true
if i == self.numberOfRows then
self.numMoves = self.numMoves - 1
end
end
end
flipTurn(self)
end

function ConnectFour:touched(t)
local selection = t.x/(WIDTH/self.numberOfColumns)
selection = math.ceil(selection)
self:move(selection)
end

function ConnectFour:updateWinner(x, y)
if self.gameWon ~= nil then return end

local winner = nil
local goal = self.goal - 1

for i = 1, 4 do
self:resetChain()
for j = -goal, goal do
if i==1 then winner = self:countChain(x+j, y)
elseif i==2 then winner = self:countChain(x, y+j)
elseif i==3 then winner = self:countChain(x+j, y+j)
elseif i==4 then winner = self:countChain(x+j, y-j) end
if winner ~= nil then
self.gameWon = winner
return
end
end
end
end

function ConnectFour:gameOver()
return self.gameWon
end

function ConnectFour:countChain(i, j)
if i < 1 or self.numberOfColumns < i then return nil end
if j < 1 or self.numberOfRows < j then return nil end
if self.type ~= self.columns[i][j] then
self.type = self.columns[i][j]
self.count = 0
end
if self.type ~= self.empty and self.type == self.columns[i][j] then
self.count = self.count + 1
if self.count == self.goal then
return self.type
end
end
return nil
end

function ConnectFour:resetChain()
self.count = 0
self.type = self.empty
end

function ConnectFour:possibleMovesInterval()
return vec2(1,self.numberOfColumns)
end
``````
``````Mancala = class()

function Mancala:setupParams()
iparameter("NumberOfBins", 1, 9)
iparameter("StonesPerBin", 1, 7)

end

function Mancala:saveParams()
saveProjectData("numberOfBins", NumberOfBins)
saveProjectData("stonesPerBin", StonesPerBin)
end

function Mancala:init()
self.player = 0
self.ai = 1
self.turn = AIstarts

self.numBins = NumberOfBins
self.startingStones = StonesPerBin

self.bins = {}
self.playerMancala = self.numBins + 1
self.aiMancala = 2 * self.playerMancala
for i = 1, 2*self.numBins+2 do
table.insert(self.bins, i, self.startingStones)
end
self.bins[self.playerMancala] = 0
self.bins[self.aiMancala] = 0
end

function Mancala:copy(original)
self.turn = original.turn
self.gameWon = original.gameWon
for i = 1, original.aiMancala do
self.bins[i] = original.bins[i]
end
end

function Mancala:draw()
local dx = WIDTH/self.numBins
local dy = 100
ellipseMode(CORNER)
pushMatrix()
fontSize(36)
for i = 0, self.numBins-1 do
fill(red)
ellipse(dx*i,0,dx)
fill(blue)
ellipse(WIDTH-dx*(i+1), HEIGHT - dx, dx)
fill(white)
text(self.bins[1+i], dx*i+dx/2, dx/2)
text(self.bins[1+i+self.playerMancala], WIDTH-dx*(i+1)+dx/2, HEIGHT -dx/2)

end
popMatrix()
fill(blue)
ellipse(0, (HEIGHT -dx)/2, dx)
fill(red)
ellipse(WIDTH -dx, (HEIGHT -dx)/2, dx)
fill(white)
text(self.bins[self.aiMancala], dx/2, HEIGHT/2)
text(self.bins[self.playerMancala], WIDTH -dx/2, HEIGHT/2)
if self.turn == self.ai then
fill(blue)
str = "Blue's Move"
else
fill(red)
str = "Red's Move"
end
text(str, WIDTH/2, HEIGHT/2)
end

function Mancala:touched(t)
local selection = t.x/(WIDTH/self.numBins)
selection = math.ceil(selection)
if self.turn == self.ai then
selection = self.numBins - selection + 1 +self.playerMancala
end

self:move(selection)
end

function Mancala:move(index)
local stones = self.bins[index]
self.bins[index] = 0

for i = 1, 99 do
if stones == 0 then
if self.turn == self.ai and index ~= self.aiMancala then
flipTurn(self)
elseif self.turn == self.player and index ~= self.playerMancala then
flipTurn(self)
end
return
end

if index < self.aiMancala then
index = index + 1
else
index = 1
end

local sowHere = true
if index == self.aiMancala and self.turn == self.player then
sowHere = false
elseif index == self.playerMancala and self.turn == self.ai then
sowHere = false
end

if sowHere == true then
self.bins[index] = self.bins[index] + 1
stones = stones - 1
end
end
end

function Mancala:validMove (index)
if self.bins[index] == 0 then
return false
end
return true
end

function Mancala:gameOver()
local done = false
if self:numberOfMoves() == 0 then done = true end
flipTurn(self)
if self:numberOfMoves() == 0 then done = true end
flipTurn(self)
if done == true then
if self.bins[self.playerMancala] < self.bins[self.aiMancala] then
return self.ai
elseif self.bins[self.aiMancala] < self.bins[self.playerMancala] then
return self.player
else
return 0.5
end
end
return nil
end

function Mancala:possibleMovesInterval()
if self.turn == self.ai then
return vec2(self.playerMancala+1, self.aiMancala-1)
end
return vec2(1, self.numBins)
end

function Mancala:numberOfMoves()
local interval = self:possibleMovesInterval()
local count = 0
for i = interval.x, interval.y do
if self:validMove(i) == true then
count = count + 1
end
end
return count
end

function Mancala:randomMove(numberOfPossibleMoves)
local myMove = math.random(numberOfPossibleMoves)
local offset = 1
if self.turn == self.ai then offset = 1 + self.playerMancala end
for i = 1, self.numBins do
if self.bins[offset+i] ~= 0 then
myMove = myMove - 1
if myMove == 0 then
self:move(offset+i)
return
end
end
end
end
``````

New version! Plays ConnectFour, Mancala (Kalah), and TicTacToe (Noughts and Crosses) with good strength. Main and Mancala are documented the best, start there if you want to understand the code.

Here are the files:

Mancala - http://pastebin.com/CRiE768Z

ConnectFour - http://pastebin.com/unskVrEf

TicTacToe - http://pastebin.com/TyM7v6xe

What game should I implement next?

``````What game should I implement next?
``````

Very few people have heard of it but this one fascinates me:

http://boardgamegeek.com/boardgame/1529/ramses

That could be fun! I have a place in my heart for Egypt-related things! (hence the Mancala, actually)

Also, thank you for suggesting something inside my skill level I mean, not Go!

I love Reversi AKA Othello. One of my favorite board games. Also Chinease checkers. Love it by the way! Great stuff!

Second vote for Reversi, one of my favorites too.

Windows XP used to have an internet version of it and I played it a lot. I was very sad when they removed it in Windows 7, and installed a virtual windows XP just so I could keep playing it. It take many gigs of disk space! I actually really like the anonymous nature of the windows internet games, where you can just log in and play without a profile and a track record to worry about. I don’t know of any game sites like that for reversi (or any other game really).

I did a little UI for reversi in codea - had always wanted to try coding an AI as well so took a crack in codea but it sucked big time because it was slow. Wondering if your technique would do better.

Do you simulate the game all the way to the end or do you stop in the middle and use an evaluation function?

Here’s mine by the way:

http://ruilov.posterous.com/reversi-greedy-ai-68459

edit: gah just remembered that codea files don’t exist anymore. I’ll post the code a little later.

Othello will definitely make an appearance before Ramses or Chinese Checkers, at it will be far simpler to implement.

It can be set to simulate either entire games or simply out to a horizon. I intend to give it a hardcap on the search time as my next improvement. Currently it performs up to 10,000 playouts per each potential move, in order. This would have to change to performing one playout per potential move, up to several thousand times. Ultimately not too difficult.

An evaluation heuristic for Othello would be interesting. A boxcar average I think would work best, since the ratio of stones between sides can swing by a large margin in just 1 ply.

Chinese Checkers would involve (at least) multistep planning inside of a single turn (moves would be represented as tuples instead of scalars), which would involve refactoring the mcts code (which needs to happen anyways). Also, Chinese Checkers can support more than two players. At the moment I am focusing on two player games.

Ramses is definitely more complicated, since it involves pathfinding on a directed graph, and each turn would be represented as a 4-tuple. That said, good pathfinding implementations is part of what I need to come up with to finish my second class in Codea.

Im still confused about some of the details of Ramses’ rules. Do pieces have to move their maximum possible amount? @Blanchot Could you, in your own words, describe the rules for me?

``````Im still confused about some of the details of Ramses' rules. Do pieces have to move their maximum possible amount? @Blanchot Could you, in your own words, describe the rules for me?
``````

Oh dear it has been quite a while since I played (it’s not an easy game and likewise it’s not easy to find a ‘casual’ opponent…) but as I remember each pawn you move (each turn you can choose which two you want to move… as long as one is your own and one belongs to your opponent) has to move the maximum number of moves. The kicker of course is that number is determined by the pawn’s current position.

It is really a brain-burning thinker’s game and I’m glad you are considering it. I’m curious how easy it would be to implement an AI for it.

Did you see both sets of rules on BGG?

http://boardgamegeek.com/collection/items/boardgame/1529?comment=1

Yeah I found that, I just misread something last night. I understand the rules, though I can’t quite ‘see’ the gameplay yet. Ill print out a board and face off against myself… its definitely in my sights now.

The pieces that start in the oblong spots, can they exit to the left, or do they have to go to the middle?

Fixed a stupid bug that caused the tic tac toe random move function to break, and thus caused pathological behavior in the AI.

@Blanchot let tag you so hopefully you can answer my question:

The Ramses rules are unclear. Do the pieces that start on squares 5(10) and 22(10) exit to the middle or out the side?

@SciQuest… as I mentioned before it’s been a while since I played… but I interpret the following rule…

“When one wants to move a pawn out of an oblong square, it can only go to two squares: the square beside the oblong (4 or 21) or the square beside the pawn (10 to 17).”

… to mean that the pawn which starts on square 5 can only exit via square 4 or 10. Likewise, the pawn which starts on square 22 can only exit via square 21 or 10.

Hope this helps. Do you think you will be able to implement an AI for this intriguing game?

Edit: I just noticed (what I assume to be) the thread you started about programming AI’s on BGG. In it you mentioned you were working on an AI for Ramses and asked for other suggestions for ‘simple but deep games’. If so may I also suggest:

Qyshinsu: Mystery of the Way

http://boardgamegeek.com/boardgame/36616/qyshinsu-mystery-of-the-way

Ive decided to use a memoization technique to make valid pathfinding cheaper. Itll be my first time implementing such a thing, and Ive studied pathfinding in some depth but never implemented it. So, dont take it for too much, but, I think so, yes.

I made a thread on GameDev.net that explains what Im trying to do, and some ugly pseudocode showing how I think I might do it.

http://www.gamedev.net/topic/622725-finding-all-nodes-at-a-specific-depth/

My BGG thread is a little frustrating. They clearly know at least something about the field, and yet what they say runs counter to not only my gut but every modern textbook Ive read. That thepackrat fellow, the only one still responding, is bordering on being condescending, too.

I was more so looking for suggestions for games to build (since I view that community as likely to be way more knowledge on that subject than my other resources), but many took it as ‘tell me how to code’ which is… when I want help with that, Ill ask.

That might be it @Blancot but because in the rules that how you exit those squares depends on how you enter them… well, maybe Ill just add two more nodes, each with no incoming edges, for the starting position so that in case it IS either way that one time, then I am prepared. The brings me up to 40 nodes for a 22 square game. XP

Qyshinsu is definitely doable. Should be much easier than Ramses.

Btw, Im taking an intro to electrical engineering class and opted for my class project to be a programming-centric one. I’m doing a study of pathological behavior of MCTS in Connect-4, using the game I made in Codea.