MCTS-AI, Mancala

Mancala = class()
-- This implements the sowing game called Kalah (Mancala in USA, see wikipedia).
-- I believe having first move is a 5.5 handicap on a 6 bin, 4 stone board.
-- (without this, first player always wins with perfect play)

-- the next two functions are self documenting.
 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

-- creates an instance of the Mancala board
 function Mancala:init()
     self.player = 0
     self.ai = 1
     self.turn = AIstarts
     selfgameWon = nil

     self.numBins = NumberOfBins
     self.startingStones = StonesPerBin

     -- the way i chose to represent this causes some ugly code later, but works.
     -- let me know if you have a better implementation!
     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

     self.totalStones = self.numBins * self.startingStones * 2
 end

-- copy function is used to update sim to reflect the board.
 function Mancala:copy(original)
     self.turn = original.turn
     for i = 1, original.aiMancala do
         self.bins[i] = original.bins[i]
     end
     self.gameWon = original.gameWon
 end

-- straight forward, if inelegant.
 function Mancala:draw()
     local dx = WIDTH/self.numBins
     local dy = 100
     ellipseMode(CORNER)
     pushMatrix()
     fontSize(36)
     -- specifically, this shouldve been two seperate loops.
     -- im slow to change working code though.
     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

-- note: no protection against making invalid moves! fix this.
 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

-- sows a bin according to the rules of the game.
 function Mancala:move(index)
     local stones = self.bins[index]
     self.bins[index] = 0

     -- while (true) should work too, but i prefer something that if it breaks,
     -- will still terminate. and, im slow to fix working code.
     for i = 1, self.totalStones do
         if stones == 0 then
             -- sowing complete. flip the turn, if conditions aren't met.
             -- then update the winner and jump out of the function.
             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
             self:updateWinner()
             return
         end

         -- wrap around to the start of the board
         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
     -- fairly sure this doesn't get called. oh well, it doesn't hurt to be here.
     self:updateWinner()
 end

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

-- basically just a Get function.
 function Mancala:gameOver()
     return self.gameWon
 end

-- should probably also check to see if either player has more than half the total...
-- but this works, and allows you to keep playing if you want.
 function Mancala:updateWinner()
     -- prevents winner from ever changing from who won first.
     if self.gameWon ~= nil then return end

     local done = false
     if self:numberOfMoves() == 0 then done = true end

     -- this dirty trick of swapping turn twice prevents rewriting code.
     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
             self.gameWon = self.ai
             return
         elseif self.bins[self.aiMancala] < self.bins[self.playerMancala] then
             self.gameWon = self.player
             return
         else
             self.gameWon = 0.5
             return
         end
     end
     return nil
 end

-- i was trying to make my code more modular. i think it ended up being uglier.
-- this is called early in mcts() and in self:numberOfMoves()
 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 = 0
     if self.turn == self.ai then offset = self.playerMancala end

     -- I CHEATED!! THIS ISN'T FULLY RANDOM!!
     -- to improve the strength of the playout i gave it some domain-specific
     -- tendencies (if not knowledge, per se). it has a chance of making certain
     -- moves that i consider 'no brainers', and a lower chance of making what i
     -- consider 'generally strong moves'. this seems to have massively increased
     -- its performance & strength, though!
     -- it does still spend time making random other moves, however, so it can
     -- still visit the entire search tree (eventually). also, if none of these
     -- conditions are met, it will fall-through to a random move.
     if randBool() then
         if self.bins[offset+self.numBins] ~= 0 then
             self:move(offset+self.numBins)
             return
         end
         if self.bins[offset+self.numBins-1] == 2 then
             self:move(offset+self.numBins-1)
             return
         end
         if 2 <= self.bins[offset+self.numBins-1] and randBool() then
             self:move(offset+self.numBins-1)
             return
         end
         if randBool() then
             for i = offset+self.numBins-2, offset+1, -1 do
                 if self.bins[i] == i then
                     self:move(i)
                     return
                 end
             end
         end
     end
     -- end "cheating"

     -- make an actually random move
     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

-- approximates the relative strength of each player's positions.
-- returns a weighted ratio. i should probably cap this at 0..1
-- (currently is -0.5 .. 1.5)
 function Mancala:positionStrength()
     return 0.5 + ((self.bins[self.aiMancala] - self.bins[self.playerMancala]) / self.totalStones)
 end