SharpChess - Search function test

[peterhughes]

One of the tests I already have , which I've found helpful, is a move-ordering unit test. It loads a middle-game position...

r2qk2r/ppp2ppp/2b5/4N3/1b1Pp3/8/PPP1QPPP/R1B2RK1 b k - 1 11

...and records the total positions searched to a depth of 5.

SharpChess's total moves search comes to: 52931

The unit test returns a fail, if the number of position exceed 52931, which is the smallest number I've managed to get it down to.

The question is, does this number seem too high?

FYI

SharpChess search uses the following techniques:

• Aspiration search, 3 decreasing windows (1000=1 pawn): +-2000, +- 500, then a zero window.
• PVS Seach.
• Adaptive Null-Nove Forward Pruning (R = depth > 6 ? 3 : 2).
• Quiescence for captures and promotions.
• Search Extensions:
• Check Evasion.
• Single response.
• Pawn push to 7th rank.
• Re-capture of same-value piece.
• Search Reductions:
• Reduce by 1 when alpha > increasing depth-based margin (0, 0, 0, 5000, 5000, 7000, 7000, 9000, 9000, 15000...)
• Futility Pruning at depth 2 where LazyEval + 3000 <= alpha.
• Extended Futility Pruning at depth 3 where LazyEval + 5000 <= alpha.
• Razoring at depth 4 where LazyEval + 9750 <= alpha.

Move ordering is assigned as follows:

1. Best move from hash table.
2. Pawn Promotion Queen.
3. Pawn Promotion Rook.
4. Pawn Promotion Bishop.
5. Pawn Promotion Knight.
6. Static Exchange Evaluation result, highest captures first.
7. History Heuristic.
8. Killer Move A.
9. Killer Move B.
10. Static Exchange Evaluation result, losing captures in reverse value order.

I found that the killer moves had very impact on move ordering compared to the history heuristic, which seems to do all the work. I also tried piece-square values, but that didn't do anything for me.

[crystalclear]

r2qk2r/ppp2ppp/2b5/4N3/1b1Pp3/8/PPP1QPPP/R1B2RK1 b k - acn 123578; acs 1; ce 117; pm Qxd4;

Is what my engine gives.

It's not got the stuff you talk about - I have an idea what the things are you mention, but I haven't any experience writing them at all - I have
a search,
seperate hash and transposition tables,
transposition tables entries which are written cyclically, so recently used ones should not be overwritten for some time, whereas those for previous game states will,
some quiesense,
initial move ordering (implemented mainly for the quiesence but used in search too) that tries captures in an order given by [capturing piece][captured piece].
rudimentary piece square tables, a little like the "Simple evaluation function" that's on the internet, but with squares scored the same for black and white.
best moves remember in the transposition tables
Lower bound and upper bound info in the TTs, and stupidly, exact info too, with a depth for each! (To be changed later, like everything else!)
Alpha beta search with zero window.
Attempts at cutoffs in various ways, some that work, some that don't.
(I'd like to discuss that elsewhere.)

The values for the move ordering are from the top of my head and not fully checked to see if they are all sensible but I put in some checks like this ...
assert(move_priority[QUEEN][QUEEN]>move_priority[QUEEN][ROOK]);
to verify the values I used make QxQ get considered before QxR. I don't even know if that is good. I was reading yesterday that trying best move first doesn't always give the smallest search tree.

I am incrementing my node counter in evaluate if I remember rightly. So nodes in the middle of the tree will have been counted when the search depth was shallower, but they are not recounted when visited in the middle of the tree. I could probably reduce the count by hashing the leaves, but my eval is so simple (PST+material) that it would probably take longer to store and retrieve hashed values than visit the leaves again.

[peterhughes]

That's interesting!

The test position has 42 legal moves.

We're searching to a depth of 5.

SharpChess is searching 52,773 nodes (when summing nodes from each iterative deepening phase, which I asume you're also doing.).

That gives SharpChess a rough branching-factor of approx, 8.8.

Roughly, that is: branching-factor ^ depth = nodes-searched.

8.8 ^ 5 = 52773.

From a move-ordering perspective, I guess this means that, on average, SharpChess is searching approximately 8 non-optimal moves out of a possible 41 before it finds the optimal move.

Now, I've heard some engine developers say that they achieve branching-factors in the region of 3 to 5!

A chess engine with a branching factor of 5, would only search 5^5 = 3125 positions.

A chess engine with a branching factor of 3, would only search 3^5 = 243 positions.

I guess this is why move-ordering in alpha-beta is so critical.

I'd be interested to hear what branching-factors other engine developers a managing to achieve with the above test position.

[crystalclear]

Thanks.

I have had some node count numbers, but never really known how to rate it as good or bad, just as better or worse than a previous version of my program.
But what you have given me with this "branching factor" idea is a possible method of determining whether one node count is better or worse than another for a completely different position.
Yes, getting the right move ordering and the rest of A-B seems critical - I have had version of my program accidentally play extremely well and then any supposed improvement completely destroys the playing ability and returns it to "normal". One improvement should have reduced the number of nodes visited by increasing alpha and causing more cutoffs - but leaving alpha unchanged probably meant that the same nodes were researched and thus returned from transposition tables. With the A-B improvement that didn't work, the reduced node count on the rest of the search maybe have been on "new" nodes and thus not values were returned from the transposition tables, making the supposedly better search worse in practice.

Correct me if I am wrong here ...
To prove a move is the best all opponent replies need to be analysed, so even with perfect move ordering, branching factor cannot get anywhere near one, as you cannot look at a single opponent move.
So if there are 36 moves possible by each player in every position, would the branching factor be limited to about 6, since 6*6=36?
ie you need to look at something like 1*36*1*36*1*36*1*36 movesto search 8 play deep and prove that something is optimal for white.

That's my naive view, from a possible misunderstanding of things.
With that in mind a branching factor of a bit over 8 for 42 possible moves doesn't sound too bad.

Hmmm - transposition tables will reduce the count of nodes visited, imperfect move ordering will increase it, and my naive calculation didn't consider that we really want to show the best move has optimised for both players, not just one.
I don't know how to account for all that.

I think I need to read some technical material on branching factors.

[peterhughes]

The ChessWiki has an entry on branching factor.

http://chessprogramming.wikispaces.com/Branching+Factor

It also going on to talk about Late Move Reductions, and states that this, combined with other techniques can reduce the Effective Branching Factor to be less than 2!

http://chessprogramming.wikispaces.com/Late+Move+Reductions

This chess programming wiki didn't exist when I was developing SharpChess 6-7 years ago. I have to say, it looks like a fantastic resource!