MCTS-AI, Main

-- README / INTRODUCTION --
-- Welcome! Monte-Carlo Tree Search (MCTS) is a probabilistic technique for finding a
-- probably approximately correct solution to a generally intractable problem.
-- What that MEANS is that it is good at finding 'good enough' solutions to
-- problems that would else wise be a borderline impossible to solve (like AI!).
-- Monte-Carlo references a city known for its gambling, and tree search just
-- means that it is searching a tree data structure. (note, no actual explicit tree
-- data structure is in this program)

-- WHAT IT ACTUAL DOES (in layman's terms)
-- Here, MCTS is used as an AI. On the AI's turn, it will start running simulations.
-- It will create a list of moves it is capable of making, then make the first move
-- on a copy of the actual game board (this copy is called 'sim') and from there it
-- will play a random game, making random moves, and remember who won. It will do this
-- up to thousands of times per potential move. These random games are called playouts.
-- It will then calculate which move had the highest percentage of wins for the AI,
-- and assume that this is the best move to make, then make that move.

-- WHAT THE OPTIONS DO
-- Game: controls which game you are making. 0 is intended for instructions.
-- AIonline: turns the AI on & off. When it is off you can play against another human.
-- AIstarts: decides who starts, red (player) or blue (computer).
-- Difficulty: controls how many playouts are made per potential move.
-- -- It is an EXPONENTIAL scale! 10^n
-- -- This means it is entirely possible to CRASH CODEA by turning up the difficulty!!
-- MaxSearchDepth: number of ply deep in the search tree the playout will simulate.
-- -- If the playout ends before the search horizon, board:positionStrength() is
-- -- called and returns a rough estimate of how the game is going. Higher numbers
-- -- are better for the AI.
-- Timeout: planned, not implement. creates a hard-cap on the time-complexity of mcts().

-- IMPORTANT VARIABLES
-- board: the actual game board. an instance of one of many possible classes.
-- -- each of these classes (ConnectFour, etc) must implement certain functions.
-- -- specifically, those functions called by MCTS and playout. (amongst others)
-- sim: another instance of the same class as board. used for playouts.
-- player, ai: currently stored in each class individual. store values of 0 and 1.
-- -- these could/should be global variables though.

-- NOTE
-- parameters are saved so that they persist through resets. this could potentially
-- get you in trouble. (ie, AIstarts==1, Difficulty==4, MaxSearchDepth==0, Game~=0, etc)

-- END OF INTRODUCTION --

-- Just some colors, for convenience & consistency
 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)

-- For parameters common to all games
 function setupParams()
     iparameter("Game", 0, 3)
     iparameter("AIonline", 0, 1)
     iparameter("AIstarts", 0, 1)
     parameter("Difficulty", 0, 4)
     iparameter("MaxSearchDepth", 0, 20)

     -- reads persistent data.
     -- how i am keeping the parameters persistent is clunky.
     Game = readProjectData("game", 0)
     AIonline = readProjectData("aiOnline", 1)
     AIstarts = readProjectData("aiStarts", 0)
     Difficulty = readProjectData("difficulty", 2)
     MaxSearchDepth = readProjectData("maxSearchDepth", 6)
 end

-- invoked to save parameters common to all games
 function saveParams()
     saveProjectData("game", Game)
     saveProjectData("aiOnline", AIonline)
     saveProjectData("aiStarts", AIstarts)
     saveProjectData("difficulty", Difficulty)
     saveProjectData("maxSearchDepth", MaxSearchDepth)
 end

-- called once (and first) at start up.
 function setup()
     wait = true
     setupParams()
     strokeWidth(5)
     prevGame = 0
 end

-- updates the important global variables board and sim to reflect the
-- correct game. I dont like how this is handled either, as it violates
-- the 0-1-infinity rule.
 function startGame()
     clearOutput()
     -- print("Game 0: Tutorial")
     print("Game 1: Connect")
     print("Game 2: Mancala")
     print("Game 3: TicTacToe")
     if Game == 0 then
         -- display tutorial stuff.
         board = nil
         sim = nil
     elseif 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()
     elseif Game == 3 then
         print("loading TicTacToe")
         -- no params to set up
         board = TicTacToe()
         sim = TicTacToe()
     end
 end

-- the main game loop!
 function draw()
     background(40, 40, 50)
     saveParams()

     -- what to do if the game has changed
     if Game ~= prevGame then
         fin = false
         clearParameters()
         clearOutput()
         setupParams()
         startGame()
         prevGame = Game
     end

     -- this should only happen if game == 0
     if board==nil then return end

     -- yet again, i dont like this, but it works.
     -- i should theoretically at least make this check to see if
     -- a param has changed before saving it.
     board:saveParams()
     board:draw()

     -- this gets reset if the game changes.
     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

     -- the purpose of the wait variable is to add a 1 frame delay before calling MCTS.
     -- this allows the board to be rendered before calling the (potentially slow) AI
     if wait == true then
         wait = false
     elseif board.turn == board.ai and AIonline == 1 and board.gameWon == nil then
         mcts()
     end
 end

-- accepts player input!
 function touched(t)
     if t.state == ENDED and board:gameOver() == nil then
         print("move acknowledged. please wait...")
         -- all the heavy lifting is handled by each game individually
         board:touched(t)
         wait = true
     end
 end

-- where the magic happens! (aka, the AI)
-- this could be split into smaller functions, but i like it together.
 function mcts()
     -- initial setup and building list of all potential moves
     wait = true
     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

     -- if there are no possible moves, the game ends.
     print("number of possible moves is "..count)
     if count == 0 then
         fin = true
         return
     end

     -- runs the playouts for each potential move, stores results, and
     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

     -- we want to maximize the search result. 0=player, 1=ai
     -- actually, couldnt this stuff be done in the outer loop above? ...ill fix that.
     bestResult = -99
     bestIndex = -99
     for i,r in pairs(searchResults) do
         if bestResult < r then
             bestResult = r
             bestIndex = i
         end
     end

     -- actually make the move.
     print("bestResult is "..bestResult)
     print("bestMove is "..possibleMoves[bestIndex])
     if bestIndex == -99 then
         -- never had this get called. hopeful that means everything works!
         print("oops! mcts failed? (thats not good)")
     else
         board:move(possibleMoves[bestIndex])
     end
 end

-- simulates a random game!
-- **THIS IS THE PERFORMANCE BOTTLENECK**
-- AI's effective strength can increase with a more efficient playout.
 function playout(b)
     local result = b:gameOver()
     local searchDepth = 0
     while (result == nil) do
         local movesLeft = b:numberOfMoves()
         if movesLeft == 0 or MaxSearchDepth <= searchDepth and MaxSearchDepth ~= 0 then
             return b:positionStrength()
         end
         b:randomMove( movesLeft )
         searchDepth = searchDepth + 1
         result = b:gameOver()
     end
     return result
 end

-- individual boards can each call this function like: flipTurn(self)
 function flipTurn(b)
     if b.turn == b.player then
         b.turn = b.ai
     else
         b.turn = b.player
     end
 end

-- should return a random truth value. anyone know a better way to do this?
 function randBool()
     return math.random(2) == 1
 end