Tic Tac Toe

Tic Tac Toe
===========

0. Quit
1. human v. human   
2. human v. computer
3. computer v. computer

Choose an option: █

Overview

• Text-based Tic Tac Toe game with keyboard input
• Options for human and computer player combinations
• Computer player always plays optimally due to minimax algorithm. It cannot lose.
• Ability to look into the algorithm with Developer Mode

 2 . . .
 1 . . .
 0 . . .
   0 1 2

X: 1 0

 2 . . .
 1 . . .
 0 . X .
   0 1 2

Placing O at (0,0)

 2 . . .
 1 . . .
 0 O X .
   0 1 2

X: █

How to play

• Execute the file in a command line.
  • Should this not work, locally compile the file games/tictactoe.cc in the source code folder. Written in C++17.
• The menu shown at the top appears. Enter on of the options' numbers.
  • If you mistype, the prompt will appear again.
  • When selecting "2. human vs. computer", you get asked which one may begin.
  • Otherwise the game starts immediately.
• The computer executes its moves automatically, but prints whereto. E.g. "Placing O at (0, 0)".
  • If two computers play, the whole game gets printed at once.
• You choose your move by entering the first the x-coordinate followed by a space, then the y-coordinate.
  • Like this: "x y".
  • This prompt is fool-proof too.
  • If two humans play, they take turns inputting coordinates.
• Endgame:
  • If one of you wins by getting three Xs or Os in a straight line, the winner is congratulated.
  • A draw (full board, no-one won) also ends the game.
  • In any case, the program returns to the menu allowing for another round or to quit.

Developer Mode

• By starting the program with the argument -dev, the Developer Mode gets activated.
• It enables the user to look into how the computer players minimax algorithm chooses its moves. See example below.
• At the start of the game, a brief guide for how to use it shows up. Here's a more thorough explanation:
  • When it's a computer player's turn, the "> " prompt shows up.
  • Pressing Enter means the algorithm's internal scores of every legal move are listed.
  • Then the prompt shows up again. Now, Enter means the move is executed and the other player's turn begins.
  • Entering a legal coordinate at either prompts makes the program print a hypothetical board with that move.
  • From there, after another prompt, one Enter prints a list of scores of the opponent and then another Enter returns the program to the actual board.
  • Another coordinate would mean exploring one of the opponent's counter moves.
  • Moving down the search tree by inputting coordinates and moving up again with Enter, any part of it can be explored.
  • The prompt is again fool proof.
• The scores refer to optimal play on both sides.
  • 0 means there will be a draw.
  • [big number] means the player will win.
  • -[big number] means the opponent will win.

Developer Mode on:
At each move, the "> "-prompt enables the following choices:
* Pressing Enter: Show scores for all possible moves / Execute the best move.
* Entering a coordinate `x y`: Explore a specific move by printing a hypothetical board.
    Scores and further moves will refer to that board.

 2 . . .
 1 . . .
 0 . . .
   0 1 2

X: 3 3
X: 1 1

 2 . . .
 1 . X .
 0 . . .
   0 1 2

> 2 2
Hypothetical move of O at (2, 2):

 2 . . O
 1 . X .
 0 . . .
   0 1 2

> 
X's scores of its possible moves:
(0, 0): 0
(1, 0): 0
(2, 0): 0
(0, 1): 0
(2, 1): 0
(0, 2): 0
(1, 2): 0

> 
O's score if it was placed at (2, 2): 0

 2 . . .
 1 . X .
 0 . . .
   0 1 2

O's scores of its possible moves:
(0, 0): 0
(1, 0): -2147483647
(2, 0): 0
(0, 1): -2147483647
(2, 1): -2147483647
(0, 2): 0
(1, 2): -2147483647
(2, 2): 0

> 
Placing O at (0,0)

 2 . . .
 1 . X .
 0 O . .
   0 1 2

X: █

The minimax algorithm

• The minimax algorithm works by assigning to each move a score which is negative that of the score of the optimal countermove. The move with the highest score gets chosen. The optimal countermove is evaluated the same way.
  • A move that wins the game gets maximum score, a draw 0. So if a move results in the optimal opponent winning, then that move gets the negative maximum score.
• By recursively exploring what the optimal countermove would be for each move, the whole game tree is explored before the first move is done.
  • Thus, the algorithm has factorial complexity with respect to the number of squares on the board. So in Tic Tac Toe, the number of paths evaluated is 9! ≈ 363,000. In reality, that number is somewhat smaller in this implementation of minimax because as soon as a winning move is found, the search is stopped.
  • Still, the factorial complexity means that a Tic Tac Toe game is about the biggest game where using this algorithm is still reasonable. On already a 4-by-4 board, up to 16! ≈ 2.1 * 10^13 evaluations would have to be done, 8 orders of magnitude more!

Core Game

• A text-based Gomoku-like game with up to four players was created.
  • The game is played by turns, placing symbols called 'stones' on a squared game board.
  • Stones can only be placed on empty squares and can't remove one another.
  • One wins the game by placing five stones in a vertical, horizontal or diagonal row.
• To start it, execute the file minimal_game via command line.
  • Placing stones is done by inputting the coordinates of the intended square.
  • The input is done by first typing in the x-coordinate then a space then the y-coordinate.
  • Once Enter is pressed, the program prints out the updated game board and the input prompt for the next player.
  • The program stops when one player has won or the board is full.
• Multiple variables can be changed but still only via changing and compiling the source code. These include
  • board size, currently a 30x30 board,
  • number of players, currently 3,
  • the length of a winning sequence, currently 5.
  • Eg. to play TicTacToe one would have to change the variables to a 3x3 board, 2 players and a 3-stone sequence.
• Convenience features:
  • The board features a coordinate grid.
  • A little symbol before the input indicates which player's turn it is.
  • The input prompt is robust against wrong or random inputs or coordinates outside the board or on top of an another stone. It just poses the prompt again.
  • The game does automatically detect and congratulate a winner which finishes the game.