1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
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
|
