But you look deeper and see that after move B the opponent will force checkmate you in a few moves. You keep looking at the board and found an even better move B. Imagine you are playing chess and found a really good move A. An intuition behind A/B pruning is the following. Naive minimax would be too slow for chess as it would require iterating too many moves in depth to find a good one.Īlpha-beta pruning is used to speed up minimax by removing nodes not worth consider. Minimax is a rule used to minimize the worst-case potential loss - a player considers all of the best opponent moves, and selects the move such that the opponent’s best strategy gives a score as large as possible. For each possible move the value of the position is calculated using minimax algorithm with alpha-beta pruning. Search algorithmįor toy chess engines the most popular search algorithm is depth-first search that starts from root and goes down to the given depth limit, iterating all possible moves before backtracking. Now we can make a slightly better engine that chooses the best available move instead of a valid random one.īut real chess engines look deeper and analyze a tree of possible moves fromĮach side to find the best move in the longest perspective.

Type Piece byte func ( p Piece ) Value () int We could create a 12x12 board, but as long as we represent it as a linear array - we only need 12x10 board, because the rightmost padding square from the previous row could also be used as the leftmost padding of the next row (× = padding): So, we need a 2 square padding around the board. Of course, other sliding pieces can move over longer distances, but such moves would be evaluated step by step, and board boundaries would be found sooner. The longest move distance that a chess piece can move is a knight move by 2 squares. This allows us to avoid boundary checks and simplifies code a lot. We would add some padding around the typical 8x8 board so that invalid piece moves would end up in this padding area. It is important to find a convenient and memory-efficient board representation, because during the optimal move search thousands of boards would be kept in memory.Ī board is typically represented as an array of squares. You may find the full code of the engine at (the name comes from latin species name of Gopher rockfish). The code snippets in this post are simplified and contain only most important parts of code.

How to perform a search for the optimal move.How to evaluate the board (who is likely to win).How to represent the chess board (squares, pieces, valid moves).To build a chess engine one has to decide on three important topics:

Go is also known as a simple and highly readable language, so I hope the two of them could make a great couple. Sunfish is notable for its simplicity and small size, while still being capable of playing decent chess. In this article we will try to understand how chess engines work by porting the sunfish chess engine to Go.

Algorithm for chess program