Build a Tic-Tac-Toe Game Engine With an AI Player in Python

#Python

When you’re a child, you learn to play tic-tac-toe, which some people know as naughts and crosses. The game remains fun and challenging until you enter your teenage years. Then, you learn to program and discover the joy of coding a virtual version of this two-player game. As an adult, you may still appreciate the simplicity of the game by using Python to create an opponent with artificial intelligence (AI). By completing this detailed step-by-step adventure, you’ll build an extensible game engine with an unbeatable computer player that uses the minimax algorithm to play tic-tac-toe. Along the way, you’ll dive into immutable class design, generic plug-in architecture, and modern Python code practices and patterns. In this tutorial, you’ll learn how to: Create a reusable Python library with the tic-tac-toe game engineModel the domain of tic-tac-toe following Pythonic code styleImplement artificial players including one based on the minimax algorithmBuild a text-based console front end for the game with a human playerExplore strategies for performance optimizations

By the end of this tutorial, you’ll have a highly reusable and extensible Python library with an abstract game engine for tic-tac-toe. It’ll encapsulate universal game rules and computer players, including one that never loses due to bare-bones artificial intelligence support. In addition, you’ll create a sample console front end that builds on top of your library and implements a text-based interactive tic-tac-toe game running in the terminal.

Generally, you may mix and choose the players from among a human player, a dummy computer player making moves at random, and a smart computer player sticking to the optimal strategy. You can also specify which player should make the first move, increasing their chances of winning or tying. Later, you’ll be able to adapt your generic tic-tac-toe library for different platforms, such as a windowed desktop environment or a web browser. While you’ll only follow instructions on building a console application in this tutorial, you can find Tkinter and PyScript front end examples in the supporting materials. Note: These front ends aren’t covered here because implementing them requires considerable familiarity with threading, asyncio, and queues in Python, which is beyond the scope of this tutorial. But feel free to study and play around with the sample code on your own. The Tkinter front end is a streamlined version of the same game that’s described in a separate tutorial, which only serves as a demonstration of the library in a desktop environment: Tkinter Front End Unlike the original, it doesn’t look as slick, nor does it allow you to restart the game easily. However, it adds the option to play against the computer or another human player if you want to. The PyScript front end lets you or your friends play the game in a web browser even when they don’t have Python installed on their computer, which is a notable benefit: PyScript Front End If you’re adventurous and know a little bit of PyScript or JavaScript, then you could extend this front end by adding the ability to play online with another human player through the network. To facilitate the communication, you’d need to implement a remote web server using the WebSocket protocol, for instance. Take a look at a working WebSocket client and server example in another tutorial to get an idea of how that might work. It’s worth noting that each of the three front ends demonstrated in this section merely implement a different presentation layer for the same Python library, which provides the underlying game logic and players. There’s no unnecessary redundancy or code duplication across them, thanks to the clear separation of concerns and other programming principles that you’ll practice in this tutorial. Remove ads Project Overview The project that you’re going to build consists of two high-level components depicted in the diagram below: Tic-Tac-Toe Architecture Diagram The first component is an abstract tic-tac-toe Python library, which remains agnostic about the possible ways of presenting the game to the user in a graphical form. Instead, it contains the core logic of the game and two artificial players. However, the library can’t stand on its own, so you’re also going to create a sample front end to collect user input from the keyboard and visualize the game in the console using plain text. You’ll start by implementing the low-level details of the tic-tac-toe library, and then you’ll use those to implement a higher-level game front end in a bottom-up fashion. When you finish this tutorial, the complete file structure resulting will look like this: tic-tac-toe/ │ ├── frontends/ │ │ │ └── console/ │ ├── __init__.py │ ├── __main__.py │ ├── args.py │ ├── cli.py │ ├── players.py │ └── renderers.py │ └── library/ │ ├── src/ │ │ │ └── tic_tac_toe/ │ │ │ ├── game/ │ │ ├── __init__.py │ │ ├── engine.py │ │ ├── players.py │ │ └── renderers.py │ │ │ ├── logic/ │ │ ├── __init__.py │ │ ├── exceptions.py │ │ ├── minimax.py │ │ ├── models.py │ │ └── validators.py │ │ │ └── __init__.py │ └── pyproject.toml The frontends/ folder is meant to house one or more concrete game implementations, such as your text-based console one, while library/ is the home folder for the game library. You can think of both top-level folders as related yet separate projects. Notice that your console front end contains the __main__.py file, making it a runnable Python package that you’ll be able to invoke from the command line using Python’s -m option. Assuming that you changed the current working directory to frontends/ after downloading the complete source code that you’ll be writing in this tutorial, you can start the game with the following command: (venv) $ python -m console Remember that Python must be able to find the tic-tac-toe library, which your front end depends on, on the module search path. The best practice for ensuring this is by creating and activating a shared virtual environment and installing the library with pip. You’ll find detailed instructions on how to do this in the README file in the supporting materials. The tic-tac-toe library is a Python package named tic_tac_toe consisting of two subpackages: tic_tac_toe.game: A scaffolding designed to be extended by front endstic_tac_toe.logic: The building blocks of the tic-tac-toe game You’ll dive deeper into each of them soon. The pyproject.toml file contains the metadata necessary for building and packaging the library. To install the downloaded library or the finished code that you’ll build in this tutorial into an active virtual environment, try this command: (venv) $ python -m pip install --editable library/ During development, you can make an editable install using pip with the -e or --editable flag to mount the library’s source code instead of the built package in your virtual environment. This will prevent you from having to repeat the installation after making changes to the library to reflect them in your front end. Okay, that’s what you’re going to build! But before you get started, check out the prerequisites. Prerequisites This is an advanced tutorial touching on a wide range of Python concepts that you should be comfortable with in order to move on smoothly. Please use the following resources to familiarize yourself with or refresh your memory on a few important topics: Object-oriented programming (OOP)Inheritance and compositionAbstract classesData classesType hintsRegular expressionsCachingRecursion The project that you’re going to build relies solely on Python’s standard library and has no external dependencies. That said, you’ll need at least Python 3.10 or later to take advantage of the latest syntax and features leveraged in this tutorial. If you’re currently using an older Python release, then you can install and manage multiple Python versions with pyenv or try the latest Python release in Docker. Lastly, you should know the rules of the game that you’ll be implementing. The classic tic-tac-toe is played on a three-by-three grid of cells or squares where each player places their mark, an X or an O, in an empty cell. The first player to place three of their marks in a row horizontally, vertically, or diagonally wins the game. Remove ads Step 1: Model the Tic-Tac-Toe Game Domain In this step, you’ll identify the parts that make up a tic-tac-toe game and implement them using an object-oriented approach. By modeling the domain of the game with immutable objects, you’ll end up with modular and composable code that’s easier to test, maintain, debug, and reason about, among several other advantages. For starters, open the code editor of your choice, such as Visual Studio Code or PyCharm, and create a new project called tic-tac-toe, which will also become the name of your project folder. Nowadays, most code editors will give you the option to create a virtual environment for your project automatically, so go ahead and follow suit. If yours doesn’t, then make the virtual environment manually from the command line: $ cd tic-tac-toe/ $ python3 -m venv venv/ This will create a folder named venv/ under tic-tac-toe/. You don’t have to activate your new virtual environment unless you plan to continue working in the current command-line session. Next, scaffold this basic structure of files and folders in your new project, remembering to use underscores (_) instead of dashes (-) for the Python package in the src/ subfolder: tic-tac-toe/ │ ├── frontends/ │ │ │ └── console/ │ ├── __init__.py │ └── __main__.py │ └── library/ │ ├── src/ │ │ │ └── tic_tac_toe/ │ │ │ ├── game/ │ │ └── __init__.py │ │ │ ├── logic/ │ │ └── __init__.py │ │ │ └── __init__.py │ └── pyproject.toml All of the files in the file tree above should be empty at this point. You’ll successively fill them with content and add more files as you go through this tutorial. Start by editing the pyproject.toml file located next to your src/ subfolder. You can paste this fairly minimal packaging configuration for your tic-tac-toe library into it: # pyproject.toml [build-system] requires = ["setuptools", "wheel"] build-backend = "setuptools.build_meta" [project] name = "tic-tac-toe" version = "1.0.0" You specify the required build tools, which Python will download and install if necessary, along with some metadata for your project. Adding the pyproject.toml file to the library lets you build and install it as a Python package into your active virtual environment. Note: The pyproject.toml file is a standard configuration file using the TOML format for specifying minimum build system requirements for Python projects. The concept was introduced in PEP 518 and is now the recommended way of adding packaging metadata and configuration in Python. You’re going to need this to install the tic-tac-toe library into your virtual environment. Open the terminal window and issue the following commands to activate your virtual environment if you haven’t already, and install the tic-tac-toe library using the editable mode: $ source venv/bin/activate (venv) $ python -m pip install --editable library/ Even though there’s no Python code in your library yet, installing it now with the --editable flag will let the Python interpreter import the functions and classes that you’ll be adding shortly straight from your project. Otherwise, every single time you made a change in your source code and wanted to test it, you’d have to remember to build and install the library into your virtual environment again. Now that you have a general structure for your project, you can start implementing some code. By the end of this step, you’ll have all the essential pieces of a tic-tac-toe game in place, including the game logic and state validation, so you’ll be ready to combine them in an abstract game engine. Enumerate the Players’ Marks At the start of the game, each tic-tac-toe player gets assigned one of two symbols, either cross (X) or naught (O), which they use to mark locations on the game board. Since there are only two symbols belonging to a fixed set of discrete values, you can define them within an enumerated type or enum. Using enums is preferable over constants due to their enhanced type safety, common namespace, and programmatic access to their members. Create a new Python module called models in the tic_tac_toe.logic package: tic-tac-toe/ │ └── library/ │ ├── src/ │ │ │ └── tic_tac_toe/ │ │ │ ├── game/ │ │ └── __init__.py │ │ │ ├── logic/ │ │ ├── __init__.py │ │ └── models.py │ │ │ └── __init__.py │ └── pyproject.toml You’ll use this file throughout the rest of this step to define tic-tac-toe domain model objects. Now, import the enum module from Python’s standard library and define a new data type in your models: # tic_tac_toe/logic/models.py import enum class Mark(enum.Enum): CROSS = "X" NAUGHT = "O" The two singleton instances of the Mark class, the enum members Mark.CROSS and Mark.NAUGHT, represent the players’ symbols. By default, you can’t compare a member of a Python enum against its value. For instance, comparing Mark.CROSS == "X" will give you False. This is by design to avoid confusing identical values defined in different places and having unrelated semantics. However, it may sometimes be more convenient to think about the player marks in terms of strings instead of enum members. To make that happen, define Mark as a mixin class of the str and enum.Enum types: # tic_tac_toe/logic/models.py import enum class Mark(str, enum.Enum): CROSS = "X" NAUGHT = "O" This is known as a derived enum, whose members can be compared to instances of the mixed-in type. In this case, you can now compare Mark.NAUGHT and Mark.CROSS to string values. Note: Python 3.10 was the latest release at the time of writing this tutorial, but if you’re using a newer release, then you can directly extend enum.StrEnum, which was added to the standard library in Python 3.11: import enum class Mark(enum.StrEnum): CROSS = "X" NAUGHT = "O" Members of enum.StrEnum are also strings, which means that you can use them almost anywhere that a regular string is expected. Once you assign a given mark to the first player, the second player must be assigned the only remaining and unassigned mark. Because enums are glorified classes, you’re free to put ordinary methods and properties into them. For example, you can define a property of a Mark member that’ll return the other member: # tic_tac_toe/logic/models.py import enum class Mark(str, enum.Enum): CROSS = "X" NAUGHT = "O" @property def other(self) -> "Mark": return Mark.CROSS if self is Mark.NAUGHT else Mark.NAUGHT The body of your property is a single line of code that uses a conditional expression to determine the correct mark. The quotation marks around the return type in your property’s signature are mandatory to make a forward declaration and avoid an error due to an unresolved name. After all, you claim to return a Mark, which hasn’t been fully defined yet. Note: Alternatively, you can postpone the evaluation of annotations until after they’ve been defined: # tic_tac_toe/logic/models.py from __future__ import annotations import enum class Mark(str, enum.Enum): CROSS = "X" NAUGHT = "O" @property def other(self) -> Mark: return Mark.CROSS if self is Mark.NAUGHT else Mark.NAUGHT Adding a special __future__ import, which must appear at the beginning of your file, enables the lazy evaluation of type hints. You’ll use this pattern later to avoid the circular reference problem when importing cross-referencing modules. In Python 3.11, you can also use a universal typing.Self type to avoid the forward declaration in type hints in the first place. To reveal a few practical examples of using the Mark enum, expand the collapsible section below: How to Use MarkShow/Hide You now have a way to represent the available markings that players will leave on the board to advance the game. Next, you’ll implement an abstract game board with well defined locations for those markings. Remove ads Represent the Square Grid of Cells While some people play variants of tic-tac-toe with different numbers of players or different sizes of grids, you’ll stick with the most basic and classic rules. Recall that the game’s board is represented by a three-by-three grid of cells in the classic tic-tac-toe. Each cell can be empty or marked with either a cross or a naught. Because you represent marks with a single character, you can implement the grid using a string of precisely nine characters corresponding to the cells. A cell can be empty, in which case you’ll fill it with the space character (" "), or it can contain the player’s mark. In this tutorial, you’ll store the grid in row-major order by concatenating the rows from top to bottom. For example, with such a representation, you could express the three gameplays demonstrated before with the following string literals: "XXOXO O ""OXXXXOOOX""OOOXXOXX " To better visualize them, you can whip up and run this short function in an interactive Python interpreter session: >>>>>> def preview(cells): ... print(cells[:3], cells[3:6], cells[6:], sep="\n") >>> preview("XXOXO O ") XXO XO O >>> preview("OXXXXOOOX") OXX XXO OOX >>> preview("OOOXXOXX ") OOO XXO XX The function takes a string of cells as an argument and prints it onto the screen in the form of three separate rows carved out with the slice operator from the input string. While using strings to represent the grid of cells is pretty straightforward, it falls short in terms of validating its shape and content. Other than that, plain strings can’t provide some extra, grid-specific properties that you might be interested in. For these reasons, you’ll create a new Grid data type on top of a string wrapped in an attribute: # tic_tac_toe/logic/models.py import enum from dataclasses import dataclass # ... @dataclass(frozen=True) class Grid: cells: str = " " * 9 You define Grid as a frozen data class to make its instances immutable so that once you create a grid object, you won’t be able to alter its cells. This may sound limiting and wasteful at first because you’ll be forced to make many instances of the Grid class instead of just reusing one object. However, the benefits of immutable objects, including fault tolerance and improved code readability, far outweigh the costs in modern computers. By default, when you don’t specify any value for the .cells attribute, it’ll assume a string of exactly nine spaces to reflect an empty grid. However, you can still initialize the grid with the wrong value for cells, ultimately crashing the program. You can prevent this by allowing your objects only to exist if they’re in a valid state. Otherwise, they won’t be created at all, following the fail-fast and always-valid domain model principles. Data classes take control of object initialization, but they also let you run a post-initialization hook to set derived properties based on the values of other fields, for example. You’ll take advantage of this mechanism to perform cell validation and potentially discard invalid strings before instantiating a grid object: # tic_tac_toe/logic/models.py import enum import re from dataclasses import dataclass # ... @dataclass(frozen=True) class Grid: cells: str = " " * 9 def __post_init__(self) -> None: if not re.match(r"^[\sXO]{9}$", self.cells): raise ValueError("Must contain 9 cells of: X, O, or space") Your special .__post_init__() method uses a regular expression to check whether the given value of the .cells attribute is exactly nine characters long and contains only the expected characters—that is, "X", "O", or " ". There are other ways to validate strings, but regular expressions are very compact and will remain consistent with the future validation rules that you’ll add later. Note: The grid is only responsible for validating the syntactical correctness of a string of cells, but it doesn’t understand the higher-level rules of the game. You’ll implement the validation of a particular cell combination’s semantics elsewhere once you gain additional context. At this point, you can add a few extra properties to your Grid class, which will become handy when determining the state of the game: # tic_tac_toe/logic/models.py import enum import re from dataclasses import dataclass from functools import cached_property # ... @dataclass(frozen=True) class Grid: cells: str = " " * 9 def __post_init__(self) -> None: if not re.match(r"^[\sXO]{9}$", self.cells): raise ValueError("Must contain 9 cells of: X, O, or space") @cached_property def x_count(self) -> int: return self.cells.count("X") @cached_property def o_count(self) -> int: return self.cells.count("O") @cached_property def empty_count(self) -> int: return self.cells.count(" ") The three properties return the current number of crosses, naughts, and empty cells, respectively. Because your data class is immutable, its state will never change, so you can cache the computed property values with the help of the @cached_property decorator from the functools module. This will ensure that their code will run at most once, no matter how many times you access these properties, for example during validation. To reveal a few practical examples of using the Grid class, expand the collapsible section below: How to Use GridShow/Hide Using Python code, you modeled a three-by-three grid of cells, which can contain a particular combination of players’ marks. Now, it’s time to model the player’s move so that artificial intelligence can evaluate and choose the best option. Remove ads Take a Snapshot of the Player’s Move An object representing the player’s move in tic-tac-toe should primarily answer the following two questions: Player’s Mark: What mark did the player place?Mark’s Location: Where was it placed? However, in order to have the complete picture, one must also know about the state of the game before making a move. After all, it can be a good or a bad move, depending on the current situation. You may also find it convenient to have the resulting state of the game at hand so that you can assign it a score. By simulating that move, you’ll be able to compare it with other possible moves. Note: A move object can’t validate itself without knowing some of the game details, such as the starting player’s mark, which aren’t available to it. You’ll check whether a given move is valid, along with validating a specific grid cell combination, in a class responsible for managing the game’s state. Based on these thoughts, you can add another immutable data class to your models: