TITLE: How does AI win at chess? AUTHOR: Eddie S. Jackson, MrNetTek DATE: January 13, 2019 at 7:22 PM EST RESEARCH: Google search, current news, books, Copilot. EDITING: Grammarly
Artificial intelligence (AI) is the ability of machines to perform tasks that normally require human intelligence, such as reasoning, learning, planning, and decision-making. Chess is a classic game that challenges the intelligence of both humans and machines, as it involves strategic thinking, tactical skills, and creativity. Chess has been a popular testbed for AI research since the 1940s when the first chess-playing programs were developed. Since then, AI has made remarkable progress in chess, surpassing human performance and achieving superhuman levels of play.
One of the main challenges of AI for chess is to design an algorithm that can search through the vast number of possible moves and positions in a chess game, and find the best move for any given situation. A chess game can have about 10^120 possible positions, which is more than the number of atoms in the observable universe. Therefore, it is impossible for any computer to search all of them exhaustively. Instead, AI relies on heuristics, which are rules of thumb or shortcuts that help narrow down the search space and evaluate the quality of moves and positions.
One of the most common heuristics for chess is calledno computer can search minimax, which assumes that both players are rational and try to maximize their advantage and minimize their opponent’s advantage. Minimax works by assigning a numerical value to each position, based on factors such as material balance, piece activity, king safety, pawn structure, and so on. The higher the value, the better the position for the player who has the move. Minimax then searches ahead a certain number of moves (called depth) and chooses the move that leads to the position with the highest value for the player who has the move (called maximizer), assuming that the opponent (called minimizer) will choose the move that leads to the position with the lowest value for the maximizer. This process is repeated recursively until a certain depth is reached or a terminal position (such as checkmate or stalemate) is encountered.
In C#, minimax can be implemented using a recursive function that takes a position and a depth as parameters, and returns the best value and move for the maximizer. The function can use a Board class that represents the state of the chess board, with methods such as GetLegalMoves, MakeMove, UndoMove and Evaluate. The function can also use a Move class that represents a chess move, with fields such as From, To, Piece, Capture and Promotion. The pseudocode for minimax can look something like this:
// Minimax function
public static (double value, Move bestMove) Minimax(Board position, int depth)
{
// If depth is zero or position is terminal, return the evaluation and no move
if (depth == 0 || position.IsTerminal())
{
return (position.Evaluate(), null);
}
// Initialize the best value and move for the maximizer
double bestValue = double.NegativeInfinity;
Move bestMove = null;
// Loop through all legal moves in the position
foreach (Move move in position.GetLegalMoves())
{
// Make the move on a copy of the position
Board newPosition = position.Copy();
newPosition.MakeMove(move);
// Call minimax recursively on the new position with reduced depth and opposite color
// Negate the value to switch between maximizer and minimizer
(double value, Move _) = Minimax(newPosition, depth - 1);
value = -value;
// If the value is better than the best value, update the best value and move
if (value > bestValue)
{
bestValue = value;
bestMove = move;
}
// Undo the move on the original position
position.UndoMove(move);
}
// Return the best value and move for the maximizer
return (bestValue, bestMove);
}
Minimax is a simple and elegant heuristic, but it has some limitations. For example, it does not take into account uncertainty or randomness in human or machine play. It also does not account for different styles or preferences of players. Moreover, it can be very slow and memory-intensive when searching deep into the game tree.
To overcome these limitations, AI researchers have developed various improvements to minimax for chess.
Some of these are:
- Alpha-beta pruning: This is a technique that allows the algorithm to skip some branches of the game tree that are not relevant for the final decision. It works by keeping track of two values, alpha and beta, that represent the lower and upper bounds of the best value for the maximizer and minimizer respectively. If the value of a position falls outside these bounds, the algorithm can stop searching that branch, as it will not affect the final outcome. Alpha-beta pruning can significantly reduce the number of nodes that need to be searched, and thus speed up the algorithm.
- Move ordering: This is a technique that tries to sort the moves in a position according to their expected value, so that the best moves are searched first. This can increase the chances of finding a good move early and triggering alpha-beta pruning. Move ordering can be done using various criteria, such as captures, threats, history, killer moves and so on.
- Bitboards: These are a way of representing the chess board using bits, where each bit corresponds to a square on the board. Bitboards can allow faster and more efficient operations on the board, such as generating moves, checking attacks, evaluating positions and hashing states. Bitboards can also reduce the memory usage of the algorithm.
- Transposition tables: These are a form of caching that store the results of previous searches in a hash table. This can avoid repeating the same calculations for positions that have already been searched before. Transposition tables can also store additional information, such as the best move, the depth and the type of node (exact, lower bound or upper bound). Transposition tables can improve both the speed and quality of the search.
- Board symmetries: These are transformations that preserve the essential features of a position, such as rotations or reflections. By exploiting board symmetries, the algorithm can reduce the number of positions that need to be searched and evaluated. For example, if a position is symmetric along the vertical axis, then only half of the board needs to be searched.
Those are some of the most common improvements to minimax for chess AI. There are many more techniques that can enhance the performance and intelligence of the algorithm, such as quiescence search, iterative deepening, null move pruning, aspiration windows and so on. However, even with these improvements, minimax still has some limitations that prevent it from reaching human-like or superhuman levels of play. For example, minimax relies on a fixed evaluation function that may not capture all the nuances and subtleties of chess. Minimax also does not learn from its own or its opponent’s mistakes or preferences. Minimax also does not have any creativity or intuition that can help it find novel or surprising moves.
So, to deal with inherent shortcomings of minimax (mainly lack of adaptability), AI researchers have turned to other paradigms for the AI in chess, such as machine learning and neural networks. These methods can allow the algorithm to learn from data and experience, rather than relying on predefined rules and heuristics. These methods can also enable the algorithm to adapt to different situations and opponents, and to generate more diverse and human-like moves. One of the most successful examples of this approach is AlphaZero, a deep reinforcement learning algorithm that learned to play chess from scratch by playing against itself. AlphaZero achieved superhuman levels of play in chess and other games, surpassing previous state-of-the-art algorithms such as Stockfish and Komodo. See AlphaZero.
When it comes to chess, artificial intelligence has advanced significantly since 1997 with Deep Blue. There have been various improvements to minimax for chess, such as alpha-beta pruning, move ordering, bitboards, transposition tables and board symmetries. AI programming has also explored other paradigms for playing intelligent chess, such as machine learning and neural networks. The technology has achieved remarkable results in chess and other games, such as AlphaZero, a deep reinforcement learning algorithm that learned to play chess from scratch. Contemporary AI has demonstrated the ability to search, evaluate and learn from chess, and to challenge and surpass human intelligence in this domain. In simple terms, modern AI can beat you at chess, because of improved learning ability in its core technology.
Something to note, while AI has certainly improved its chess game, it often fails simple logic, in and outside of chess. Perhaps, there is still a reason to keep humans around after all. All joking aside, the improvements in AI are a phenomenal achievement, and a testament to human’s ability to wield technology, and not just be controlled by it.
Notes
Tags: Artificial Intelligence, MrNetTek, Eddie Jackson Computer, AI
#ArtificialIntelligence #MrNetTek