concept tic - tac - toe in category algorithms

This is an excerpt from Manning's book Classic Computer Science Problems in Java MEAP V04. Login to get full access to this book.

Tic-tac-toe is a simple game, but it can be used to illustrate the same minimax algorithm that can be applied in advanced strategy games like Connect Four, checkers, and chess. We will build a tic-tac-toe AI that plays perfectly using minimax.

With all of these ingredients in place, it is trivial to take the next step and develop a full artificial opponent that can play an entire game of tic-tac-toe. Instead of evaluating a test position, the AI will just evaluate the position generated by each opponent’s move. In the following short code snippet, the tic-tac-toe AI plays against a human opponent who goes first:

Listing 8.12 TicTacToe.java

package chapter8;
 
import java.util.Scanner;
 
public class TicTacToe {
 
    private TTTBoard board = new TTTBoard();
    private Scanner scanner = new Scanner(System.in);
 
    private Integer getPlayerMove() {
        Integer playerMove = -1;
        while (!board.getLegalMoves().contains(playerMove)) {
            System.out.println("Enter a legal square (0-8):");
            Integer play = scanner.nextInt();
            playerMove = play;
        }
        return playerMove;
    }
 
    private void runGame() {
        // main game loop
        while (true) {
            Integer humanMove = getPlayerMove();
            board = board.move(humanMove);
            if (board.isWin()) {
                System.out.println("Human wins!");
                break;
            } else if (board.isDraw()) {
                System.out.println("Draw!");
                break;
            }
            Integer computerMove = Minimax.findBestMove(board, 9);
            System.out.println("Computer move is " + computerMove);
            board = board.move(computerMove);
            System.out.println(board);
            if (board.isWin()) {
                System.out.println("Computer wins!");
                break;
            } else if (board.isDraw()) {
                System.out.println("Draw!");
                break;
            }
        }
    }
 
    public static void main(String[] args) {
        new TicTacToe().runGame();
    }
 
}

copy

By setting the maxDepth parameter of findBestMove() to 9 (it could be 8 really), this tic-tac-toe AI will always see to the very end of the game. (The maximum number of moves in tic-tac-toe is nine, and the AI goes second.) Therefore, it should play perfectly every time. A perfect game is one in which both opponents play the best possible move every turn. The result of a perfect game of tic-tac-toe is a draw. With this in mind, you should never be able to beat the tic-tac-toe AI. If you play your best, it will be a draw. If you make a mistake, the AI will win. Try it out yourself. You should not be able to beat it. Here’s an example run of our program:

This is an excerpt from Manning's book Classic Computer Science Problems in Python. Login to get full access to this book.

As with most of our more complex problems in this book, we will try to make our solution as generic as possible. In the case of adversarial search, that means making our search algorithms non-game-specific. Let’s start by defining some simple base classes that define all of the state our search algorithms will need. Later, we can subclass those base classes for the specific games we are implementing (tic-tac-toe and Connect Four) and feed the subclasses into the search algorithms to make them “play” the games. Here are those base classes:

Listing 8.1. board.py

from __future__ import annotations
from typing import NewType, List
from abc import ABC, abstractmethod

Move = NewType('Move', int)


class Piece:
    @property
    def opposite(self) -> Piece:
        raise NotImplementedError("Should be implemented by subclasses.")


class Board(ABC):
    @property
    @abstractmethod
    def turn(self) -> Piece:
        ...

    @abstractmethod
    def move(self, location: Move) -> Board:
        ...

    @property
    @abstractmethod
    def legal_moves(self) -> List[Move]:
        ...

    @property
    @abstractmethod
    def is_win(self) -> bool:
        ...

    @property
    def is_draw(self) -> bool:
        return (not self.is_win) and (len(self.legal_moves) == 0)

    @abstractmethod
    def evaluate(self, player: Piece) -> float:
        ...


!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":4}],[{\"line\":1,\"ch\":0},{\"line\":1,\"ch\":4}],[{\"line\":2,\"ch\":0},{\"line\":2,\"ch\":4}],[{\"line\":0,\"ch\":16},{\"line\":0,\"ch\":22}],[{\"line\":1,\"ch\":12},{\"line\":1,\"ch\":18}],[{\"line\":2,\"ch\":9},{\"line\":2,\"ch\":15}],[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":4}],[{\"line\":1,\"ch\":0},{\"line\":1,\"ch\":4}],[{\"line\":2,\"ch\":0},{\"line\":2,\"ch\":4}],[{\"line\":0,\"ch\":16},{\"line\":0,\"ch\":22}],[{\"line\":1,\"ch\":12},{\"line\":1,\"ch\":18}],[{\"line\":2,\"ch\":9},{\"line\":2,\"ch\":15}],[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":4}],[{\"line\":1,\"ch\":0},{\"line\":1,\"ch\":4}],[{\"line\":2,\"ch\":0},{\"line\":2,\"ch\":4}],[{\"line\":0,\"ch\":16},{\"line\":0,\"ch\":22}],[{\"line\":1,\"ch\":12},{\"line\":1,\"ch\":18}],[{\"line\":2,\"ch\":9},{\"line\":2,\"ch\":15}],[{\"line\":4,\"ch\":15},{\"line\":4,\"ch\":21}],[{\"line\":7,\"ch\":0},{\"line\":7,\"ch\":5}],[{\"line\":10,\"ch\":63},{\"line\":10,\"ch\":68}],[{\"line\":13,\"ch\":0},{\"line\":13,\"ch\":5}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}],[{\"line\":10,\"ch\":8},{\"line\":10,\"ch\":13}],[{\"line\":10,\"ch\":34},{\"line\":10,\"ch\":72}],[{\"line\":7,\"ch\":0},{\"line\":7,\"ch\":5}],[{\"line\":10,\"ch\":63},{\"line\":10,\"ch\":68}],[{\"line\":13,\"ch\":0},{\"line\":13,\"ch\":5}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}],[{\"line\":35,\"ch\":8},{\"line\":35,\"ch\":14}],[{\"line\":0,\"ch\":25},{\"line\":0,\"ch\":28}],[{\"line\":35,\"ch\":16},{\"line\":35,\"ch\":19}],[{\"line\":35,\"ch\":33},{\"line\":35,\"ch\":36}],[{\"line\":9,\"ch\":4},{\"line\":9,\"ch\":7}],[{\"line\":16,\"ch\":4},{\"line\":16,\"ch\":7}],[{\"line\":20,\"ch\":4},{\"line\":20,\"ch\":7}],[{\"line\":25,\"ch\":4},{\"line\":25,\"ch\":7}],[{\"line\":30,\"ch\":4},{\"line\":30,\"ch\":7}],[{\"line\":34,\"ch\":4},{\"line\":34,\"ch\":7}],[{\"line\":38,\"ch\":4},{\"line\":38,\"ch\":7}]]"}
!@%STYLE%@!

copy

The Move type will represent a move in a game. It is, at heart, just an integer. In games like tic-tac-toe and Connect Four, an integer can represent a move by indicating a square or column where a piece should be placed. Piece is a base class for a piece on the board in a game. It will also double as our turn indicator. This is why the opposite property is needed. We need to know whose turn follows a given turn.

Tic-tac-toe is a simple game, but it can be used to illustrate the same minimax algorithm that can be applied in advanced strategy games like Connect Four, checkers, and chess. We will build a tic-tac-toe AI that plays perfectly using minimax.

8.2.3. Testing minimax with tic-tac-toe

Tic-tac-toe is such a simple game that it’s easy for us, as humans, to figure out the definite correct move in a given position. This makes it possible to easily develop unit tests. In the following code snippet, we will challenge our minimax algorithm to find the correct next move in three different tic-tac-toe positions. The first is easy and only requires it to think to the next move for a win. The second requires a block; the AI must stop its opponent from scoring a victory. The last is a little bit more challenging and requires the AI to think two moves into the future.