Chess: high branching ratio

Question

I am trying to develop a simple chess engine, but I am afraid of its performance. I implemented Negamax with alpha-beta cropping and iterative deepening (without any additional heuristics), but I can’t get a reasonable search time beyond the 3-4th layer. Here is an excerpt from my program log from the beginning of the game:

2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1 2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28 2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28 2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 2013-05-11 18:22:06,835 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2 2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90 2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118 2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 2013-05-11 18:22:06,897 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3 2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027 2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414 2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 2013-05-11 18:22:08,005 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4 2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629 2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880 2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 2013-05-11 18:22:10,485 [9] INFO CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5 2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758 2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538 2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6 

This shows that the branching factor is about 10. I read that with the correct order of movement I need to get something around 6, so I suspect that my order is wrong. It currently works as follows:

• The node game tree has a linked list of its children; initially, captures and promotions are placed in front of quiet moves.
• During a search, a child element that increases alpha or causes clipping is placed at the top of the list.
• In the next iteration, the recesses PV should be sought first

Is this the right way to streamline the moves and the branching factor that I get should be expected? I am currently using a simple static evaluation function that takes into account only the difference in material positions - could this be the reason for the low cutoff speed (if the mobility of the numbers is also taken into account, I get similar results)? Can there be methods such as reducing the zero movement or the killer’s heuristic (not by 10-15%, but by an order of magnitude)? I do not expect my engine to be strong, but I would like the branching ratio to be around 6.

Answer 1

I also developed a chess engine in C # and it has a branching coefficient of about 2.5. It is certainly possible to improve your engine by many orders of magnitude. Currently, the overall strategy is to use a very aggressive stroke based on good order transfer. You sacrifice some correctness for seeing some deep tactical lines.

Here is an overview of the methods that I found most effective. Please note that some components are add-ons, while others are substitutes, so the results that I give are general recommendations. Big wins at the end of the list are not possible unless you have a solid foundation.

• Just negamax with alpha beta pruning : 4 depth for 3 seconds.

• Add an iterative deepening and null move heuristic : depth 5. An iterative deepening does not really help at the moment, but it is easy to implement. Zero movement consists of skipping your turn and observing if you can still get a beta cut-off with a fine search. If possible, then it is probably safe to prune a tree since it is almost always beneficial to move.

• Killer heuristics : depth 6. This includes saving moves that cause beta cutoffs and try them first if they are legal the next time you are at the same depth. It seems you are doing something similar already.

• Order MVV / LVA : depth 8. In principle, you want to have a ton of potential material net gain at the top of the move list. Therefore, if a pawn captures the queen, you must first look for her.

• Presentation of the bit version : depth 10. This does not improve the branching factor, but it is what I did when I achieved this. Cut arrays, use UInt64 instead and use make / unmake instead of copy-make. You do not need to use magic bits if you find it difficult; there are simpler methods that are still very fast. Bits significantly improve performance and simplify the recording of evaluation components. I went from perft (6), counting minutes to 3 seconds. (By the way, writing a perft function is a great way to guarantee the correct generation of movements)

• Transpose table : depth 13. This gives big wins, but it’s also very difficult to get right. Be absolutely sure that your position hashing is correct before implementing the table. Most of the profit comes from an amazing step, organizing the table gives you. Always keep the best go to the table and whenever you get a suitable position, try the first one.

• Abbreviations at the end of the turn : depth 16. This greatly inflates your search depth, but gaining strength is more than other methods. Basically, your move order is so good that you only need to search for the first few moves in the node, and you can just check the rest with a shallow search.

• Trimming uselessness : depth 17. Leaf nodes are trimmed by missed movements that have a low chance of improving node value when considering potential material gain. If the net potential gain + static position estimate is lower than the current position value, skip the move estimate.

There are other components that also help, but most of them are minor, and some of them are property.: D However, this is not all about high search depths and low branching factors. Things like finding peace , worsen the depth of the search, but are pretty much necessary for any engine. Without this, your engine will suffer from big tactical mistakes. You might also consider checking for extensions and one-line answers . I would also recommend at least presenting square tables in your evaluation function. This is a very simple way to significantly improve the positional knowledge of your program; you'll probably see your engine playing more general discoveries. Chess programming is a fun hobby, and I hope that the amount of information will not impede you!

Answer 2

There are several heuristics that can be used to reduce branching ratios.

First, you must use the transpose table (TT) to save the position results, depth and best move. Before you perform a search, first check to see if it has already been performed with depth> = to the depth that you plan to perform. If so, you can simply use the result from the table. If this is not the case, you can still use table navigation as your first search transition.

If there is no match in the TT position (inside the search), you can use Iterative Deepening (ID) . Instead of searching for a depth of N , first search for a depth of N-2 . This will be very fast and will allow you to go to the search first at a depth of N

There is also Null Move Pruning . When combined with Alpha-Beta (Negamax is a variation on Alpha-Beta), your branching ratio will be greatly reduced. The idea is that before you search for a position, you perform a zero move (do not play) and perform a search for abbreviation (N-2 or N-3). Search for abbreviations will be very fast. If the search result for the zero movement is still higher than the beta, this means that the position is so bad that you no longer need to search for it (not always true, but this is most of the time).

Of course, there are several other heuristics you can use to improve move ordering that will improve your branching ratio.