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.
D
<lang d>import std.stdio; import std.conv; import std.string; import std.random; import std.algorithm;
struct Board { int[9] board;
string positionString(int pos) in { assert(pos >= 0); assert(pos < 9); } out(ret) { assert(ret.length == 1); } body { if(board[pos]) return board[pos] == 1 ? "X" : "O"; return to!string(pos + 1); }
string toString() { string lineSeparator = "-+-+-\n"; string row(int start) { return format("%s|%s|%s\n", positionString(start + 0), positionString(start + 1), positionString(start + 2)); }
string ret;
ret ~= row(0); ret ~= lineSeparator; ret ~= row(3); ret ~= lineSeparator; ret ~= row(6);
return ret; }
int[] openPositions() { int[] ret; foreach(i, v; board) { if(!v) ret ~= i; }
return ret; }
bool isAvailable(int position) { if(position < 0 || position >= 9) return false; return board[position] == 0; }
bool finished() { return winner() != -1; }
int winner() { 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) { int desired = board[win[0]]; if(desired == 0) 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; // a winner! }
if(openPositions().length == 0) return 0; // a draw
return -1; // the game is still going }
int suggestMove(int player) out(ret) { assert(ret >= 0); assert(ret < 9); assert(isAvailable(ret)); } body { return randomCover(openPositions(), Random(unpredictableSeed)).front; } }
void main() { writeln("\tTic-tac-toe game player.");
Board board;
int currentPlayer = 1;
while(!board.finished()) { writeln(board);
int move;
if(currentPlayer == 1) { do { writef("Input the index of your move (from %s): ", map!"a+1"(board.openPositions())); readf("%d\n", &move);
move--; // zero based indexing } while(!board.isAvailable(move)); } else { move = board.suggestMove(currentPlayer); }
assert(board.isAvailable(move));
writefln("%s chose %d", currentPlayer == 1 ? "You" : "I", move + 1);
board.board[move] = currentPlayer;
currentPlayer = currentPlayer == 2 ? 1 : 2; }
int winner = board.winner(); if(winner == 0) writeln("\nDraw"); if(winner == 1) writeln("\nYou win!"); if(winner == 2) writeln("\nComputer wins."); }
}</lang> Output:
Tic-tac-toe game player. 1|2|3 -+-+- 4|5|6 -+-+- 7|8|9 Input the index of your move (from [1, 2, 3, 4, 5, 6, 7, 8, 9]): 1 You chose 1 X|2|3 -+-+- 4|5|6 -+-+- 7|8|9 I chose 5 X|2|3 -+-+- 4|O|6 -+-+- 7|8|9 Input the index of your move (from [2, 3, 4, 6, 7, 8, 9]): 2 You chose 2 X|X|3 -+-+- 4|O|6 -+-+- 7|8|9 I chose 4 X|X|3 -+-+- O|O|6 -+-+- 7|8|9 Input the index of your move (from [3, 6, 7, 8, 9]): 3 You chose 3 You win!
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
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]