add my tictactoe game as another test

3 files changed, 393 insertions, 0 deletions

diff --git a/test/tictactoe/tictactoe.lua b/test/tictactoe/tictactoe.lua
new file mode 100644
index 0000000..dadbb2b
--- /dev/null
+++ b/test/tictactoe/tictactoe.lua
@@ -0,0 +1,97 @@
+local Board = require "tictactoe_board"
+local Player = require "tictactoe_player"
+require "curses"
+require "signal"
+
+-- deinitialize curses on exit, or when a signal is received, so we don't leave
+-- the terminal in a messed up state
+local function cleanup(sig)
+    curses.endwin()
+    if sig then
+        signal.signal(sig, "default")
+        signal.raise(sig)
+    end
+end
+
+local function get_player_types()
+    local player1, player2
+    io.write("Is player 1 a human? ");
+    local response = io.read()
+    if response:sub(1, 1):lower() == "y" then
+        player1 = "human"
+    else
+        player1 = "computer"
+    end
+
+    io.write("Is player 2 a human? ");
+    local response = io.read()
+    if response:sub(1, 1):lower() == "y" then
+        player2 = "human"
+    else
+        player2 = "computer"
+    end
+
+    return player1, player2
+end
+
+local function init_curses()
+    curses.initscr()
+    signal.signal("INT", cleanup)
+    signal.signal("TERM", cleanup)
+    curses.start_color()
+    curses.setup_term{nl = false, cbreak = true, echo = false, keypad = true}
+    for _, color in ipairs({"red", "blue", "green"}) do
+        curses.init_pair(color, color)
+    end
+end
+
+local function init_board(ymax, xmax)
+    local ymax, xmax = curses.getmaxyx()
+    local board_y, board_x = Board.size()
+    -- center the board horizontally, and place the board a little above center
+    -- vertically, so that the caption isn't too low
+    return Board.new(math.floor(ymax - board_y) / 2 - 1,
+                     math.floor(xmax - board_x) / 2)
+end
+
+local function main()
+    -- initialize the game
+    local player1, player2 = get_player_types()
+    init_curses()
+    board = init_board()
+    players = { x = Player.new(player1, "x"), o = Player.new(player2, "o") }
+
+    -- start the main loop
+    local turn = "x"
+    board:draw()
+    curses.refresh()
+    while true do
+        if #board:empty_tiles() == 0 then
+            board:caption("Tie!")
+            break
+        end
+
+        board:mark(turn, players[turn]:get_move(board))
+        board:draw()
+
+        local winner, winner_tiles = board:winner()
+        if winner then
+            board:mark_winner(winner, winner_tiles)
+            board:caption(winner:upper() .. " wins!")
+            break
+        end
+        if turn == "x" then turn = "o" else turn = "x" end
+    end
+end
+
+-- use pcall to catch lua errors, which we can't catch with our signal handlers
+-- (so that we can clean up curses if necessary)
+local success, err_msg = pcall(main)
+
+if success then
+    curses.getch()
+    cleanup()
+else
+    cleanup()
+    print(err_msg)
+end
diff --git a/test/tictactoe/tictactoe_board.lua b/test/tictactoe/tictactoe_board.lua
new file mode 100644
index 0000000..8962257
--- /dev/null
+++ b/test/tictactoe/tictactoe_board.lua
@@ -0,0 +1,155 @@
+local error    = error
+local insert   = table.insert
+local ipairs   = ipairs
+local setmetatable = setmetatable
+local type     = type
+local unpack   = unpack
+
+require 'curses'
+local addstr   = curses.addstr
+local addch    = curses.addch
+local clrtoeol = curses.clrtoeol
+local move     = curses.move
+
+module 'tictactoe_board'
+
+-- constants
+local board_background = {
+    "   |   |   ",
+    "   |   |   ",
+    "   |   |   ",
+    "---+---+---",
+    "   |   |   ",
+    "   |   |   ",
+    "   |   |   ",
+    "---+---+---",
+    "   |   |   ",
+    "   |   |   ",
+    "   |   |   ",
+}
+
+-- constructor arguments are the coordinates on the screen where the board
+-- should be drawn
+function new(y, x)
+    -- the board uses empty tables to represent 'empty tile', since the
+    -- table constructor is guaranteed to produce unique tables, which will
+    -- compare not equal with each other
+    local board = {
+        { {}, {}, {} },
+        { {}, {}, {} },
+        { {}, {}, {} },
+    }
+    return setmetatable({board = board, yorig = y, xorig = x}, {__index = _M})
+end
+
+function clone(self)
+    local copy = new(self.yorig, self.xorig)
+    for row in ipairs(self.board) do
+        for col in ipairs(self.board[row]) do
+            if self:at(row, col) ~= nil then
+                copy.board[row][col] = self.board[row][col]
+            end
+        end
+    end
+    return copy
+end
+
+function size()
+    return #board_background, board_background[1]:len()
+end
+
+-- translate board positions to positions on the screen
+-- return a table with named members, to pass directly to the curses functions
+function position(self, row, col)
+    return {y = self.yorig + (row - 1) * 4 + 1,
+            x = self.xorig + (col - 1) * 4 + 1}
+end
+
+function draw(self)
+    -- draw the board
+    for i, line in ipairs(board_background) do
+        addstr({y = self.yorig + i - 1, x = self.xorig}, line)
+    end
+
+    -- draw the x's and o's
+    for row in ipairs(self.board) do
+        for col, tile in ipairs(self.board[row]) do
+            if tile == "x" then
+                addch(self:position(row, col), "X", {color = "red"})
+            elseif tile == "o" then
+                addch(self:position(row, col), "O", {color = "blue"})
+            end
+        end
+    end
+end
+
+function at(self, y, x)
+    if type(self.board[y][x]) == "table" then
+        return nil
+    else
+        return self.board[y][x]
+    end
+end
+
+-- return a list of empty tiles on the board, where tiles are 2 element lists
+-- of {y, x}
+function empty_tiles(self)
+    local ret = {}
+    for row in ipairs(self.board) do
+        for col in ipairs(self.board[row]) do
+            if self:at(row, col) == nil then
+                insert(ret, {row, col})
+            end
+        end
+    end
+    return ret
+end
+
+function mark(self, turn, row, col)
+    if turn == "x" or turn == "o" then
+        self.board[row][col] = turn
+    else
+        error("mark called with \'" .. turn .. "\'")
+    end
+end
+
+-- check whether there is a winner on the board
+-- returns the symbol for the winner (or nil if there is no winner), as well as
+-- a list of the tiles that make up the win, so that we can mark them later
+function winner(self)
+    -- check rows and columns
+    for i = 1, 3 do
+        if self.board[i][1] == self.board[i][2] and
+           self.board[i][2] == self.board[i][3] then
+            return self.board[i][i], {{i, 1}, {i, 2}, {i, 3}}
+        elseif self.board[1][i] == self.board[2][i] and
+               self.board[2][i] == self.board[3][i] then
+            return self.board[i][i], {{1, i}, {2, i}, {3, i}}
+        end
+    end
+
+    -- check diagonals
+    if self.board[1][1] == self.board[2][2] and
+       self.board[2][2] == self.board[3][3] then
+        return self.board[2][2], {{1, 1}, {2, 2}, {3, 3}}
+    elseif self.board[3][1] == self.board[2][2] and
+           self.board[2][2] == self.board[1][3] then
+        return self.board[2][2], {{3, 1}, {2, 2}, {1, 3}}
+    end
+end
+
+function mark_winner(self, winner, winner_tiles)
+    for _, loc in ipairs(winner_tiles) do
+        addch(self:position(unpack(loc)), winner:upper(), {color = "green"})
+    end
+end
+
+-- draw a string centered under the board
+function caption(self, str)
+    move(self.yorig + #board_background + 1, 0)
+    clrtoeol()
+    addstr({y = self.yorig + #board_background + 1,
+            x = self.xorig + (board_background[1]:len() - 1) / 2 -
+                str:len() / 2},
+           str)
+end
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