Tic-tac-toe
You are encouraged to solve this task according to the task description, using any language you may know.
Play a game of tic-tac-toe. Ensure that legal moves are played and that a winning position is notified.
Ada
<lang Ada>with Ada.Text_IO, Ada.Numerics.Discrete_Random;
-- can play human-human, human-computer, computer-human or computer-computer -- the computer isn't very clever: it just chooses a legal random move
procedure Tic_Tac_Toe is
type The_Range is range 1 .. 3; type Board_Type is array (The_Range, The_Range) of Character;
package Rand is new Ada.Numerics.Discrete_Random(The_Range); Gen: Rand.Generator; -- required for the random moves
procedure Show_Board(Board: Board_Type) is
use Ada.Text_IO;
begin
for Row in The_Range loop
for Column in The_Range loop
Put(Board(Row, Column));
end loop;
Put_Line("");
end loop;
Put_Line("");
end Show_Board;
function Find_Winner(Board: Board_Type) return Character is
-- if 'x' or 'o' wins, it returns that, else it returns ' '
function Three_Equal(A,B,C: Character) return Boolean is
begin
return (A=B) and (A=C);
end Three_Equal;
begin -- Find_Winner
for I in The_Range loop
if Three_Equal(Board(I,1), Board(I,2), Board(I,3)) then
return Board(I,1);
elsif Three_Equal(Board(1,I), Board(2,I), Board(3,I)) then
return Board(1,I);
end if;
end loop;
if Three_Equal(Board(1,1), Board(2,2), Board (3,3)) or
Three_Equal(Board(3,1), Board(2,2), Board (1,3)) then
return Board(2,2);
end if;
return ' ';
end Find_Winner;
procedure Do_Move(Board: in out Board_Type;
New_Char: Character; Computer_Move: Boolean) is
Done: Boolean := False;
C: Character;
use Ada.Text_IO;
procedure Do_C_Move(Board: in out Board_Type; New_Char: Character) is
Found: Boolean := False;
X,Y: The_Range;
begin
while not Found loop
X := Rand.Random(Gen);
Y := Rand.Random(Gen);
if (Board(X,Y) /= 'x') and (Board(X,Y) /= 'o') then
Found := True;
Board(X,Y) := New_Char;
end if;
end loop;
end Do_C_Move;
begin
if Computer_Move then
Do_C_Move(Board, New_Char);
else -- read move;
Put_Line("Choose your move, " & New_Char);
while not Done loop
Get(C);
for Row in The_Range loop
for Col in The_Range loop
if Board(Row, Col) = C then
Board(Row, Col) := New_Char;
Done := True;
end if;
end loop;
end loop;
end loop;
end if;
end Do_Move;
The_Board : Board_Type := (('1','2','3'), ('4','5','6'), ('7','8','9'));
Cnt_Moves: Natural := 0;
Players: array(0 .. 1) of Character := ('x', 'o'); -- 'x' begins
C_Player: array(0 .. 1) of Boolean := (False, False);
Reply: Character;
begin -- Tic_Tac_Toe
-- firstly, ask whether the computer shall take over either player
for I in Players'Range loop
Ada.Text_IO.Put_Line("Shall " & Players(I) &
" be run by the computer? (y=yes)");
Ada.Text_IO.Get(Reply);
if Reply='y' or Reply='Y' then
C_Player(I) := True;
Ada.Text_IO.Put_Line("Yes!");
else
Ada.Text_IO.Put_Line("No!");
end if;
end loop;
Rand.Reset(Gen); -- to initalize the random generator
-- now run the game
while (Find_Winner(The_Board) = ' ') and (Cnt_Moves < 9) loop
Show_Board(The_Board);
Do_Move(The_Board, Players(Cnt_Moves mod 2), C_Player(Cnt_Moves mod 2));
Cnt_Moves := Cnt_Moves + 1;
end loop;
Ada.Text_IO.Put_Line("This is the end!");
-- finally, output the outcome
Show_Board (The_Board);
if Find_Winner(The_Board) = ' ' then
Ada.Text_IO.Put_Line("Draw");
else
Ada.Text_IO.Put_Line("The winner is: " & Find_Winner(The_Board));
end if;
end Tic_Tac_Toe;</lang>
Output:
> ./tic_tac_toe Shall x be run by the computer? (y=yes) y Yes! Shall o be run by the computer? (y=yes) n No! 123 456 789 1x3 456 789 Choose your move, o 5 1x3 4o6 789 1x3 xo6 789 Choose your move, o 6 1x3 xoo 789 1xx xoo 789 Choose your move, o 1 oxx xoo 789 oxx xoo 78x Choose your move, o 7 oxx xoo o8x This is the end! oxx xoo oxx Draw > ./tic_tac_toe Shall x be run by the computer? (y=yes) n No! Shall o be run by the computer? (y=yes) y Yes! 123 456 789 Choose your move, x 6 123 45x 789 123 45x o89 Choose your move, x 4 123 x5x o89 123 x5x o8o Choose your move, x 8 123 x5x oxo o23 x5x oxo Choose your move, x 5 This is the end! o23 xxx oxo The winner is: x
AutoHotkey
This program uses a Gui with 9 buttons. Clicking on one will place an X there, disable the button, and cause the program to go somewhere. It plays logically, trying to win, trying to block, or playing randomly in that order. <lang AutoHotkey>Gui, Add, Button, x12 y12 w30 h30 vB1 gButtonHandler, Gui, Add, Button, x52 y12 w30 h30 vB2 gButtonHandler, Gui, Add, Button, x92 y12 w30 h30 vB3 gButtonHandler, Gui, Add, Button, x12 y52 w30 h30 vB4 gButtonHandler, Gui, Add, Button, x52 y52 w30 h30 vB5 gButtonHandler, Gui, Add, Button, x92 y52 w30 h30 vB6 gButtonHandler, Gui, Add, Button, x12 y92 w30 h30 vB7 gButtonHandler, Gui, Add, Button, x52 y92 w30 h30 vB8 gButtonHandler, Gui, Add, Button, x92 y92 w30 h30 vB9 gButtonHandler,
- Generated using SmartGUI Creator 4.0
Gui, Show, x127 y87 h150 w141, Tic-Tac-Toe Winning_Moves := "123,456,789,147,258,369,159,357" Return
ButtonHandler:
; Fired whenever the user clicks on an enabled button Go(A_GuiControl,"X") GoSub MyMove
Return
MyMove: ; Loops through winning moves. First attempts to win, then to block, then a random move
Went=0
Loop, parse, Winning_Moves,`,
{
Current_Set := A_LoopField
X:=O:=0
Loop, parse, Current_Set
{
GuiControlGet, Char,,Button%A_LoopField%
If ( Char = "O" )
O++
If ( Char = "X" )
X++
}
If ( O = 2 and X = 0 ) or ( X = 2 and O = 0 ){
Finish_Line(Current_Set)
Went = 1
Break ; out of the Winning_Moves Loop to ensure the computer goes only once
}
}
If (!Went)
GoSub RandomMove
Return
Go(Control,chr){
GuiControl,,%Control%, %chr% GuiControl,Disable,%Control% GoSub, CheckWin
}
CheckWin:
Loop, parse, Winning_Moves,`,
{
Current_Set := A_LoopField
X:=O:=0
Loop, parse, Current_Set
{
GuiControlGet, Char,,Button%A_LoopField%
If ( Char = "O" )
O++
If ( Char = "X" )
X++
}
If ( O = 3 ){
Msgbox O Wins!
GoSub DisableAll
Break
}
If ( X = 3 ){
MsgBox X Wins!
GoSub DisableAll
Break
}
}
return
DisableAll:
Loop, 9
GuiControl, Disable, Button%A_Index%
return
Finish_Line(Set){ ; Finish_Line is called when a line exists with 2 of the same character. It goes in the remaining spot, thereby blocking or winning.
Loop, parse, set
{
GuiControlGet, IsEnabled, Enabled, Button%A_LoopField%
Control=Button%A_LoopField%
If IsEnabled
Go(Control,"O")
}
}
RandomMove:
Loop{
Random, rnd, 1, 9
GuiControlGet, IsEnabled, Enabled, Button%rnd%
If IsEnabled
{
Control=Button%rnd%
Go(Control,"O")
Break
}
}
return
GuiClose: ExitApp </lang>
C
Opening alternates between human and computer. Computer never loses. <lang C>#include <stdio.h>
- include <stdlib.h>
int b[3][3]; /* board. 0: blank; -1: computer; 1: human */
int check_winner() { int i; for (i = 0; i < 3; i++) { if (b[i][0] && b[i][1] == b[i][0] && b[i][2] == b[i][0]) return b[i][0]; if (b[0][i] && b[1][i] == b[0][i] && b[2][i] == b[0][i]) return b[0][i]; } if (!b[1][1]) return 0;
if (b[1][1] == b[0][0] && b[2][2] == b[0][0]) return b[0][0]; if (b[1][1] == b[2][0] && b[0][2] == b[1][1]) return b[1][1];
return 0; }
void showboard() { char *t = "X O"; int i, j; for (i = 0; i < 3; i++, putchar('\n')) for (j = 0; j < 3; j++) printf("%c ", t[ b[i][j] + 1 ]); printf("-----\n"); }
- define for_ij for (i = 0; i < 3; i++) for (j = 0; j < 3; j++)
int best_i, best_j; int test_move(int val, int depth) { int i, j, score; int best = -1, changed = 0;
if ((score = check_winner())) return (score == val) ? 1 : -1;
for_ij { if (b[i][j]) continue;
changed = b[i][j] = val; score = -test_move(-val, depth + 1); b[i][j] = 0;
if (score <= best) continue; if (!depth) { best_i = i; best_j = j; } best = score; }
return changed ? best : 0; }
char* game(int user) { int i, j, k, move, win = 0; for_ij b[i][j] = 0;
printf("Board postions are numbered so:\n1 2 3\n4 5 6\n7 8 9\n"); printf("You have O, I have X.\n\n"); for (k = 0; k < 9; k++, user = !user) { while(user) { printf("your move: "); if (!scanf("%d", &move)) { scanf("%*s"); continue; } if (--move < 0 || move >= 9) continue; if (b[i = move / 3][j = move % 3]) continue;
b[i][j] = 1; break; } if (!user) { if (!k) { /* randomize if computer opens, less boring */ best_i = rand() % 3; best_j = rand() % 3; } else test_move(-1, 0);
b[best_i][best_j] = -1; printf("My move: %d\n", best_i * 3 + best_j + 1); }
showboard(); if ((win = check_winner())) return win == 1 ? "You win.\n\n": "I win.\n\n"; } return "A draw.\n\n"; }
int main() { int first = 0; while (1) printf(game(first = !first)); return 0; }</lang>
D
<lang d>import std.stdio, std.string, std.algorithm, std.conv,
std.random, std.ascii, std.array, std.range;
struct GameBoard {
char[9] board = "123456789".dup;
enum char human = 'X',
computer = 'O';
enum GameState { going, humanWins, computerWins, draw }
invariant() {
foreach (i, c; board)
if (isDigit(c))
assert(i == c - '1'); // in correct position?
else
assert(c == human || c == computer);
}
string toString() const {
string row(in int start) {
return format("%s|%s|%s\n", board[start + 0],
board[start + 1],
board[start + 2]);
}
enum string lineSep = "-+-+-\n";
return row(0) ~ lineSep ~ row(3) ~ lineSep ~ row(6);
}
int[] availablePositions() const /*pure nothrow*/ {
auto p = filter!((i){ return isDigit(board[i]); })(iota(9));
return array(p);
}
bool isAvailable(in int position) const pure nothrow {
if (position < 0 || position >= 9)
return false;
return isDigit(board[position]);
}
bool finished() const /*pure nothrow*/ {
return winner() != GameState.going;
}
GameState winner() const /*pure nothrow*/ {
enum wins = [[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]];
foreach (win; wins) {
const char desired = board[win[0]];
if (isDigit(desired))
continue; // nobody wins on this one
// the same player needs to take all three positions
if (board[win[1]] == desired && board[win[2]] == desired)
return desired == GameBoard.human ?
GameState.humanWins :
GameState.computerWins;
}
if (availablePositions().length == 0)
return GameState.draw;
return GameState.going;
}
int computerMove() const // random move
out(ret) {
assert(ret >= 0 && ret < 9);
assert(isAvailable(ret));
} body {
// return choice(availablePositions());
return randomCover(availablePositions(),
Random(unpredictableSeed)).front;
}
}
GameBoard playGame() {
GameBoard board; bool playsHuman = true;
while (!board.finished()) {
writeln(board);
int move;
if (playsHuman) {
do {
writef("Your move (available moves %s)? ",
map!q{ a + 1 }(board.availablePositions()));
readf("%d\n", &move);
move--; // zero based indexing
if (move < 0)
return board;
} while (!board.isAvailable(move));
} else
move = board.computerMove();
assert(board.isAvailable(move));
writefln("%s chose %d", playsHuman ? "You" : "I", move + 1);
board.board[move] = playsHuman ? GameBoard.human :
GameBoard.computer;
playsHuman = !playsHuman; // switch player
}
return board;
}
void main() {
writeln("Tic-tac-toe game player.");
const GameBoard.GameState outcome = playGame().winner();
final switch (outcome) {
case GameBoard.GameState.going:
writeln("Game stopped.");
break;
case GameBoard.GameState.humanWins:
writeln("\nYou win!");
break;
case GameBoard.GameState.computerWins:
writeln("\nI win.");
break;
case GameBoard.GameState.draw:
writeln("\nDraw");
break;
}
}</lang> Output example:
Tic-tac-toe game player. 1|2|3 -+-+- 4|5|6 -+-+- 7|8|9 Your move (available moves [1, 2, 3, 4, 5, 6, 7, 8, 9])? 1 You chose 1 X|2|3 -+-+- 4|5|6 -+-+- 7|8|9 I chose 4 X|2|3 -+-+- O|5|6 -+-+- 7|8|9 Your move (available moves [2, 3, 5, 6, 7, 8, 9])? 5 You chose 5 X|2|3 -+-+- O|X|6 -+-+- 7|8|9 I chose 9 X|2|3 -+-+- O|X|6 -+-+- 7|8|O Your move (available moves [2, 3, 6, 7, 8])? 3 You chose 3 X|2|X -+-+- O|X|6 -+-+- 7|8|O I chose 6 X|2|X -+-+- O|X|O -+-+- 7|8|O Your move (available moves [2, 7, 8])? 7 You chose 7 You win!
F#
A purely-functional solution with a naive (but perfect) computer player implementation. The first move is played randomly by the computer.
<lang fsharp>type Brick =
| Empty | Computer | User
let brickToString = function
| Empty -> ' ' | Computer -> 'X' | User -> 'O'
// y -> x -> Brick type Board = Map<int, Map<int, Brick> >
let emptyBoard =
let emptyRow = Map.ofList [0,Empty; 1,Empty; 2,Empty] Map.ofList [0,emptyRow; 1,emptyRow; 2,emptyRow]
let get (b:Board) (x,y) = b.[y].[x]
let set player (b:Board) (x,y) : Board =
let row = b.[y].Add(x, player) b.Add(y, row)
let winningPositions =
[for x in [0..2] -> x,x] // first diagonal
::[for x in [0..2] -> 2-x,x] // second diagonal
::[for y in [0..2] do
yield! [[for x in [0..2]->(y,x)]; // columns
[for x in [0..2] -> (x,y)]]] // rows
let hasWon player board =
List.exists (fun ps -> List.forall (fun pos -> get board pos = player) ps) winningPositions
let freeSpace board =
[for x in 0..2 do
for y in 0..2 do
if get board (x,y) = Empty then yield x,y]
type Evaluation =
| Win | Draw | Lose
let rec evaluate board move =
let b2 = set Computer board move
if hasWon Computer b2 then Win
else
match freeSpace b2 with
| [] -> Draw
| userChoices ->
let b3s = List.map (set User b2) userChoices
if List.exists (hasWon User) b3s then Lose
elif List.exists (fun b3 -> bestOutcome b3 = Lose) b3s
then Lose
elif List.exists (fun b3 -> bestOutcome b3 = Draw) b3s
then Draw
else Win
and findBestChoice b =
match freeSpace b with
| [] -> ((-1,-1), Draw)
| choices ->
match List.tryFind (fun c -> evaluate b c = Win) choices with
| Some c -> (c, Win)
| None -> match List.tryFind (fun c -> evaluate b c = Draw) choices with
| Some c -> (c, Draw)
| None -> (List.head choices, Lose)
and bestOutcome b = snd (findBestChoice b)
let bestChoice b = fst (findBestChoice b)
let computerPlay b = set Computer b (bestChoice b)
let printBoard b =
printfn " | A | B | C |" printfn "---+---+---+---+" for y in 0..2 do printfn " %d | %c | %c | %c |" (3-y) (get b (0,y) |> brickToString) (get b (1,y) |> brickToString) (get b (2,y) |> brickToString) printfn "---+---+---+---+"
let rec userPlay b =
printfn "Which field do you play? (format: a1)"
let input = System.Console.ReadLine()
if input.Length <> 2
|| input.[0] < 'a' || input.[0] > 'c'
|| input.[1] < '1' || input.[1] > '3' then
printfn "illegal input"
userPlay b
else
let x = int(input.[0]) - int('a')
let y = 2 - int(input.[1]) + int('1')
if get b (x,y) <> Empty then
printfn "Field is not free."
userPlay b
else
set User b (x,y)
let rec gameLoop b player =
if freeSpace b = [] then
printfn "Game over. Draw."
elif player = Computer then
printfn "Computer plays..."
let b2 = computerPlay b
printBoard b2
if hasWon Computer b2 then
printfn "Game over. I have won."
else
gameLoop b2 User
elif player = User then
let b2 = userPlay b
printBoard b2
if hasWon User b2 then
printfn "Game over. You have won."
else
gameLoop b2 Computer
// randomly choose an element of a list let choose =
let rnd = new System.Random() fun (xs:_ list) -> xs.[rnd.Next(xs.Length)]
// play first brick randomly printfn "Computer starts." let b = set Computer emptyBoard (choose (freeSpace emptyBoard)) printBoard b gameLoop b User</lang>
Example game:
Computer starts. | A | B | C | ---+---+---+---+ 3 | | | X | ---+---+---+---+ 2 | | | | ---+---+---+---+ 1 | | | | ---+---+---+---+ Which field do you play? (format: a1) a1 | A | B | C | ---+---+---+---+ 3 | | | X | ---+---+---+---+ 2 | | | | ---+---+---+---+ 1 | O | | | ---+---+---+---+ Computer plays... | A | B | C | ---+---+---+---+ 3 | X | | X | ---+---+---+---+ 2 | | | | ---+---+---+---+ 1 | O | | | ---+---+---+---+ Which field do you play? (format: a1) b3 | A | B | C | ---+---+---+---+ 3 | X | O | X | ---+---+---+---+ 2 | | | | ---+---+---+---+ 1 | O | | | ---+---+---+---+ Computer plays... | A | B | C | ---+---+---+---+ 3 | X | O | X | ---+---+---+---+ 2 | | | | ---+---+---+---+ 1 | O | | X | ---+---+---+---+ Which field do you play? (format: a1) c2 | A | B | C | ---+---+---+---+ 3 | X | O | X | ---+---+---+---+ 2 | | | O | ---+---+---+---+ 1 | O | | X | ---+---+---+---+ Computer plays... | A | B | C | ---+---+---+---+ 3 | X | O | X | ---+---+---+---+ 2 | | X | O | ---+---+---+---+ 1 | O | | X | ---+---+---+---+ Game over. I have won.
Icon and Unicon
The following works in both Icon and Unicon. The computer plays randomly against a human player, with legal moves enforced and wins/draws notified.
<lang Icon>
- Play TicTacToe
$define E " " # empty square $define X "X" # X piece $define O "O" # O piece
- -- define a board
record Board(a, b, c, d, e, f, g, h, i)
procedure display_board (board, player)
write ("\n===============")
write (board.a || " | " || board.b || " | " || board.c)
write ("---------")
write (board.d || " | " || board.e || " | " || board.f)
write ("---------")
write (board.g || " | " || board.h || " | " || board.i)
end
- return a set of valid moves (empty positions) in given board
procedure empty_fields (board)
fields := set() every i := !fieldnames(board) do if (board[i] == E) then insert (fields, i) return fields
end
procedure game_start ()
return Board (E, E, E, E, E, E, E, E, E)
end
procedure game_is_drawn (board)
return *empty_fields(board) = 0
end
procedure game_won_by (board, player)
return (board.a == board.b == board.c == player) |
(board.d == board.e == board.f == player) |
(board.g == board.h == board.i == player) |
(board.a == board.d == board.g == player) |
(board.b == board.e == board.h == player) |
(board.c == board.f == board.i == player) |
(board.a == board.e == board.i == player) |
(board.g == board.e == board.c == player)
end
procedure game_over (board)
return game_is_drawn (board) | game_won_by (board, O) | game_won_by (board, X)
end
- -- players make their move on the board
- assume there is at least one empty square
procedure human_move (board, player)
choice := "z"
options := empty_fields (board)
# keep prompting until player selects a valid square
until member (options, choice) do {
writes ("Choose one of: ")
every writes (!options || " ")
writes ("\n> ")
choice := read ()
}
board[choice] := player
end
- pick and make a move at random from empty positions
procedure random_move (board, player)
board[?empty_fields(board)] := player
end
- -- manage the game play
procedure play_game ()
# hold procedures for players' move in variables player_O := random_move player_X := human_move
# randomly determine if human or computer moves first
if (?2 = 0)
then {
write ("Human plays first as O")
player_O := human_move
player_X := random_move
}
else write ("Computer plays first, human is X")
# set up the game to start
board := game_start ()
player := O
display_board (board, player)
# loop until the game is over, getting each player to move in turn
until game_over (board) do {
write (player || " to play next")
# based on player, prompt for the next move
if (player == O)
then (player_O (board, player))
else (player_X (board, player))
# change player to move
player := if (player == O) then X else O
display_board (board, player)
}
# finish by writing out result
if game_won_by (board, O)
then write ("O won")
else if game_won_by (board, X)
then write ("X won")
else write ("draw") # neither player won, so must be a draw
end
- -- get things started
procedure main ()
play_game ()
end </lang>
PicoLisp
This solution doesn't bother about the game logic, but simply uses the alpha-beta-pruning 'game' function in the "simul" library. <lang PicoLisp>(load "@lib/simul.l") # for 'game' function
(de display ()
(for Y (3 2 1)
(prinl " +---+---+---+")
(prin " " Y)
(for X (1 2 3)
(prin " | " (or (get *Board X Y) " ")) )
(prinl " |") )
(prinl " +---+---+---+")
(prinl " a b c") )
(de find3 (P)
(find
'((X Y DX DY)
(do 3
(NIL (= P (get *Board X Y)))
(inc 'X DX)
(inc 'Y DY)
T ) )
(1 1 1 1 2 3 1 1)
(1 2 3 1 1 1 1 3)
(1 1 1 0 0 0 1 1)
(0 0 0 1 1 1 1 -1) ) )
(de myMove ()
(when
(game NIL 8
'((Flg) # Moves
(unless (find3 (or (not Flg) 0))
(make
(for (X . L) *Board
(for (Y . P) L
(unless P
(link
(cons
(cons X Y (or Flg 0))
(list X Y) ) ) ) ) ) ) ) )
'((Mov) # Move
(set (nth *Board (car Mov) (cadr Mov)) (cddr Mov)) )
'((Flg) # Cost
(if (find3 (or Flg 0)) -100 0) ) )
(let Mov (caadr @)
(set (nth *Board (car Mov) (cadr Mov)) 0) )
(display) ) )
(de yourMove (X Y)
(and
(sym? X)
(>= 3 (setq X (- (char X) 96)) 1)
(num? Y)
(>= 3 Y 1)
(not (get *Board X Y))
(set (nth *Board X Y) T)
(display) ) )
(de main ()
(setq *Board (make (do 3 (link (need 3))))) (display) )
(de go Args
(cond
((not (yourMove (car Args) (cadr Args)))
"Illegal move!" )
((find3 T) "Congratulation, you won!")
((not (myMove)) "No moves")
((find3 0) "Sorry, you lost!") ) )</lang>
Output:
: (main)
+---+---+---+
3 | | | |
+---+---+---+
2 | | | |
+---+---+---+
1 | | | |
+---+---+---+
a b c
: (go a 1)
+---+---+---+
3 | | | |
+---+---+---+
2 | | | |
+---+---+---+
1 | T | | |
+---+---+---+
a b c
+---+---+---+
3 | | | |
+---+---+---+
2 | | 0 | |
+---+---+---+
1 | T | | |
+---+---+---+
a b c
Prolog
Works with SWI-Prolog.
Uses a minimax algorithm with no Alpha-beta pruning, as the max depth of the recursion is 8. Computer never loses.
A GUI interface written in XPCE is given.
<lang Prolog>:- use_module('min-max.pl').
- -dynamic box/2.
- - dynamic tic_tac_toe_window/1.
% Computer begins. tic-tac-toe(computer) :- V is random(9), TTT = [_,_,_,_,_,_ ,_,_,_], nth0(V, TTT, o), display_tic_tac_toe(TTT).
% Player begins tic-tac-toe(me) :- TTT = [_,_,_,_,_,_ ,_,_,_], display_tic_tac_toe(TTT).
display_tic_tac_toe(TTT) :-
retractall(box(_,_)),
retractall(tic_tac_toe_window(_)),
new(D, window('Tic-tac-Toe')),
send(D, size, size(170,170)),
X = 10, Y = 10,
display(D, X, Y, 0, TTT),
assert(tic_tac_toe_window(D)),
send(D, open).
display(_, _, _, _, []).
display(D, X, Y, N, [A,B,C|R]) :- display_line(D, X, Y, N, [A,B,C]), Y1 is Y+50, N3 is N+3, display(D, X, Y1, N3, R).
display_line(_, _, _, _, []).
display_line(D, X, Y, N, [C|R]) :-
( nonvar(C)-> C1 = C; C1 = ' '),
new(B, tic_tac_toe_box(C1)),
assertz(box(N, B)),
send(D, display, B, point(X, Y)),
X1 is X + 50,
N1 is N+1,
display_line(D, X1, Y, N1, R).
% class tic_tac_toe_box % display an 'x' when the player clicks % display an 'o' when the computer plays
- - pce_begin_class(tic_tac_toe_box, box, "Graphical window with text").
variable(mess, any, both, "text to display").
initialise(P, Lbl) :-> send(P, send_super, initialise), send(P, slot, mess, Lbl), WS = 50, HS = 50, send(P, size, size(WS,HS)), send(P, recogniser, handler_group(new(click_gesture(left, , single, message(@receiver, my_click))))).
% the box is clicked my_click(B) :-> send(B, set_val, x), send(@prolog, play).
% only works when the box is "free" set_val(B, Val) :-> get(B, slot, mess, ' '), send(B, slot, mess, Val), send(B, redraw), send(B, flush).
% redefined method to display custom graphical objects.
'_redraw_area'(P, A:area) :->
send(P, send_super, '_redraw_area', A),
%we display the text
get(P, slot, mess, Lbl),
new(Str1, string(Lbl)),
get_object(P, area, area(X,Y,W,H)),
send(P, draw_box, X, Y, W, H),
send(P, draw_text, Str1,
font(times, normal, 30),
X, Y, W, H, center, center).
- - pce_end_class.
play :- numlist(0, 8, L), maplist(init, L, TTT), finished(x, TTT, Val), ( Val = 2 -> send(@display, inform,'You win !'), tic_tac_toe_window(D), send(D, destroy) ; ( Val = 1 -> send(@display, inform,'Draw !'), tic_tac_toe_window(D), send(D, destroy) ; next_move(TTT, TT1), maplist(display, L, TT1), finished(o, TT1, V), ( V = 2 -> send(@display, inform,'I win !'), tic_tac_toe_window(D), send(D, destroy) ; ( V = 1 -> send(@display, inform,'Draw !'), tic_tac_toe_window(D), send(D, destroy) ; true)))).
% use minmax to compute the next move
next_move(TTT, TT1) :-
minimax(o, 0, 1024, TTT, _V1- TT1).
% we display the new board
display(I, V) :-
nonvar(V),
box(I, V1),
send(V1, set_val, V).
display(_I, _V).
% we create the board for minmax init(I, V) :- box(I, V1), get(V1, slot, mess, V), V \= ' '.
init(_I, _V).
% winning position for the player P ? winned(P, [A1, A2, A3, A4, A5, A6, A7, A8, A9]) :-
(is_winning_line(P, [A1, A2, A3]);
is_winning_line(P, [A4, A5, A6]); is_winning_line(P, [A7, A8, A9]); is_winning_line(P, [A1, A4, A7]); is_winning_line(P, [A2 ,A5, A8]); is_winning_line(P, [A3, A6, A9]); is_winning_line(P, [A1, A5, A9]); is_winning_line(P, [A3, A5, A7])).
is_winning_line(P, [A, B, C]) :-
nonvar(A), A = P,
nonvar(B), B = P,
nonvar(C), C = P.
% Winning position for the player eval(Player, Deep, TTT, V) :- winned(Player, TTT), ( Player = o -> V is 1000 - 50 * Deep; V is -1000+ 50 * Deep).
% Loosing position for the player eval(Player, Deep, TTT, V) :- select(Player, [o,x], [Player1]), winned(Player1, TTT), ( Player = x -> V is 1000 - 50 * Deep; V is -1000+ 50 * Deep).
% Draw position eval(_Player, _Deep, TTT, 0) :- include(var, TTT, []).
% we fetch the free positions of the board
possible_move(TTT, LMove) :-
new(C, chain),
forall(between(0,8, I),
( nth0(I, TTT, X),
( var(X) -> send(C, append, I); true))),
chain_list(C, LMove).
% we create the new position when the player P clicks % the box "N" assign_move(P, TTT, N, TT1) :- copy_term(TTT, TT1), nth0(N, TT1, P).
% We fetch all the possible boards obtained from board TTT % for the player P get_next(Player, Deep, TTT, Player1, Deep1, L):- possible_move(TTT, LMove), select(Player, [o,x], [Player1]), Deep1 is Deep + 1, maplist(assign_move(Player, TTT), LMove, L).
% The game is over ?
% Player P wins
finished(P, TTT, 2) :-
winned(P, TTT).
% Draw finished(_P, TTT, 1) :- include(var, TTT, []).
% the game is not over finished(_P, _TTT, 0) .
% minmax must knows when the computer plays % (o for ordinateur in French) computer(o).
</lang> Module min-max.pl defines minimax algorithm. <lang prolog>:- module('min-max.pl', [minimax/5]).
% minimax(Player, Deep, MaxDeep, B, V-B) % @arg1 : current player at this level % @arg2 : current level of recursion % @arg3 : max level of recursion (in this version of the game no use : set to 1024 !) % @arg4 : current board % @arg5 : B is the evaluation of the board, the result is V-B to know the new board
% Here we get an evaluation minimax(Player, Deep, MaxDeep, B, V-B) :- ( eval(Player, Deep, B, V) -> true ; % in this version if the game this second division always fails ( Deep > MaxDeep) -> V is random(2000 - 1000)).
% here we must compute all the possible moves to know the evaluation of the board minimax(Player, Deep, MaxDeep, B, V) :- get_next(Player, Deep, B, Player1, Deep1, L), maplist(minimax(Player1, Deep1, MaxDeep), L, LV), maplist(lie, L, LV, TLV), sort(TLV, SLVTmp), ( computer(Player) -> reverse(SLVTmp, SLV); SLV = SLVTmp), SLV = [V | _R].
lie(TTT, V-_, V-TTT).
</lang>
Python
The computer enforces the rules but plays a random game. <lang python>
Tic-tac-toe game player. Input the index of where you wish to place your mark at your turn.
import random
board = list('123456789') wins = ((0,1,2), (3,4,5), (6,7,8),
(0,3,6), (1,4,7), (2,5,8),
(0,4,8), (2,4,6))
def printboard():
print('\n'.join(' '.join(board[x:x+3]) for x in(0,3,6)))
def score():
for w in wins:
b = board[w[0]]
if b in 'XO' and all (board[i] == b for i in w):
return b, [i+1 for i in w]
return None, None
def finished():
return all (b in 'XO' for b in board)
def space():
return [ b for b in board if b not in 'XO']
def my_turn(xo):
options = space() choice = random.choice(options) board[int(choice)-1] = xo return choice
def your_turn(xo):
options = space()
while True:
choice = input(" Put your %s in any of these positions: %s "
% (xo, .join(options))).strip()
if choice in options:
break
print( "Whoops I don't understand the input" )
board[int(choice)-1] = xo
return choice
def me(xo='X'):
printboard()
print('I go at', my_turn(xo))
return score()
assert not s[0], "\n%s wins across %s" % s
def you(xo='O'):
printboard()
# Call my_turn(xo) below for it to play itself
print('You went at', your_turn(xo))
return score()
assert not s[0], "\n%s wins across %s" % s
print(__doc__)
while not finished():
s = me('X')
if s[0]:
printboard()
print("\n%s wins across %s" % s)
break
if not finished():
s = you('O')
if s[0]:
printboard()
print("\n%s wins across %s" % s)
break
else:
print('\nA draw')
</lang>
Sample Game
Tic-tac-toe game player.
Input the index of where you wish to place your mark at your turn.
1 2 3
4 5 6
7 8 9
I go at 9
1 2 3
4 5 6
7 8 X
Put your O in any of these positions: 12345678 1
You went at 1
O 2 3
4 5 6
7 8 X
I go at 3
O 2 X
4 5 6
7 8 X
Put your O in any of these positions: 245678 4
You went at 4
O 2 X
O 5 6
7 8 X
I go at 2
O X X
O 5 6
7 8 X
Put your O in any of these positions: 5678 7
You went at 7
O X X
O 5 6
O 8 X
O wins across [1, 4, 7]
Better skilled player
In this version, The computer player will first complete a winning line of its own if it can, otherwise block a winning line of its opponent if they have two in a row, or then choose a random move.
<lang python>
Tic-tac-toe game player. Input the index of where you wish to place your mark at your turn.
import random
board = list('123456789') wins = ((0,1,2), (3,4,5), (6,7,8),
(0,3,6), (1,4,7), (2,5,8),
(0,4,8), (2,4,6))
def printboard():
print('\n-+-+-\n'.join('|'.join(board[x:x+3]) for x in(0,3,6)))
def score(board=board):
for w in wins:
b = board[w[0]]
if b in 'XO' and all (board[i] == b for i in w):
return b, [i+1 for i in w]
return None
def finished():
return all (b in 'XO' for b in board)
def space(board=board):
return [ b for b in board if b not in 'XO']
def my_turn(xo, board):
options = space() choice = random.choice(options) board[int(choice)-1] = xo return choice
def my_better_turn(xo, board):
'Will return a next winning move or block your winning move if possible'
ox = 'O' if xo =='X' else 'X'
oneblock = None
options = [int(s)-1 for s in space(board)]
for choice in options:
brd = board[:]
brd[choice] = xo
if score(brd):
break
if oneblock is None:
brd[choice] = ox
if score(brd):
oneblock = choice
else:
choice = oneblock if oneblock is not None else random.choice(options)
board[choice] = xo
return choice+1
def your_turn(xo, board):
options = space()
while True:
choice = input("\nPut your %s in any of these positions: %s "
% (xo, .join(options))).strip()
if choice in options:
break
print( "Whoops I don't understand the input" )
board[int(choice)-1] = xo
return choice
def me(xo='X'):
printboard()
print('\nI go at', my_better_turn(xo, board))
return score()
def you(xo='O'):
printboard()
# Call my_turn(xo, board) below for it to play itself
print('\nYou went at', your_turn(xo, board))
return score()
print(__doc__)
while not finished():
s = me('X')
if s:
printboard()
print("\n%s wins along %s" % s)
break
if not finished():
s = you('O')
if s:
printboard()
print("\n%s wins along %s" % s)
break
else:
print('\nA draw')</lang>
Sample output
Tic-tac-toe game player.
Input the index of where you wish to place your mark at your turn.
1|2|3
-+-+-
4|5|6
-+-+-
7|8|9
I go at 2
1|X|3
-+-+-
4|5|6
-+-+-
7|8|9
Put your O in any of these positions: 13456789 5
You went at 5
1|X|3
-+-+-
4|O|6
-+-+-
7|8|9
I go at 1
X|X|3
-+-+-
4|O|6
-+-+-
7|8|9
Put your O in any of these positions: 346789 3
You went at 3
X|X|O
-+-+-
4|O|6
-+-+-
7|8|9
I go at 7
X|X|O
-+-+-
4|O|6
-+-+-
X|8|9
Put your O in any of these positions: 4689 4
You went at 4
X|X|O
-+-+-
O|O|6
-+-+-
X|8|9
I go at 6
X|X|O
-+-+-
O|O|X
-+-+-
X|8|9
Put your O in any of these positions: 89 9
You went at 9
X|X|O
-+-+-
O|O|X
-+-+-
X|8|O
I go at 8
A draw
Tcl
<lang tcl>package require Tcl 8.6
- This code splits the players from the core game engine
oo::class create TicTacToe {
variable board player letter who
constructor {player1class player2class} {
set board {1 2 3 4 5 6 7 8 9} set player(0) [$player1class new [self] [set letter(0) "X"]] set player(1) [$player2class new [self] [set letter(1) "O"]] set who 0
}
method PrintBoard {} {
lassign $board a1 b1 c1 a2 b2 c2 a3 b3 c3 puts [format " %s | %s | %s" $a1 $b1 $c1] puts "---+---+---" puts [format " %s | %s | %s" $a2 $b2 $c2] puts "---+---+---" puts [format " %s | %s | %s" $a3 $b3 $c3]
}
method WinForSomeone {} {
foreach w { {0 1 2} {3 4 5} {6 7 8} {0 3 6} {1 4 7} {2 5 8} {0 4 8} {2 4 6} } { set b [lindex $board [lindex $w 0]] if {$b ni "X O"} continue foreach i $w {if {[lindex $board $i] ne $b} break} if {[lindex $board $i] eq $b} { foreach p $w {lappend w1 [expr {$p+1}]} return [list $b $w1] } } return ""
}
method status {} {
return $board
}
method IsDraw {} {
foreach b $board {if {[string is digit $b]} {return false}} return true
}
method legalMoves {} {
foreach b $board {if {[string is digit $b]} {lappend legal $b}} return $legal
}
method DoATurn {} {
set legal [my legalMoves] my PrintBoard while 1 { set move [$player($who) turn] if {$move in $legal} break puts "Illegal move!" } lset board [expr {$move - 1}] $letter($who) $player($who) describeMove $move set who [expr {1 - $who}] return [my WinForSomeone]
}
method game {} {
puts " Tic-tac-toe game player.
Input the index of where you wish to place your mark at your turn.\n"
while {![my IsDraw]} { set winner [my DoATurn] if {$winner eq ""} continue lassign $winner winLetter winSites my PrintBoard puts "\n$winLetter wins across \[[join $winSites {, }]\]" return $winLetter } puts "\nA draw"
}
}
- Stupid robotic player
oo::class create RandomRoboPlayer {
variable g
constructor {game letter} {
set g $game
}
method turn {} {
set legal [$g legalMoves] return [lindex $legal [expr {int(rand()*[llength $legal])}]]
}
method describeMove {move} {
puts "I go at $move"
}
}
- Interactive human player delegate
oo::class create HumanPlayer {
variable g char
constructor {game letter} {
set g $game set char $letter
}
method turn {} {
set legal [$g legalMoves] puts ">>> Put your $char in any of these positions: [join $legal {}]" while 1 { puts -nonewline ">>> " flush stdout gets stdin number if {$number in $legal} break puts ">>> Whoops I don't understand the input!" } return $number
}
method describeMove {move} {
puts "You went at $move"
}
}
- Assemble the pieces
set ttt [TicTacToe new HumanPlayer RandomRoboPlayer] $ttt game</lang> Sample game:
Tic-tac-toe game player.
Input the index of where you wish to place your mark at your turn.
1 | 2 | 3
---+---+---
4 | 5 | 6
---+---+---
7 | 8 | 9
>>> Put your X in any of these positions: 123456789
>>> 1
You went at 1
X | 2 | 3
---+---+---
4 | 5 | 6
---+---+---
7 | 8 | 9
I go at 5
X | 2 | 3
---+---+---
4 | O | 6
---+---+---
7 | 8 | 9
>>> Put your X in any of these positions: 2346789
>>> 7
You went at 7
X | 2 | 3
---+---+---
4 | O | 6
---+---+---
X | 8 | 9
I go at 9
X | 2 | 3
---+---+---
4 | O | 6
---+---+---
X | 8 | O
>>> Put your X in any of these positions: 23468
>>> 4
You went at 4
X | 2 | 3
---+---+---
X | O | 6
---+---+---
X | 8 | O
X wins across [1, 4, 7]