Chapter 6. Board Games AI

In this chapter, you will learn a family of algorithms for developing AI for board games:

• Working with the game-tree class

• Introducing Minimax

• Negamaxing

• AB Negamaxing

• Negascouting

• Implementing a tic-tac-toe rival

• Implementing a checkers rival

Introduction

In this chapter, you will learn about a family of algorithms for developing board game techniques to create artificial intelligence. They are based on the principle of a game tree (graph) that spans as we evaluate a state and decide to visit its neighbors. They also take into account board games for two rivals. But with a little bit of work, some of them can be extended to more players.

Working with the game-tree class

The game state can be represented in a lot of different ways, but you will learn how to create extendible classes in order to use the high-level board AI algorithms for different circumstances.

Getting ready…

It is important to be clear on object-oriented programming, specifically on inheritance and polymorphism. This is because we'll be creating generic functions that can be applied to a number of board game decisions and then writing specific subclasses that inherit and further specify these functions.

How to do it…

We will build two classes in order to represent game-tree with the help of the following steps:

1. Create the abstract class Move:

   using UnityEngine;
   using System.Collections;
   
   public abstract class Move
   {
       
   }

2. Create the pseudo-abstract class Board:

   using UnityEngine;
   using System.Collections;
   
   public class Board
   {
       protected int player;
       //next steps here
   }

3. Define the default constructor:

   public Board()
   {
       player = 1;
   }

4. Implement the virtual...

Introducing Minimax

Minimax is an algorithm based on the decision to minimize the possible loss for the worst case (maximum loss). Besides game development and game theory, Minimax is a decision rule and is also used in statistics, decision theory, and philosophy.

This technique was originally formulated for the two-player zero-sum game theory, meaning that one player's win is the opponent's loss. However, in this case, it is flexible enough to handle more than two players.

Getting ready…

It is important to know the difference between a dynamic member function and a static member function, as well as recursion. A dynamic member function is bound to the instance of the class, while the static member function is bound to the class itself. The static method allows us to call it without instantiating an object. This is great for general-purpose algorithms, such as the one developed in this recipe.

In the case of recursion, it's not always clear that (unlike iteration) this is an iterative process...

Negamaxing

When we have a zero-sum game with only two players involved, we are able to improve Minimax, taking advantage of the principle that one player's loss is the other's gain. In this way, it is able to provide the same results as the Minimax algorithm. However, it does not track whose move it is.

Getting ready…

It is important to know the difference between a dynamic member function and a static member function, as well as recursion. A dynamic member function is bound to the instance of the class, while a static member function is bound to the class itself. The static method allows us to call it without instantiating an object. This is great for general-purpose algorithms, such as the one we are developing in this recipe.

In the case of recursion, it's not always clear that (unlike iteration) this is an iterative process that requires a base case (also called the stop condition) and a recursive case (the one to keep iterating).

How to do it…

We will add a new function to the BoardAI class...

AB Negamaxing

There is still room for improving the Negamax algorithm. Despite its efficiency, the downside of the Negamax algorithm is that it examines more nodes than necessary (for example, board positions). To overcome this problem, we use Negamax with a search strategy called alpha-beta pruning.

Getting ready…

It is important to know the difference between a dynamic member function and a static member function, as well as recursion. A dynamic member function is bound to the instance of the class, while the static member function is bound to the class itself. The static method allows us to call it without instantiating an object. This is great for general-purpose algorithms, such as the one we are developing in this recipe.

In the case of recursion, it's not always clear that (unlike iteration) this is an iterative process that requires a base case (also called the stop condition) and a recursive case (the one to keep iterating).

How to do it…

We will add a new function to the BoardAI class...

Negascouting

Including a search strategy also makes room for new challenges. Negascouting is the result of narrowing the search by improving the pruning heuristic. It is based on a concept called a search window, which is the interval between the alpha and beta values. So, reducing the search window increases the chance of a branch being pruned.

Getting ready…

It is important to know the difference between a dynamic member function and a static member function, as well as recursion. A dynamic member function is bound to the instance of the class, while the static member function is bound to the class itself. The static method allows us to call it without instantiating an object. This is great for general-purpose algorithms, such as the one we are developing in this recipe.

In the case of recursion, it's not always clear that (unlike iteration) this is an iterative process that requires a base case (also called the stop condition) and a recursive case (the one to keep iterating).

How to do it...

Implementing a tic-tac-toe rival

In order to make use of the previous recipes, we will devise a way to implement a rival for a popular game: tic-tac-toe. Not only does it help us extend the base classes, but it also gives us a way to create rivals for our own board games.

Getting ready…

We will need to create a specific move class for the tic-tac-toe board derived from the parent class we created at the beginning of the chapter:

using UnityEngine;
using System.Collections;

public class MoveTicTac : Move
{
    public int x;
    public int y;
    public int player;

    public MoveTicTac(int x, int y, int player)
    {
        this.x = x;
        this.y = y;
        this.player = player;
    }
}

How to do it…

We will create a new class, deriving it from Board, override its parent's methods, and create new ones.

1. Create the BoardTicTac class, deriving it from Board, and add the corresponding member variables for storing the board's values:

   using UnityEngine;
   using System;
   using System.Collections...

Implementing a checkers rival

You will learn how to extend the previous recipes with an advanced example. In this case, you will learn how to model a checkers (draughts) board and its pieces in order to comply with the necessary functions to be used with our board-AI framework.

This approach uses a chess board (8 x 8) and its respective number of pieces (12). However, it can be easily parameterized in order to change these values in case we want to have a differently sized board.

Getting ready…

First, we need to create a new type of movement for this particular case called MoveDraughts:

using UnityEngine;
using System.Collections;

public class MoveDraughts : Move
{
    public PieceDraughts piece;
    public int x;
    public int y;
    public bool success;
    public int removeX;
    public int removeY;
}

This data structure stores the piece to be moved, the new x and y coordinates if the movement is a successful capture, and the position of the piece to be removed.

How to do it…

We will implement...