MCTS, one AI playing 3 games!

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

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. :slight_smile: 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)
    
    Game = readProjectData("game", 0)
    AIonline = readProjectData("aiOnline", 1)
    AIstarts = readProjectData("aiStarts", 0)
    Difficulty = readProjectData("difficulty", 2)
    MaxSearchDepth = readProjectData("maxSearchDepth", 6)
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
        print("loading Connect")
        ConnectFour:setupParams()
        board = ConnectFour()
        sim = ConnectFour()
    elseif Game == 2 then
        print("loading Mancala")
        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
        print("move acknowledged. please wait...")
        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)

    ConnectColumns = readProjectData("connectCol", 4)
    ConnectRows = readProjectData("connectRows", 4)
    ConnectChain = readProjectData("connectChain", 3)
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)

    NumberOfBins = readProjectData("numberOfBins", 6)
    StonesPerBin = readProjectData("stonesPerBin", 4)
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:

Main - http://pastebin.com/6Gj2iiVu

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 :stuck_out_tongue: 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://files.boardgamegeek.com/file/download/2dw4d2iva/Ramses.PDF?
http://gamecabinet.com/rules/Ramses.html

Edit… adding a link to player comments:

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.