In this article by Ivo Gabe de Wolff, author of the book TypeScript Blueprints, we will build a game in which the computer will play well. The game is called Tic-Tac-Toe. The game is played by two players on a grid, usually three by three. The players try to place their symbols threein a row (horizontal, vertical or diagonal). The first player can place crosses, the second player placescircles. If the board is full, and no one has three symbols in a row, it is a draw.
(For more resources related to this topic, see here.)
The game is usually played on a three by three grid and the target is to have three symbols in a row. To make the application more interesting, we will make the dimension and the row length variable.
We will not create a graphical interface for this application. We will only build the game mechanics and the artificial intelligence(AI). An AI is a player controlled by the computer. If implemented correctly, the computer should never lose on a standard three by three grid. When the computer plays against the computer, it will result in a draft. We will also write various unit tests for the application.
We will build the game as a command line application. That means you can play the game in a terminal. You can interact with the game only with text input.
It's player one's turn!
Choose one out of these options:
1X|X|-+-+- |O|-+-+- | |
2X| |X-+-+- |O|-+-+- | |
3X| |-+-+-X|O|-+-+- | |
4X| |-+-+- |O|X-+-+- | |
5X| |-+-+- |O|-+-+-X| |
6X| |-+-+- |O|-+-+- |X|
7X| |-+-+- |O|-+-+- | |X
Creating the project structure
We will locate the source files in lib and the tests in lib/test. We use gulp to compile the project and AVA to run tests. We can install the dependencies of our project with NPM:
npm init -y
npm install ava gulp gulp-typescript --save-dev
In gulpfile.js, we configure gulp to compile our TypeScript files.
var gulp = require("gulp");
var ts = require("gulp-typescript");
var tsProject = ts.createProject("./lib/tsconfig.json");
gulp.task("default", function() {
return tsProject.src()
.pipe(ts(tsProject))
.pipe(gulp.dest("dist"));
});
Configure TypeScript
We can download type definitions for NodeJS with NPM:
npm install @types/node --save-dev
We must exclude browser files in TypeScript. In lib/tsconfig.json, we add the configuration for TypeScript:
{
"compilerOptions": {
"target": "es6",
"module": "commonjs"
}
}
For applications that run in the browser, you will probably want to target ES5, since ES6 is not supported in all browsers. However, this application will only beexecuted in NodeJS, so we do not have such limitations. You have to use NodeJS 6 or later for ES6 support.
Adding utility functions
Since we will work a lot with arrays, we can use some utility functions. First, we create a function that flattens a two dimensional array into a one dimensional array.
export function flatten<U>(array: U[][]) {
return (<U[]>[]).concat(...array);
}
Next, we create a functionthat replaces a single element of an array with a specified value. We will use functional programming in this article again, so we must use immutable data structures. We can use map for this, since this function provides both the element and the index to the callback. With this index, we can determine whether that element should be replaced.
export function arrayModify<U>(array: U[], index: number, newValue: U) {
return array.map((oldValue, currentIndex) =>
currentIndex === index ? newValue : oldValue);
}
We also create a function that returns a random integer under a certain upper bound.
export function randomInt(max: number) {
return Math.floor(Math.random() * max);
}
We will use these functions in the next sessions.
Creating the models
In lib/model.ts, we will create the model for our game. The model should contain the game state.
We start with the player. The game is played by two players. Each field of the grid contains the symbol of a player or no symbol. We will model the grid as a two dimensional array, where each field can contain a player.
export type Grid = Player[][];
A player is either Player1, Player2 or no player.
export enum Player {
Player1 = 1,
Player2 = -1,
None = 0
}
We have given these members values so we can easily get the opponent of a player.
export function getOpponent(player: Player): Player {
return -player;
}
We create a type to represent an index of the grid. Since the grid is two dimensional, such an index requires two values.
export type Index = [number, number];
We can use this type to create two functions that get or update one field of the grid. We use functional programming in this article, so we will not modify the grid. Instead, we return a new grid with one field changed.
export function get(grid: Grid, [rowIndex, columnIndex]: Index) {
const row = grid[rowIndex];
if (!row) return undefined;
return row[columnIndex];
}
export function set(grid: Grid, [row, column]: Index, value: Player) {
return arrayModify(grid, row,
arrayModify(grid[row], column, value)
);
}
Showing the grid
To show the game to the user, we must convert a grid to a string. First, we will create a function that converts a player to a string, then a function that uses the previous function to show a row, finally a function that uses these functions to show the complete grid.
The string representation of a grid should have lines between the fields. We create these lines with standard characters (+, -, and |). This gives the following result:
X|X|O-+-+- |O|-+-+-X| |
To convert a player to the string, we must get his symbol. For Player1, that is a cross and for Player2, a circle. If a field of the grid contains no symbol, we return a space to keep the grid aligned.
function showPlayer(player: Player) {
switch (player) {
case Player.Player1:
return "X";
case Player.Player2:
return "O";
default:
return "";
}
}
We can use this function to the tokens of all fields in a row. We add a separator between these fields.
function showRow(row: Player[]) {
return row.map(showPlayer).reduce((previous, current) => previous + "|" + current);
}
Since we must do the same later on, but with a different separator, we create a small helper function that does this concatenation based on a separator.
const concat = (separator: string) => (left: string, right: string) =>
left + separator + right;
This function requires the separator and returns a function that can be passed to reduce. We can now use this function in showRow.
function showRow(row: Player[]) {
return row.map(showPlayer).reduce(concat("|"));
}
We can also use this helper function to show the entire grid. First we must compose the separator, which is almost the same as showing a single row. Next, we can show the grid with this separator.
export function showGrid(grid: Grid) {
const separator = "n" + grid[0].map(() =>"-").reduce(concat("+")) + "n";
return grid.map(showRow).reduce(concat(separator));
}
Creating operations on the grid
We will now create some functions that do operations on the grid. These functions check whether the board is full, whether someone has won, and what options a player has.
We can check whether the board is full by looking at all fields. If no field exists that has no symbol on it, the board is full, as every field has a symbol.
export function isFull(grid: Grid) {
for (const row of grid) {
for (const field of row) {
if (field === Player.None) return false;
}
}
return true;
}
To check whether a user has won, we must get a list of all horizontal, vertical and diagonal rows. For each row, we can check whether a row consists of a certain amount of the same symbols on a row. We store the grid as an array of the horizontal rows, so we can easily get those rows. We can also get the vertical rows relatively easily.
function allRows(grid: Grid) {
return [
...grid,
...grid[0].map((field, index) => getVertical(index)),
...
];
function getVertical(index: number) {
return grid.map(row => row[index]);
}
}
Getting a diagonal row requires some more work. We create a helper function that will walk on the grid from a start point, in a certain direction. We distinguish two different kinds of diagonals: a diagonal that goes to the lower-right and a diagonal that goes to the lower-left.
For a standard three by three game, only two diagonals exist. However, a larger grid may have more diagonals. If the grid is 5 by 5, and the users should get three in a row, ten diagonals with a length of at least three exist:
0, 0 to 4, 40, 1 to 3, 40, 2 to 2, 41, 0 to 4, 32, 0 to 4, 24, 0 to 0, 43, 0 to 0, 32, 0 to 0, 24, 1 to 1, 44, 2 to 2, 4
The diagonals that go toward the lower-right, start at the first column or at the first horizontal row. Other diagonals start at the last column or at the first horizontal row. In this function, we will just return all diagonals, even if they only have one element, since that is easy to implement.
We implement this with a function that walks the grid to find the diagonal. That function requires a start position and a step function. The step function increments the position for a specific direction.
function allRows(grid: Grid) {
return [
...grid,
...grid[0].map((field, index) => getVertical(index)),
...grid.map((row, index) => getDiagonal([index, 0], stepDownRight)),
...grid[0].slice(1).map((field, index) => getDiagonal([0, index + 1], stepDownRight)),
...grid.map((row, index) => getDiagonal([index, grid[0].length - 1], stepDownLeft)),
...grid[0].slice(1).map((field, index) => getDiagonal([0, index], stepDownLeft))
];
function getVertical(index: number) {
return grid.map(row => row[index]);
}
function getDiagonal(start: Index, step: (index: Index) => Index) {
const row: Player[] = [];
for (let index = start; get(grid, index) !== undefined; index = step(index)) {
row.push(get(grid, index));
}
return row;
}
function stepDownRight([i, j]: Index): Index {
return [i + 1, j + 1];
}
function stepDownLeft([i, j]: Index): Index {
return [i + 1, j - 1];
}
function stepUpRight([i, j]: Index): Index {
return [i - 1, j + 1];
}
}
To check whether a row has a certain amount of the same elements on a row, we will create a function with some nice looking functional programming. The function requires the array, the player, and the index at which the checking starts. That index will usually be zero, but during recursion we can set it to a different value. originalLength contains the original length that a sequence should have. The last parameter, length, will have the same value in most cases, but in recursion we will change the value. We start with some base cases. Every row contains a sequence of zero symbols, so we can always return true in such a case.
function isWinningRow(row: Player[], player: Player, index: number, originalLength: number, length: number): boolean {
if (length === 0) {
return true;
}
If the row does not contain enough elements to form a sequence, the row will not have such a sequence and we can return false.
if (index + length > row.length) {
return false;
}
For other cases, we use recursion. If the current element contains a symbol of the provided player, this row forms a sequence if the next length—1 fields contain the same symbol.
if (row[index] === player) {
return isWinningRow(row, player, index + 1, originalLength, length - 1);
}
Otherwise, the row should contain a sequence of the original length in some other position.
return isWinningRow(row, player, index + 1, originalLength, originalLength);
}
If the grid is large enough, a row could contain a long enough sequence after a sequence that was too short. For instance, XXOXXX contains a sequence of length three. This function handles these rows correctly with the parameters originalLength and length.
Finally, we must create a function that returns all possible sets that a player can do. To implement this function, we must first find all indices. We filter these indices to indices that reference an empty field. For each of these indices, we change the value of the grid into the specified player. This results in a list of options for the player.
export function getOptions(grid: Grid, player: Player) {
const rowIndices = grid.map((row, index) => index);
const columnIndices = grid[0].map((column, index) => index);
const allFields = flatten(rowIndices.map(
row => columnIndices.map(column =><Index> [row, column])
));
return allFields
.filter(index => get(grid, index) === Player.None)
.map(index => set(grid, index, player));
}
The AI will use this to choose the best option and a human player will get a menu with these options.
Creating the grid
Before the game can be started, we must create an empty grid. We will write a function that creates an empty grid with the specified size.
export function createGrid(width: number, height: number) {
const grid: Grid = [];
for (let i = 0; i < height; i++) {
grid[i] = [];
for (let j = 0; j < width; j++) {
grid[i][j] = Player.None;
}
}
return grid;
}
In the next section, we will add some tests for the functions that we have written. These functions work on the grid, so it will be useful to have a function that can parse a grid based on a string.
We will separate the rows of a grid with a semicolon. Each row contains tokens for each field. For instance, "XXO; O ;X " results in this grid:
X|X|O-+-+- |O|-+-+-X| |
We can implement this by splitting the string into an array of lines. For each line, we split the line into an array of characters. We map these characters to a Player value.
export function parseGrid(input: string) {
const lines = input.split(";");
return lines.map(parseLine);
function parseLine(line: string) {
return line.split("").map(parsePlayer);
}
function parsePlayer(character: string) {
switch (character) {
case "X":
return Player.Player1;
case "O":
return Player.Player2;
default:
return Player.None;
}
}
}
In the next section we will use this function to write some tests.
Adding tests
We will use AVA to write tests for our application. Since the functions do not have side effects, we can easily test them.
In lib/test/winner.ts, we test the findWinner function. First, we check whether the function recognizes the winner in some simple cases.
import test from "ava";
import { Player, parseGrid, findWinner } from "../model";
test("player winner", t => {
t.is(findWinner(parseGrid(" ;XXX; "), 3), Player.Player1);
t.is(findWinner(parseGrid(" ;OOO; "), 3), Player.Player2);
t.is(findWinner(parseGrid(" ; ; "), 3), Player.None);
});
We can also test all possible three-in-a-row positions in the three by three grid. With this test, we can find out whether horizontal, vertical, and diagonal rows are checked correctly.
test("3x3 winner", t => {
const grids = [
"XXX; ; ",
" ;XXX; ",
" ; ;XXX",
"X ;X ;X ",
" X ; X ; X ",
" X; X; X",
"X ; X ; X",
" X; X ;X "
];
for (const grid of grids) {
t.is(findWinner(parseGrid(grid), 3), Player.Player1);
}
});
We must also test that the function does not claim that someone won too often. In the next test, we validate that the function does not return a winner for grids that do not have a winner.
test("3x3 no winner", t => {
const grids = [
"XXO;OXX;XOO",
" ; ; ",
"XXO; ;OOX",
"X ;X ; X "
];
for (const grid of grids) {
t.is(findWinner(parseGrid(grid), 3), Player.None);
}
});
Since the game also supports other dimensions, we should check these too. We check that all diagonals of a four by three grid are checked correctly, where the length of a sequence should be two.
test("4x3 winner", t => {
const grids = [
"X ; X ; ",
" X ; X ; ",
" X ; X; ",
" ;X ; X ",
" X ; X; ",
" X ; X ; ",
"X ; X ; ",
" ; X; X "
];
for (const grid of grids) {
t.is(findWinner(parseGrid(grid), 2), Player.Player1);
}
});
You can of course add more test grids yourself.
Add tests before you fix a bug. These tests should show the wrong behavior related to the bug. When you have fixed the bug, these tests should pass. This prevents the bug returning in a future version.
Random testing
Instead of running the test on some predefined set of test cases, you can also write tests that run on random data. You cannot compare the output of a function directly with an expected value, but you can check some properties of it. For instance, getOptions should return an empty list if and only if the board is full. We can use this property to test getOptions and isFull.
First, we create a function that randomly chooses a player. To higher the chance of a full grid, we add some extra weight on the players compared to an empty field.
import test from "ava";
import { createGrid, Player, isFull, getOptions } from "../model";
import { randomInt } from "../utils";
function randomPlayer() {
switch (randomInt(4)) {
case 0:
case 1:
return Player.Player1;
case 2:
case 3:
return Player.Player2;
default:
return Player.None;
}
}
We create 10000 random grids with this function. The dimensions and the fields are chosen randomly.
test("get-options", t => {
for (let i = 0; i < 10000; i++) {
const grid = createGrid(randomInt(10) + 1, randomInt(10) + 1)
.map(row => row.map(randomPlayer));
Next, we check whether the property that we describe holds for this grid.
const options = getOptions(grid, Player.Player1)
t.is(isFull(grid), options.length === 0);
We also check that the function does not give the same option twice.
for (let i = 1; i < options.length; i++) {
for (let j = 0; j < i; j++) {
t.notSame(options[i], options[j]);
}
}
}
});
Depending on how critical a function is, you can add more tests. In this case, you could check that only one field is modified in an option or that only an empty field can be modified in an option.
Now you can run the tests using gulp && ava dist/test.You can add this to your package.json file. In the scripts section, you can add commands that you want to run. With npm run xxx, you can run task xxx. npm testthat was added as shorthand for npm run test, since the test command is often used.
{
"name": "article-7",
"version": "1.0.0",
"scripts": {
"test": "gulp && ava dist/test"
},
...
Implementing the AI using Minimax
We create an AI based on Minimax. The computer cannot know what his opponent will do in the next steps, but he can check what he can do in the worst-case. The minimum outcome of these worst cases is maximized by this algorithm. This behavior has given Minimax its name.
To learn how Minimax works, we will take a look at the value or score of a grid. If the game is finished, we can easily define its value: if you won, the value is 1; if you lost, -1 and if it is a draw, 0. Thus, for player 1 the next grid has value 1 and for player 2 the value is -1.
X|X|X-+-+-O|O|-+-+-X|O|
We will also define the value of a grid for a game that has not been finished. We take a look at the following grid:
X| |X-+-+-O|O|-+-+-O|X|
It is player 1's turn. He can place his stone on the top row, and he would win, resulting in a value of 1. He can also choose to lay his stone on the second row. Then the game will result in a draft, if player 2 is not dumb, with score 0. If he chooses to place the stone on the last row, player 2 can win resulting in -1. We assume that player 1 is smart and that he will go for the first option. Thus, we could say that the value of this unfinished game is 1.
We will now formalize this. In the previous paragraph, we have summed up all options for the player. For each option, we have calculated the minimum value that the player could get if he would choose that option. From these options, we have chosen the maximum value.
Minimax chooses the option with the highest value of all options.
Implementing Minimax in TypeScript
As you can see, the definition of Minimax looks like you can implement it with recursion. We create a function that returns both the best option and the value of the game. A function can only return a single value, but multiple values can be combined into a single value in a tuple, which is an array with these values.
First, we handle the base cases. If the game is finished, the player has no options and the value can be calculated directly.
import { Player, Grid, findWinner, isFull, getOpponent, getOptions } from "./model";
export function minimax(grid: Grid, rowLength: number, player: Player): [Grid, number] {
const winner = findWinner(grid, rowLength);
if (winner === player) {
return [undefined, 1];
} else if (winner !== Player.None) {
return [undefined, -1];
} else if (isFull(grid)) {
return [undefined, 0];
Otherwise, we list all options. For all options, we calculate the value. The value of an option is the same as the opposite of the value of the option for the opponent. Finally, we choose the option with the best value.
} else {
let options = getOptions(grid, player);
const opponent = getOpponent(player);
return options.map<[Grid, number]>(
option => [option, -(minimax(option, rowLength, opponent)[1])]
).reduce(
(previous, current) => previous[1] < current[1] ? current : previous
);
}
}
When you use tuple types, you should explicitly add a type definition for it. Since tuples are arrays too, an array type is automatically inferred. When you add the tuple as return type, expressions after the return keyword will be inferred as these tuples. For options.map, you can mention the union type as a type argument or by specifying it in the callback function (options.map((option): [Grid, number] => ...);).
You can easily see that such an AI can also be used for other kinds of games. Actually, the minimax function has no direct reference to Tic-Tac-Toe, only findWinner, isFull and getOptions are related to Tic-Tac-Toe.
Optimizing the algorithm
The Minimax algorithm can be slow. Choosing the first set, especially, takes a long time since the algorithm tries all ways of playing the game. We will use two techniques to speed up the algorithm.
First, we can use the symmetry of the game. When the board is empty it does not matter whether you place a stone in the upper-left corner or the lower-right corner. Rotating the grid around the center 180 degrees gives an equivalent board. Thus, we only need to take a look at half the options when the board is empty.
Secondly, we can stop searching for options if we found an option with value 1. Such an option is already the best thing to do.
Implementing these techniques gives the following function:
import { Player, Grid, findWinner, isFull, getOpponent, getOptions } from "./model";
export function minimax(grid: Grid, rowLength: number, player: Player): [Grid, number] {
const winner = findWinner(grid, rowLength);
if (winner === player) {
return [undefined, 1];
} else if (winner !== Player.None) {
return [undefined, -1];
} else if (isFull(grid)) {
return [undefined, 0];
} else {
let options = getOptions(grid, player);
const gridSize = grid.length * grid[0].length;
if (options.length === gridSize) {
options = options.slice(0, Math.ceil(gridSize / 2));
}
const opponent = getOpponent(player);
let best: [Grid, number];
for (const option of options) {
const current: [Grid, number] = [option, -(minimax(option, rowLength, opponent)[1])];
if (current[1] === 1) {
return current;
} else if (best === undefined || current[1] > best[1]) {
best = current;
}
}
return best;
}
}
This will speed up the AI. In the next sections we will implement the interface for the game and we will write some tests for the AI.
Creating the interface
NodeJS can be used to create servers. You can also create tools with a command line interface (CLI). For instance, gulp, NPM and typings are command line interfaces built with NodeJS. We will use NodeJS to create the interface for our game.
Handling interaction
The interaction from the user can only happen by text input in the terminal. When the game starts, it will ask the user some questions about the configuration: width, height, row length for a sequence, and the player(s) that are played by the computer. The highlighted lines are the input of the user.
Tic-Tac-Toe
Width3
Height3
Row length2
Who controls player 1?1You
2Computer1
Who controls player 2?1You
2Computer1
During the game, the game asks the user which of the possible options he wants to do. All possible steps are shown on the screen, with an index. The user can type the index of the option he wants.
X| |-+-+-O|O|-+-+- |X|
It's player one's turn!
Choose one out of these options:
1X|X|-+-+-O|O|-+-+- |X|
2X| |X-+-+-O|O|-+-+- |X|
3X| |-+-+-O|O|X-+-+- |X|
4X| |-+-+-O|O|-+-+-X|X|
5X| |-+-+-O|O|-+-+- |X|X
A NodeJS application has three standard streams to interact with the user. Standard input, stdin, is used to receive input from the user. Standard output, stdout, is used to show text to the user. Standard error, stderr, is used to show error messages to the user. You can access these streams with process.stdin, process.stdout and process.stderr.
You have probably already used console.log to write text to the console. This function writes the text to stdout. We will use console.log to write text to stdout and we will not use stderr.
We will create a helper function that reads a line from stdin. This is an asynchronous task, the function starts listening and resolves when the user hits enter. In lib/cli.ts, we start by importing the types and function that we have written.
import { Grid, Player, getOptions, getOpponent, showGrid, findWinner, isFull, createGrid } from "./model";
import { minimax } from "./ai";
We can listen to input from stdin using the data event. The process sends either the string or a buffer, an efficient way to store binary data in memory. With once, the callback will only be fired once. If you want to listen to all occurrences of the event, you can use on.
function readLine() {
return new Promise<string>(resolve => {
process.stdin.once("data", (data: string | Buffer) => resolve(data.toString()));
});
}
We can easily use readLinein async functions. For instance, we can now create a function that reads, parses and validates a line. We can use this to read the input of the user, parse it to a number, and finally check that the number is within a certain range. This function will return the value if it passes the validator. Otherwise it shows a message and retries.
async function readAndValidate<U>(message: string, parse: (data: string) => U, validate: (value: U) => boolean): Promise<U> {
const data = await readLine();
const value = parse(data);
if (validate(value)) {
return value;
} else {
console.log(message);
return readAndValidate(message, parse, validate);
}
}
We can use this function to show a question where the user has various options. The user should type the index of his answer. This function validates that the index is within bounds. We will show indices starting at 1 to the user, so we must carefully handle these.
async function choose(question: string, options: string[]) {
console.log(question);
for (let i = 0; i < options.length; i++) {
console.log((i + 1) + "t" + options[i].replace(/n/g, "nt"));
console.log();
}
return await readAndValidate(
`Enter a number between 1 and ${ options.length }`,
parseInt,
index => index >= 1 && index <= options.length
) - 1;
}
Creating players
A player could either be a human or the computer. We create a type that can contain both kinds of players.
type PlayerController = (grid: Grid) => Grid | Promise<Grid>;
Next we create a function that creates such a player. For a user, we must first know whether he is the first or the second player. Then we return an async function that asks the player which step he wants to do.
const getUserPlayer = (player: Player) => async (grid: Grid) => {
const options = getOptions(grid, player);
const index = await choose("Choose one out of these options:", options.map(showGrid));
return options[index];
};
For the AI player, we must know the player index and the length of a sequence. We use these variables and the grid of the game to run the Minimax algorithm.
const getAIPlayer = (player: Player, rowLength: number) => (grid: Grid) =>
minimax(grid, rowLength, player)[0];
Now we can create a function that asks the player whether a player should be played by the user or the computer.
async function getPlayer(index: number, player: Player, rowLength: number): Promise<PlayerController> {
switch (await choose(`Who controls player ${ index }?`, ["You", "Computer"])) {
case 0:
return getUserPlayer(player);
default:
return getAIPlayer(player, rowLength);
}
}
We combine these functions in a function that handles the whole game. First, we must ask the user to provide the width, height and length of a sequence.
export async function game() {
console.log("Tic-Tac-Toe");
console.log();
console.log("Width");
const width = await readAndValidate("Enter an integer", parseInt, isFinite);
console.log("Height");
const height = await readAndValidate("Enter an integer", parseInt, isFinite);
console.log("Row length");
const rowLength = await readAndValidate("Enter an integer", parseInt, isFinite);
We ask the user which players should be controlled by the computer.
const player1 = await getPlayer(1, Player.Player1, rowLength);
const player2 = await getPlayer(2, Player.Player2, rowLength);
The user can now play the game. We do not use a loop, but we use recursion to give the player their turns.
return play(createGrid(width, height), Player.Player1);
async function play(grid: Grid, player: Player): Promise<[Grid, Player]> {
In every step, we show the grid. If the game is finished, we show which player has won.
console.log();
console.log(showGrid(grid));
console.log();
const winner = findWinner(grid, rowLength);
if (winner === Player.Player1) {
console.log("Player 1 has won!");
return <[Grid, Player]> [grid, winner];
} else if (winner === Player.Player2) {
console.log("Player 2 has won!");
return <[Grid, Player]>[grid, winner];
} else if (isFull(grid)) {
console.log("It's a draw!");
return <[Grid, Player]>[grid, Player.None];
}
If the game is not finished, we ask the current player or the computer which set he wants to do.
console.log(`It's player ${ player === Player.Player1 ? "one's" : "two's" } turn!`);
const current = player === Player.Player1 ? player1 : player2;
return play(await current(grid), getOpponent(player));
}
}
In lib/index.ts, we can start the game. When the game is finished, we must manually exit the process.
import { game } from "./cli";
game().then(() => process.exit());
We can compile and run this in a terminal:
gulp && node --harmony_destructuring dist
At the time of writing, NodeJS requires the --harmony_destructuring flag to allow destructuring, like [x, y] = z. In future versions of NodeJS, this flag will be removed and you can run it without it.
Testing the AI
We will add some tests to check that the AI works properly. For a standard three by three game, the AI should never lose. That means when an AI plays against an AI, it should result in a draw. We can add a test for this. In lib/test/ai.ts, we import AVA and our own definitions.
import test from "ava";
import { createGrid, Grid, findWinner, isFull, getOptions, Player } from "../model";
import { minimax } from "../ai";
import { randomInt } from "../utils";
We create a function that simulates the whole gameplay.
type PlayerController = (grid: Grid) => Grid;
function run(grid: Grid, a: PlayerController, b: PlayerController): Player {
const winner = findWinner(grid, 3);
if (winner !== Player.None) return winner;
if (isFull(grid)) return Player.None;
return run(a(grid), b, a);
}
We write a function that executes a step for the AI.
const aiPlayer = (player: Player) => (grid: Grid) =>
minimax(grid, 3, player)[0];
Now we create the test that validates that a game where the AI plays against the AI results in a draw.
test("AI vs AI", t => {
const result = run(createGrid(3, 3), aiPlayer(Player.Player1), aiPlayer(Player.Player2))
t.is(result, Player.None);
});
Testing with a random player
We can also test what happens when the AI plays against a random player or when a player plays against the AI. The AI should win or it should result in a draw. We run these multiple times; what you should always do when you use randomization in your test.
We create a function that creates the random player.
const randomPlayer = (player: Player) => (grid: Grid) => {
const options = getOptions(grid, player);
return options[randomInt(options.length)];
};
We write the two tests that both run 20 games with a random player and an AI.
test("random vs AI", t => {
for (let i = 0; i < 20; i++) {
const result = run(createGrid(3, 3), randomPlayer(Player.Player1), aiPlayer(Player.Player2))
t.not(result, Player.Player1);
}
});
test("AI vs random", t => {
for (let i = 0; i < 20; i++) {
const result = run(createGrid(3, 3), aiPlayer(Player.Player1), randomPlayer(Player.Player2))
t.not(result, Player.Player2);
}
});
We have written different kinds of tests:
Tests that check the exact results of single function
Tests that check a certain property of results of a function
Tests that check a big component
Always start writing tests for small components. If the AI tests should fail, that could be caused by a mistake in hasWinner, isFull or getOptions, so it is hard to find the location of the error. Only testing small components is not enough; bigger tests, such as the AI tests, are closer to what the user will do. Bigger tests are harder to create, especially when you want to test the user interface. You must also not forget that tests cannot guarantee that your code runs correctly, it just guarantees that your test cases work correctly.
Summary
In this article, we have written an AI for Tic-Tac-Toe. With the command line interface, you can play this game against the AI or another human. You can also see how the AI plays against the AI. We have written various tests for the application.
You have learned how Minimax works for turn-based games. You can apply this to other turn-based games as well. If you want to know more on strategies for such games, you can take a look at game theory, the mathematical study of these games.
Resources for Article:
Further resources on this subject:
Basic Website using Node.js and MySQL database [article]
Data Science with R [article]
Web Typography [article]
Read more
United States
Great Britain
India
Germany
France
Canada
Russia
Spain
Brazil
Australia
South Africa
Thailand
Ukraine
Switzerland
Slovakia
Luxembourg
Hungary
Romania
Denmark
Ireland
Estonia
Belgium
Italy
Finland
Cyprus
Lithuania
Latvia
Malta
Netherlands
Portugal
Slovenia
Sweden
Argentina
Colombia
Ecuador
Indonesia
Mexico
New Zealand
Norway
South Korea
Taiwan
Turkey
Czechia
Austria
Greece
Isle of Man
Bulgaria
Japan
Philippines
Poland
Singapore
Egypt
Chile
Malaysia
