Tic-tac-toe in Erlang — introduction
This is part of an Erlang sample-code review built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here. The source code and this tutorial are organized into these sections:
- Introduction (this page)
- Top-level loop
- User input
- Board display
- Board abstraction
- Game abstraction
- Next move calculations and predictions
- Predicted outcome abstraction
- Utilities to introduce randomness
- Macros for testing and debugging
Introduction
I recently programmed tic-tac-toe using Erlang, and I thought I’d offer to anyone looking for sample code. Here’s the source.
Tic-tac-toe is a good choice for an example program. It’s a simple yet still non-trivial game, so it’s interesting. Everyone knows the rules, which makes it easy to understand the architecture and code design. Deciding the next move involves some analysis and decision making. And it touches on a lot of features.
This version of tic-tac-toe has a standard-IO text interface, which means it reads and displays to the console. That’s right: no graphics, no windows, no mouse. It prints the board using fixed-width scrolling text, and it asks for keyboard commands. State of the art — in 1970.
It wouldn’t be hard to kick together a GS (Erlang Graphic System module) interface. Maybe I’ll do that sometime.
Running the program
To run this program first you have to install Erlang on your computer. You might also want to look at the tutorial.
When you can get an Erlang shell started you can run tic-tac-toe. Assuming I’ve saved tic.erl at c:/examples/erlang/tic.erl, here’s what it looks like to load the module (tic) and start the game.
Erlang (BEAM) emulator version 5.6.5 [smp:2] [async-threads:0]
Eshell V5.6.5 (abort with ^G)
1> c( 'c:/examples/erlang/tic').
{ok,tic}
2> tic:play( ).
Welcome to tic-tac-toe, the game that predicts
the outcomes of every move and lets you erase
X's and O's and skip turns.
Starting a new game.
[] []
[] []
1 [] 2 [] 3
[] []
[] []
===============##===============##===============
[] []
[] []
4 [] 5 [] 6
[] []
[] []
===============##===============##===============
[] []
[] []
7 [] 8 [] 9
[] []
[] []
It is X's turn to move.
What do you want to do (h=help, q=quit)?
At this point the game stops, waiting for me to type something and hit return. I’ll ask for help.
What do you want to do (h=help, q=quit)? h
Please enter one of the following:
q - quit
h - help, show this message
g - start a new game
b - show a simple board
n - show the board with open spots numbered
p - show a board with predicted outcomes
1-9 (a single digit)
- choose X's next move
a - automatically choose X's next move
s - skip X's next move
What do you want to do (h=help, q=quit)?
There are three generic commands: quit, help, and start a new new game. And then there are three options that affect how the board is printed. And finally there are 3 ways to make a move.
Let’s let the computer move first. We type ‘a’ and hit return.
It is X's turn to move.
What do you want to do (h=help, q=quit)? a
Automatically selecting X's next move.
[] []
1 Leads to [] 2 Loses in [] 3 Loses in
CAT game [] three turns [] three turns
[] after this [] after this
[] []
===============##===============##===============
XXX XXX [] []
XX XX [] 5 Leads to [] 6 Leads to
XXX [] CAT game [] CAT game
XX XX [] []
XXX XXX [] []
===============##===============##===============
[] []
7 Leads to [] 8 Loses in [] 9 Loses in
CAT game [] three turns [] three turns
[] after this [] after this
[] []
It is O's turn to move.
What do you want to do (h=help, q=quit)?
As you can see, this isn’t just simple tic-tac-toe. The computer is predicting the outcome of each of the possible next moves for ‘O’. If ‘O’ plays in the center (position 5) and neither ‘X’ nor ‘O’ make any mistakes, this will end up a cat game. But if ‘O’ plays position 2 (just above the center) then ‘X’ can win in three more moves.
Let’s put ‘O’ at position 2 and then let the computer choose all the future moves for both ‘X’ and ‘O’.
It is O's turn to move.
What do you want to do (h=help, q=quit)? 2
Marking O at position 2.
[] OOOOO []
1 Wins in [] OOO OOO [] 3 Leads to
three turns [] OOO OOO [] CAT game
after this [] OOO OOO []
[] OOOOO []
===============##===============##===============
XXX XXX [] []
XX XX [] 5 Wins in [] 6 Loses in
XXX [] three turns [] three turns
XX XX [] after this [] after this
XXX XXX [] []
===============##===============##===============
[] []
7 Loses in [] 8 Leads to [] 9 Leads to
three turns [] CAT game [] CAT game
after this [] []
[] []
It is X's turn to move.
What do you want to do (h=help, q=quit)? a
Automatically selecting X's next move.
XXX XXX [] OOOOO []
XX XX [] OOO OOO [] 3 Loses
XXX [] OOO OOO [] after this
XX XX [] OOO OOO []
XXX XXX [] OOOOO []
===============##===============##===============
XXX XXX [] []
XX XX [] 5 Loses [] 6 Loses
XXX [] after this [] after this
XX XX [] []
XXX XXX [] []
===============##===============##===============
[] []
7 Loses in [] 8 Loses [] 9 Loses
two turns [] after this [] after this
after this [] []
[] []
It is O's turn to move.
What do you want to do (h=help, q=quit)? a
Automatically selecting O's next move.
XXX XXX [] OOOOO []
XX XX [] OOO OOO [] 3 Loses in
XXX [] OOO OOO [] two turns
XX XX [] OOO OOO [] after this
XXX XXX [] OOOOO []
===============##===============##===============
XXX XXX [] []
XX XX [] 5 Wins in [] 6 Loses in
XXX [] next turn [] two turns
XX XX [] after this [] after this
XXX XXX [] []
===============##===============##===============
OOOOO [] []
OOO OOO [] 8 Leads to [] 9 Loses in
OOO OOO [] CAT game [] two turns
OOO OOO [] [] after this
OOOOO [] []
It is X's turn to move.
What do you want to do (h=help, q=quit)? a
Automatically selecting X's next move.
XXX XXX [] OOOOO []
XX XX [] OOO OOO [] 3 Loses
XXX [] OOO OOO [] after this
XX XX [] OOO OOO []
XXX XXX [] OOOOO []
===============##===============##===============
XXX XXX [] XXX XXX []
XX XX [] XX XX [] 6 Loses
XXX [] XXX [] after this
XX XX [] XX XX []
XXX XXX [] XXX XXX []
===============##===============##===============
OOOOO [] []
OOO OOO [] 8 Loses [] 9 Loses
OOO OOO [] after this [] after this
OOO OOO [] []
OOOOO [] []
It is O's turn to move.
What do you want to do (h=help, q=quit)? a
Automatically selecting O's next move.
XXX XXX [] OOOOO []
XX XX [] OOO OOO [] 3 Loses
XXX [] OOO OOO [] after this
XX XX [] OOO OOO []
XXX XXX [] OOOOO []
===============##===============##===============
XXX XXX [] XXX XXX []
XX XX [] XX XX [] 6 WINNING
XXX [] XXX [] MOVE!
XX XX [] XX XX []
XXX XXX [] XXX XXX []
===============##===============##===============
OOOOO [] OOOOO []
OOO OOO [] OOO OOO [] 9 WINNING
OOO OOO [] OOO OOO [] MOVE!
OOO OOO [] OOO OOO []
OOOOO [] OOOOO []
It is X's turn to move.
What do you want to do (h=help, q=quit)? a
Automatically selecting X's next move.
XXX XXX [] OOOOO []
XX XX [] OOO OOO []
XXX [] OOO OOO [] 3
XX XX [] OOO OOO []
XXX XXX [] OOOOO []
===============##===============##===============
XXX XXX [] XXX XXX [] XXX XXX
XX XX [] XX XX [] XX XX
XXX [] XXX [] XXX
XX XX [] XX XX [] XX XX
XXX XXX [] XXX XXX [] XXX XXX
===============##===============##===============
OOOOO [] OOOOO []
OOO OOO [] OOO OOO []
OOO OOO [] OOO OOO [] 9
OOO OOO [] OOO OOO []
OOOOO [] OOOOO []
X is the winner.
What do you want to do (h=help, q=quit)? q
Thanks for playing!
ok
3>
Pretty brilliant, eh? OK, maybe not. I know tic-tac-toe isn’t exactly cutting-edge game theory, but I enjoyed programming it, and I hope you enjoy it too.
Thanks for reading!
Tic-tac-toe in Erlang — top-level loop
This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here. The source file and this tutorial are organized as follows:
- Introduction
- Top-level loop (this page)
- User input
- Board display
- Board abstraction
- Game abstraction
- Next move calculations and predictions
- Predicted outcome abstraction
- Utilities to introduce randomness
- Macros for testing and debugging
Top-level loop
This is the top-level loop that plays the tic-tac-toe game. It is a common pattern, a read-eval-print loop that reads the user’s request, carries out the user command, displays the board, and repeats.
Interface
The top-level loop section implements play(), the exported function that plays the game of tic-tac-toe.
play( )
Plays tic-tac-toe with the user. Exported from tic module.
Source code
Here’s the Erlang source code for the top-level loop section of the tic.erl file.
% --------------------------------------------------------------
% Export Function - play()
% --------------------------------------------------------------
% play( )
%
% Plays a game of tic-tac-toe, printing the board and reading
% user instructions to/from standard IO.
%
% This could print some final statistics.
play( ) ->
% We use random:uniform(N) to break ties.
% Take this out (or replace it with something that sets the
% seed) if you want exact reproducability.
randomize_random_seed( ),
% The opening message.
write_line( ),
write_line( "Welcome to tic-tac-toe, the game that predicts"),
write_line( "the outcomes of every move and lets you erase"),
write_line( "X's and O's and skip turns."),
% Play until the user quits.
play_new_game( init_game( )),
% The closing message.
write_line( ),
write_line( "Thanks for playing!"),
write_line( ),
ok.
% --------------------------------------------------------------
% play_new_game( Game )
%
% Plays a new game created by the caller.
play_new_game( Game ) ->
write_line( ),
write_line( "Starting a new game."),
case catch game_loop( Game) of
quit -> ok;
{new_game, Game_final} ->
play_new_game( init_game( Game_final))
end.
% --------------------------------------------------------------
% game_loop( Game )
%
% Displays the board, gets user input, changes the board,
% and calls itself tail-recursivly with the changed board.
game_loop( Game ) ->
print_board( Game),
game_loop(
case get_next_move( Game) of
quit -> throw( quit);
new_game -> throw( {new_game, Game});
Option when
Option == simple;
Option == number;
Option == predict ->
set_game_print_option( Game, Option);
skip ->
skip_game_next_turn( Game);
automatic ->
automatic_game_next_turn( Game);
{mark, Pos} ->
mark_game_next_turn( Game, Pos);
{erase, Pos} ->
erase_game_next_turn( Game, Pos)
end).
% --------------------------------------------------------------
% skip_game_next_turn( Game )
%
% Called when the user asks to skip a turn.
% Never called on a cat game or a game that is already won.
%
% Returns a new #game{} object where the state is flipped
% between "it is X's turn" and "it is O's turn".
% May also calculate new predicted outcomes for the board.
skip_game_next_turn( Game ) ->
set_game_state_board(
Game,
case get_game_state( Game) of
x_next -> o_next;
o_next -> x_next
end,
get_game_board( Game)).
% --------------------------------------------------------------
% automatic_game_next_turn( Game )
%
% Called when the user asks the computer to choose the
% next move.
%
% Returns a #game{} with the new move recorded.
automatic_game_next_turn( Game ) ->
mark_game_next_turn( Game,
get_board_best_predicted_position(
get_game_board( Game))).
% --------------------------------------------------------------
% mark_game_next_turn( Game, Position )
%
% Called when the user selects a board position to mark
% for the next move.
%
% Returns a re-calculated #game{}.
mark_game_next_turn( Game, Pos ) ->
State_old = get_game_state( Game),
Board_old = clear_board_predicted_outcomes(
get_game_board( Game)),
?m_assert( (State_old == x_next) or (State_old == o_next)),
?m_assert( get_board_mark( Board_old, Pos) == empty),
{ Xo, State_win, State_flip } =
case State_old of
x_next -> { x_mark, x_winner, o_next };
o_next -> { o_mark, o_winner, x_next }
end,
Board_marked = mark_board( Board_old, Pos, Xo),
set_game_state_board(
Game,
case is_board_won( Board_marked, Xo) of
true -> State_win;
false ->
case is_board_full( Board_marked) of
true -> cat_game;
false -> State_flip
end
end,
Board_marked).
% --------------------------------------------------------------
% erase_game_next_turn( Game, Position )
%
% Erases the X or O mark on the board at position.
%
% Returns a re-calculated #game{}.
erase_game_next_turn( Game, Pos ) ->
State_old = get_game_state( Game),
Board_old = clear_board_predicted_outcomes(
get_game_board( Game)),
Xo_old = get_board_mark( Board_old, Pos),
?m_assert( (Xo_old == x_mark) or (Xo_old == o_mark)),
Board_erased = mark_board( Board_old, Pos, empty),
set_game_state_board(
Game,
case {State_old, Xo_old} of
{cat_game, x_mark} -> x_next;
{cat_game, o_mark} -> o_next;
{x_winner, o_mark} -> x_winner;
{o_winner, x_mark} -> o_winner;
{x_next , x_mark} -> x_next;
{o_next , x_mark} -> x_next;
{x_next , o_mark} -> o_next;
{o_next , o_mark} -> o_next;
{x_winner, x_mark} ->
case is_board_won( Board_erased, x_mark) of
true -> x_winner;
false -> x_next
end;
{o_winner, o_mark} ->
case is_board_won( Board_erased, o_mark) of
true -> o_winner;
false -> o_next
end
end,
Board_erased).
Tic-tac-toe in Erlang — predicted outcome abstraction
This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here. The source file and this tutorial are organized into these sections:
- Introduction
- Top-level loop
- User input
- Board display
- Board abstraction
- Game abstraction
- Next move calculations and predictions
- Predicted outcome abstraction (this page)
- Utilities to introduce randomness
- Macros for testing and debugging
Predicted outcome abstraction
This section provides an enumeration of possible (predicted) outcomes. Predicted outcomes are implemented as integers, although no code outside of this section has to know that. The functions in this section (along with operators == and /=) provide a complete abstraction for the predicted outcome type.
There are only a few possible predicted outcomes, such as the game will be won in one move or the game will be lost in 2 moves. We use these integer values to represent them.
| 0 | No prediction. You get this if you do a limited search for a winner and can draw no conclusions, or if you search the board space enough to conclude the game will end in a tie (a cat game). An empty spot in the board can also be marked with the atom empty, which means we don’t have a predicted outcome for that spot. We treat empty the same as a predicted cat game, although you could argue this is not optimal. |
| -1 | The next mark can win the game. |
| -2 | The current-turn mark will win on the 2nd turn after this. So if it’s X’s turn, we expect a move by X, followed by an O, followed by the winning X (3 half-turns or ply). |
| -3 | The current-turn mark can win in 3 turns (5 half-turns). |
| +1 | The current-turn mark will lose in this words. Say it is X’s turn, the X will play first, followed by a winning move by O (2 half-turns or ply). |
| +2 | If it’s X’s turn, the moves will be: X, O, X, and O (winning move, X loses in 4 half-turns). |
| +3 | The current-turn mark will lose in 3 turns (6 half-turns). |
In tic-tac-toe you never end up with win/loss preditions beyond 3 turns, although the code uses higher-move predictions (win-in-5) when exploring the board space. These higher-move preditions always resolve to cat games when you work them out. So for tic-tac-toe you never have to look ahead more than three turns (6 half-turns). If you haven’t found an unambiguous win or loss after three turns, you can assume you will never find one.
An enumerated type is one without much structure (few properties), and usually with a small number of possible values. It usually has a natural order and an increment function. In C and C++ an enumerated type (enum) is also immutable, but in Erlang everything is immutable.
Interface
The functional interface to access and manipulate predicted outcomes is described here.
is_outcome_valid( Predicted_outcome_or_not )
Returns true if Predicted_outcome_or_not is a legal predicted-outcome value. Returns false for all other values. Used (with assert) for type checking.
undecided_outcome( )
Returns the undecided outcome (represented by the integer zero).
is_outcome_undecided( Predicted_outcome )
Returns true if Predicted_outcome is undecided (integer zero).
is_outcome_a_win( Predicted_outcome )
Returns true if Predicted_outcome is a win, false if it is a loss or undecided.
is_outcome_a_loss( Predicted_outcome )
Returns true if Predicted_outcome is a loss, false if it is a win or undecided.
outcome_turn_count( Predicted_outcome )
Tells you how many turns it will take to reach an outcome. If Predicted_outcome is win in 2 (which is -2), outcome_turn_count(..) will return 2. If Predicted_outcome is lose in 1 (+1), outcome_turn_count(..) is 1. outcome_turn_count( undecided_outcome( )) is zero.
next_outcome( Predicted_outcome )
This is used to enumerate the outcomes as we search the game space. The enumeration order is undecided, win in 1, lose in 1, win in 2, lose in 2, etc.
is_first_outcome_better( A, B )
Returns true if A is a better prediction than B. Winning predictions are better than cat-game predictions, which are better than losing predictions. Winning in 1 move is better than winning in 2, and losing in 3 is better than losing in 2. Returns false if (A == B).
This defines an order for predicted outcomes. The order is different than the enumeration order from next_outcome(..).
This defines an order for predicted outcomes. The order is different than the enumeration order from next_outcome(..).
Source code
Here is the code that wraps up the predicted outcome enumerated type.
% --------------------------------------------------------------
% Predicted Outcomes
% --------------------------------------------------------------
%
% Abstraction and definition of predicted_outcome.
% Predicted_outcome is an enumerated type.
%
% Predicted outcomes are integers (negative and positive).
% They are always predictions for the mark whose turn it is,
% so if X is moving next and the prediction is "lose in 1",
% it means that X is expected to lose (and O to win) when
% O moves next.
%
% Suggestions:
% Right now we treat "unknown outcome" the same as
% "predict outcome to be a tie". Both are the value 0.
% It'd probably be an improvement to separate these
% and choose "predict tie" over "unknown" while still
% considering "unknown" a better choice than "predict a
% loss in 4 moves".
%
% We can go farther and keep track of how far we've
% searched before comming up with "unknown". So we might
% have "completely unknown", which means we haven't looked
% ahead at all, and "unknown after searching 2 deep" which
% means searching 2 moves forward in the game space did not
% reveal either a win or loss. Maybe it's clearer to think
% "neither win nor loss predicted" instead of "unknown".
%
% If we are faced with a board where we'll lose no matter
% what (the other side can make three-in-a-row two different
% ways), the automatic mover will just choose a random move
% right now. But it'd be better if it choose to at least
% block one of the three-in-a-rows.
%
% So another thing we could add to the predicted outcomes
% is how many losing paths are blocked by the next move,
% and how many winning paths are opened up. So even if we
% were bound to lose we could still make the computer look
% like it's fighting the lost cause to the bitter end.
%
% We try to avoid automatically choosing the center spot
% right now unless it's clearly the best move. This is
% because it makes the game boring. An interesting game is
% one where there are more potential (and longer) paths to
% victory. A boring game is where all the moves are forced.
% We could come up with a tie-breaking factor in the
% predicted outcome that steered us away from boring
% choices (when all other factors were equal).
% --------------------------------------------------------------
% is_outcome_valid( Predicted_outcome )
%
% These integers are small because tic-tac-toe is so limited.
% -5 really never happens -- it'd be a prediction for a
% winner 9 half-moves from now.
% This is only used in asserts.
-ifndef( NODEBUG ).
is_outcome_valid( P ) ->
is_integer( P) andalso (P >= -5) andalso (P =< 4).
-endif.
% --------------------------------------------------------------
% undecided_outcome( )
% is_outcome_undecided( P )
%
% Undecided means we search for a win/loss outcome and did
% not find one. Since we always search all the way to a full
% board in tic-tac-toe, undecided_outcome( ) is the same
% as predicting a cat game.
undecided_outcome( ) -> 0.
is_outcome_undecided( P ) -> P == 0.
% --------------------------------------------------------------
% is_outcome_a_win( P )
% is_outcome_a_loss( P )
%
% Says whether we are predicting a win or a loss.
is_outcome_a_win( P ) -> P < 0.
is_outcome_a_loss( P ) -> P > 0.
% --------------------------------------------------------------
% outcome_turn_count( P )
%
% Integer saying in how many turns we are predicting a win or
% loss. Zero if we're predicting neither.
outcome_turn_count( P ) ->
?m_assert( is_outcome_valid( P)),
abs( P ).
% --------------------------------------------------------------
% next_outcome( P )
%
% Returns this sequence of integers, starting at undecided:
% 0 (undecided), -1 (win), 1 (loss), -2, 2, -3, 3 ..etc..
next_outcome( P ) ->
?m_assert( is_outcome_valid( P)),
?m_confirm( is_outcome_valid,
- ( if P < 0 -> P;
true -> P + 1
end
)
).
% --------------------------------------------------------------
% is_first_outcome_better( A, B )
%
% This is a less-than, not a less-than-or-equal test.
% If A and B are equal, this returns false.
%
% Outcomes from best to worst are:
% -1 - win next move
% -2 - win in 2 moves
% -3 - win in 3 moves
% .. etc ..
% 0 - tie game (or no prediction)
% +4 - lose in 4
% +3 - lose in 3
% +2 - lose in 2
% +1 - lose immediately
%
% What's best for X is always worst for O, and vice versa.
is_first_outcome_better( A, B ) ->
?m_assert( is_outcome_valid( A)),
?m_assert( is_outcome_valid( B)),
% Negative numbers are better since they predict a win.
% -1 is the best since it predicts an immediate win.
% 0 means a tie game, so it is better than a positive
% integer which means a loss.
% 3 is better than 1 since 1 means an immediate loss.
case { A < 0, B < 0 } of
{ true , false } -> true ;
{ false, true } -> false;
{ true , true } -> A > B;
{ false, false } ->
if
B == 0 -> false;
A == 0 -> true ;
true -> A > B
end
end.