How Chess Is Solved Using AI
Chess is an interesting test-bed for intelligent applications because the game is rich and complex with a massive search space. For this…
Let’s now explore the application of AI and search that’s used in classical games such as Chess, Go, Backgammon, and even Bridge and Poker. The application of AI to games is one of search, knowledge, and heuristics. Understanding AI and games is important because it provides a sandbox to test the efficacy of search algorithms. It’s also a means to understand the complexity of games. For example, while building a worthy AI algorithm for the game of Go is elusive, Bridge-playing AI algorithms regularly win at the highest level of Bridge championships.
Chess
In this story, We’ll begin our exploration of AI in classical games with a quick review of AI’s application in Chess. Chess is an interesting test-bed for intelligent applications because the game is rich and complex with a massive search space. For this reason, traditional search algorithms are woefully inadequate to play a reasonably intelligent game.
Chess is a game of perfect information, unlike games such as Poker, where not all of the information is known to each player. Both players see the same Chess board and know all moves that are possible for both players.
Early Chess computers operated in a brute-force way, as the speed of the computer was viewed as its greatest asset. Understanding the complexity of the game of Chess, it’s now known that more but computational speed doesn’t hurt.
Early in the days of Chess automation, limited depth search minimax was used to determine the best move to make. With limited CPU power and memory, minimax operated in very shallow trees, so the horizon effect minimized the intelligence of the moves. With the advent of minimax variations, you’ll still find minimax as the core algorithm in modern Chess systems today.
Chess programs are commonly made up of three modules.
The first is a move generator which analyses the current board and identifies the legal moves that can be made.
The second module is the evaluation function, which computes a relative utility for a given board configuration like how good a given board is compared to others for a given board configuration.
The final module is the search algorithm which must efficiently iterate through the available board configurations, given a move, and decide which path to take through the tree to select the next move to make.
In the 1990’s IBM’s Deep Blue successfully defeated Gary Kasparov, who at the time was the world Chess champion.
Chess-Board Representation
A simple representation for a Chess board is an 8 by 8 two Dimensional array with each cell containing an identifier representing the state of the cell. For example, 0 would represent an empty cell, 1 for a white pawn, -1 for a black pawn, etc.
An improved representation added a two cell board to the entire board, which was filled with a known character signifying an illegal move. This made it easier to identify illegal moves as would be possible with knights, and optimised the bounds checking aspect of the Chess program.
Today, a common representation for Chess programs is the bitboard. Using a 64-bit word which available on many computers, each cell on the Chess board can be represented by a bit in the 64-bit word. Each bit simply determines if a piece is in the cell (1) or if the cell is empty (0). But instead of having a single bitboard for the entire Chess board, there’s a bitboard for every type of piece on the Chess board (one each for the white and black piece types). A pawn bitboard would represent the placement of white pawns on the board. A bishop bitboard would contain bits for the black bishops. The advantage of the bitboard is that the computers that support the 64-bit type can very easily represent and query the state of the boards through bit masking operations, which are extremely efficient.
Another advantage of the bitboard is the efficiency in selecting a legal move. By bitwise or -ing the bitboards, you can see which cells are taken on the board and therefore, which moves are legal. It’s a simple operation that’s efficient for move generation.
Techniques Used in Chess programs
Let’s now look at some of the major techniques and algorithms that are employed by Chess programs.
Opening Book Database
The first few moves in a Chess game are important to help establish good board position. For this reason, many Chess systems employ a database of opening moves for a given strategy that can be linearly searched.
Minimax Search with Alpha-Beta Pruning
Chess systems typically use a modified version of game-tree search by performing only a shallow search of the game tree using minimax with alpha- beta pruning. While not intuitive, moves that result in smaller scores (gain or loss) are sometimes chosen that can improve the overall board position rather than a short-term gain.
The typical branching factor for Chess is around 35, but with alpha-beta pruning, this can be reduced to an effective branching factor of 25. Still large, but this reduction can help greatly to allow deeper searches into the game tree.
Other search algorithms have been devised for Chess such as aspiration search, which sets the bound of the alpha and beta parameters to some heuristically defined value instead of +INFINITY and -INFINITY. This narrows the search to nodes with a particular characteristic. There’s also quiescence search, which tries to evaluate positions that are “relatively quiescent,” or dead.
Another mechanism to minimise the search space is called null move forward pruning. The basic idea here is if you do nothing (no move), can the opponent do anything to change the board configuration to their benefit? If the answer is no, then opponent moves could be safely pruned from the tree. Hashed transposition tables are also employed to identify subtrees that have already been evaluated to avoid repetitive search. The hash is used to quickly identify the identical board configuration.
Static Board Evaluation
It should be clear that unless we’re near the end-game, our search of the game tree will not encounter any leaf nodes. Therefore, we’ll need to have a good utility function that helps us decide which move to make given our nearby horizon. The utility function for Chess defines whether a given board configuration is good or bad for the player, and it can decide this based on a large number of factors. For example, is our king or an important piece in jeopardy, or is the opponent in jeopardy for the current board? Is a piece lost in the board, and if it is, what’s the cost of the piece (pawn being the least, followed by the bishop, knight, rook, and queen in increasing value). Some of the other evaluations that can take place include the space available for pieces to move to and then the number of current threats.
While the minimax algorithm with alpha-beta pruning provides the means to search the game tree, the evaluation function helps us to decide which path is best based on a number of independent utility functions.
How Checkers Is Solved Using AI
Let’s now explore the application of AI and search that’s used in classical games such as Chess, Go, Backgammon, and…medium.com