1 files changed, 141 insertions, 0 deletions
diff --git a/test/tictactoe/tictactoe_player.lua b/test/tictactoe/tictactoe_player.lua
new file mode 100644
index 0000000..4c9d56b
--- /dev/null
+++ b/test/tictactoe/tictactoe_player.lua
@@ -0,0 +1,141 @@
+local insert = table.insert
+local ipairs = ipairs
+local remove = table.remove
+local unpack = unpack
+
+require 'curses'
+local addch  = curses.addch
+local getch  = curses.getch
+
+module 'tictactoe_player'
+
+local function get_move_human(self, board)
+    -- first find the first empty tile on the board, so that we start the
+    -- cursor off in an empty tile
+    local y, x
+    for row in ipairs(board.board) do
+        for col in ipairs(board.board[row]) do
+            if board:at(row, col) == nil then
+                y, x = row, col
+                break
+            end
+        end
+        if y or x then break end
+    end
+
+    while true do
+        local c
+        -- draw the character we are about to put down under the cursor only if
+        -- the tile under the cursor is empty
+        if board:at(y, x) == nil then
+            addch(board:position(y, x), self.symbol:upper())
+            c = getch(board:position(y, x))
+            addch(board:position(y, x), " ")
+        else
+            c = getch(board:position(y, x))
+        end
+
+            if c == "left"  or c == "h" then
+            x = (x - 2) % 3 + 1
+        elseif c == "right" or c == "l" then
+            x = x % 3 + 1
+        elseif c == "up"    or c == "k" then
+            y = (y - 2) % 3 + 1
+        elseif c == "down"  or c == "j" then
+            y = y % 3 + 1
+        elseif c == "enter" or c == " " then
+            -- don't return illegal moves
+            if board:at(y, x) == nil then
+                return y, x
+            end
+        end
+    end
+end
+
+-- recursive helper function for the computer's move calculation
+-- it returns true if the player can certainly win from the given board
+-- position and the given turn
+-- it returns false if the player will lose against a perfect opponent
+-- it returns nil if the player can force a draw, but cannot win
+-- the second return value is a list of positions that correspond to the move
+-- predictions for the rest of the game
+local function find_move(self, board, turn)
+    local tiles = board:empty_tiles()
+    -- hardcode starting move, since there's only one best move anyway, and
+    -- this speeds things up quite a bit
+    if #tiles == 9 then
+        return nil, {{3, 3}}
+    end
+
+    local winner = board:winner()
+    if winner then
+        if winner == self.symbol then return true, {}
+        else return false
+        end
+    elseif #tiles == 0 then
+        return nil, {}
+    else
+        local next_turn
+        if turn == "x" then next_turn = "o" else next_turn = "x" end
+
+        local won, path, tie_path
+        for _, tile in ipairs(tiles) do
+            -- create a copy of the board with the next position to try
+            -- filled in, and see if there is a winning position
+            local copy = board:clone()
+            copy:mark(turn, unpack(tile))
+            won, path = find_move(self, copy, next_turn)
+
+            if self.symbol == turn then
+                -- if it's our turn and the move we just tried will certainly 
+                -- win, then return that move
+                if won == true then
+                    insert(path, tile)
+                    return true, path
+                end
+            else
+                -- if it's the opponent's turn and the opponent's move will
+                -- make us lose, then drop the rest of this branch
+                if won == false then return false end
+            end
+
+            -- keep track of if we found a path that will result in a tie,
+            -- since that is the second best result
+            if won == nil then
+                insert(path, tile)
+                tie_path = path
+            end
+        end
+
+        -- if we haven't yet returned with a winning path, then return with
+        -- a tie if possible
+        if tie_path then return nil, tie_path end
+
+        -- if we get here and it's our turn, that means that all possibilities
+        -- for our move will make us lose, so drop this branch
+        -- if we get here and it's the opponent's turn, that means that
+        -- all possibilities for the opponent's move will make us win, so just
+        -- return any path
+        if self.symbol == turn then return false
+        else return true, path
+        end
+    end
+end
+
+local function get_move_computer(self, board)
+    local win, path = find_move(self, board, self.symbol)
+    -- the next move is the end of the path that find_move returned
+    return unpack(remove(path))
+end
+
+function new(type, symbol)
+    local get_move
+    if type == "human" then
+        get_move = get_move_human
+    else
+        get_move = get_move_computer
+    end
+
+    -- we don't need an actual object, a table will do fine
+    return {get_move = get_move, symbol = symbol}
+end