Chess: high branching factor

Question

I'm trying to develop a simple chess engine, but I'm struggling with its performance. I've implemented Negamax with alpha-beta pruning and iterative deepening (without any additional heuristics), but I'm unable to get reasonable search time beyond 3-4th ply. Here is an excerpt from my program's 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 

It shows that branching factor is around 10. I have read that with proper move ordering I should be getting something around 6, so I suspect that my ordering is wrong. It currently works this way:

1. Game tree node has a linked list of its children; initially, captures and promotions are placed before quiet moves
2. During search, child that increases alpha or causes cutoff is placed at the beginning of the list
3. On the next iteration of deepening PV should be searched first

Is it a proper way to order moves and branching factor I get is to be expected? Currently I'm using a simple static evaluation function that only takes position's material difference into account - can it be a reason for a low cutoff rate (if mobility of figures is also considered, I get similar results)? Would techniques such as null move reduction or killer heuristic help significantly (not by 10-15%, but by an order of magnitude)? I don't expect my engine to be strong, but I would like to get the branching factor to be about 6.

Chavaree

Is that your log from the very first move? If so, those PVs don't look legal to me. – Rightwards

Claude Shannon was the mathematician who posited the first algorithm for computer chest in the 1950's. His thesis was the basis for Shannon's Number, which is said to be the number of possible games of chess (around 10^120). In his work, he came to the conclusion that if a computer could evaluate 10^6 possible moves per second, that it would take a computer more than 10^90 years to arrive at the first move (the number of atoms in the Universe is estimated to be around 10^80). – Commendam

This is a third move. Previous were C2->C4 and D1->A4. – Chavaree

Are you using .net or Java? Might be a factor... – Willie

I'm using C#, but the trouble is not the code being executed slowly, but pruning being inefficient, which is clearly algorithm's fault. – Chavaree

Answer 1

I've developed a chess engine in C# as well, and it has a branching factor around 2.5. It is definitely possible to improve your engine by many orders of magnitudes. Nowadays the general strategy is to use very aggressive move pruning based on good move ordering. You sacrifice some correctness for the being able to see some deep tactical lines.

Here's an overview of techniques that I found to be most effective. Note that some components are complements and others are substitutes, so the results I give are general guidelines. The great gains at the end of the list are not possible if you don't have a strong foundation.

1. Just negamax with alpha-beta pruning: depth 4 within 3 seconds.

2. Add iterative deepening and null move heuristic: depth 5. Iterative deepening does not really help at this point, but it is easy to implement. The null move consists of skipping your turn and seeing if you can still get a beta cutoff with a shallow search. If you can, then it's probably safe to prune the tree since it's almost always advantageous to move.

3. Killer heuristic: depth 6. This involves storing moves that cause beta cutoffs and trying them first if they are legal next time you are at the same depth. You seem to be doing something similar already.

4. MVV/LVA ordering: depth 8. Basically, you want to put captures that have lots of potential material net gain at the top of the move list. So if a pawn captures a queen, you should obviously search it first.

5. Bitboard representation: depth 10. This doesn't improve branching factor, but this is what I did when I reached this point. Ditch the arrays, use UInt64s instead, and use make/unmake instead of copy-make. You don't need to use magic bitboards if you find it difficult; there are simpler methods that are still very fast. Bitboards greatly improve performance and make it easy to write evaluation components. I went from perft(6) taking minutes to taking 3 seconds. (By the way, writing a perft function is a great way to ensure move generation correctness)

6. Transposition table: depth 13. This offers great gains but is also very difficult to get right. Be absolutely certain that your position hashing is correct before implementing the table. Most of the benefit comes from the amazing move ordering the table gives you. Always store the best move into the table and whenever you get a matching position, try it first.

7. Late move reductions: depth 16. This greatly inflates your search depth but the strength gain is more artificial than with other techniques. Basically your move ordering is so good now that you only need to fully search the first few moves in a node, and you can just check the others with shallow searches.

8. Futility pruning: depth 17. Leaf nodes are trimmed by skipping moves that have a low chance of improving the value of the node when looking at potential material gain. If the the net potential gain of the move + static evaluation of the position is below the current value of the position, skip the evaluation for the move.

There are various other components that also help, but most are minor and some are proprietary. :D However, it is not all about high search depths and low branching factors. Things like quiescence search worsens search depth but are pretty much a necessity for any engine. Without it your engine will suffer from great tactical errors. You may also want to consider check extensions and single reply extensions. I'd also recommend at least introducing piece-square tables to your evaluation function. It's a very easy way to greatly improve the positional knowledge of your program; you'll probably see your engine playing more common openings. Chess programming is a fun hobby and I hope the volume of the information does not discourage you!

Marocain

Thank you for an excellent, exhaustive answer. I was especially looking for performance gains offered by different techniques, and will definitely use your tips. – Chavaree

I almost feel like this is some mandatory read for having a general idea on how to optimize an AI problem. – Recognition

Answer 2

There is multiple heuristics that you can use to reduce your branching factor.

First, you should use a transposition table (TT) to store positions results, depth and best move. Before you search a move, you first check if it's already been searched at a depth >= to the depth you are planing to search to. If it is, you can simply use the result from the table. If it's not, you might still use the move in the table as your first move to search.

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

There is also Null Move Pruning. In combination with Alpha-Beta (Negamax is a variation on Alpha-Beta) in will greatly reduce your branching factor. The idea is before searching a position, you try a null move (not playing) and do a reduce search (N-2 or N-3). The reduce search will be really fast. If the result of the null move search is still higher than beta it means the position is so bad that you don't need to search it anymore (not always true, but it is most of the time).

Of course there is multiple others heuristic you can use to improve your move ordering wich will all improve your branching factor.

Distract