Beginner AB move ordering question

[stevemulligan]

I'm trying to build an engine in c# based on the http://chessbin.com tutorial. As I understand it, the move ordering should not affect the outcome of the search. It will only change the speed. I noticed something strange with this position:

r2qkbnr/1pp1pppp/p1n5/1B1p1b2/5P2/2N1PN2/PPPP2PP/R1BQK2R w KQkq - 0 6

No iterative deepening, no pruning, all extensions disabled, 5 ply fail-hard negamax


With move ordering I get this line:

5 276 271 52690 b5->c6 (276) b7->c6 (-276) f3->d4 (276) f5->d7 (-276) c3->d5 (276)


Without move ordering I get something different:

5 388 1398 238614 f3->e5 (388) d8->d6 (-388) b5->a4 (388) e8->c8 (-388) a4->c6 (388)


Aside from the poor choice of moves, is this is a bug? Should the best move always be the same regardless of the move order?
I've been looking at it for days and can't figure out why the result is different. Before I spend any more time looking, I want to make sure this is a problem.

[Sven]

As you wrote, without move ordering the search should only take longer to find the best move. Since 1.Ne5? misses that the Bb5 is en prise it is obviously worse than 1.Bxc6 so I would suspect a bug in your search code.

You could enable your engine to print the whole tree that it searches to a file, then look at it. Check whether 1.Ne5 axb5 has been considered, and which value was returned from there. You might even do this in a debugger.

Have you checked correctness of your move generator with perft?

Sven

[hgm]

[d]r2qkbnr/1pp1pppp/p1n5/1B1p1b2/5P2/2N1PN2/PPPP2PP/R1BQK2R w KQkq - 0 6

[bob]

I'm trying to build an engine in c# based on the http://chessbin.com tutorial. As I understand it, the move ordering should not affect the outcome of the search. It will only change the speed. I noticed something strange with this position:

r2qkbnr/1pp1pppp/p1n5/1B1p1b2/5P2/2N1PN2/PPPP2PP/R1BQK2R w KQkq - 0 6

No iterative deepening, no pruning, all extensions disabled, 5 ply fail-hard negamax


With move ordering I get this line:

5 276 271 52690 b5->c6 (276) b7->c6 (-276) f3->d4 (276) f5->d7 (-276) c3->d5 (276)


Without move ordering I get something different:

5 388 1398 238614 f3->e5 (388) d8->d6 (-388) b5->a4 (388) e8->c8 (-388) a4->c6 (388)


Aside from the poor choice of moves, is this is a bug? Should the best move always be the same regardless of the move order?
I've been looking at it for days and can't figure out why the result is different. Before I spend any more time looking, I want to make sure this is a problem.

Let's be more specific. Move ordering should not affect the final _score_, if you are not doing hashing. It can certainly affect the PV and even best move, such as in a case where 2 different moves lead to the same score/position due to transposition...

It looks like your scores are changing. Which represents a bug.

[stevemulligan]

Many thanks Sven & Robert.

I had to add a perft function and modify my move generation to include more than just promoting to queens to get the #'s to match what is reported on chessprogramming wiki (at least to 5 ply, I didn't go beyond that)

My perft for the above position seems to match Roce.

5. Nodes: 42689429 Captures: 4272736 Castles: 695268 EP: 726 Promotions: 0 Checks: 1102528 Mates: 1035
4. Nodes: 1190261 Captures: 89056 Castles: 2534 EP: 8 Promotions: 0 Checks: 7048 Mates: 0
3. Nodes: 38593 Captures: 3551 Castles: 806 EP: 0 Promotions: 0 Checks: 982 Mates: 0
2. Nodes: 1075 Captures: 73 Castles: 0 EP: 0 Promotions: 0 Checks: 2 Mates: 0
1. Nodes: 36 Captures: 3 Castles: 1 EP: 0 Promotions: 0 Checks: 1 Mates: 0



Should the beta value for a single branch at any given ply (say 3) always be increasing? Mine seems to jump around and I'm guessing it shouldn't be doing that...

[Desperado]

Hello Steve,

well if you are pretty sure that your movegeneration works fine, let s
concentrate on evaluation and search bugs.

It looks to me that the values for _both_ lines are broken, because
both values (276,388) are indicating that one side is a piece ahead(down).

So you may check the following points:

- _sign_ (perspective) of evaluation function (you pass back to the search)

- do a 2 ply search with an _open_ window [lobound,ubound] for _every_ root move.

because within this space your engine loses the bishop on b5 which
should not happen in any case. You will get of course _exact_ values for
the root moves (and make the scores directly comparable)

_Every_ non bishop(b5) move should give a value around -300. The bishop(b5) moves will rescue the bishop
and should be scored around 0.

After having checked these 2 points you should be able to locate the root of the problem, if it is not a combined one.

good luck

Michael

[Desperado]

Hello Steve,

well if you are pretty sure that your movegeneration works fine, let s
concentrate on evaluation and search bugs.

It looks to me that the values for _both_ lines are broken, because
both values (276,388) are indicating that one side is a piece ahead(down).

So you may check the following points:

- _sign_ (perspective) of evaluation function (you pass back to the search)

- do a 2 ply search with an _open_ window [lobound,ubound] for _every_ root move.

because within this space your engine loses the bishop on b5 which
should not happen in any case. You will get of course _exact_ values for
the root moves (and make the scores directly comparable)

_Every_ non bishop(b5) move should give a value around -300. The bishop(b5) moves will rescue the bishop
and should be scored around 0.

After having checked these 2 points you should be able to locate the root of the problem, if it is not a combined one.

good luck

Michael

edit:

The second score of 388 actually indicates a piece+pawn difference.
Because your signs flip in the given lines, my (first) guess is, that it
is not a search related problem. The search would maximize a material
overhead of piece and pawn into the direction of 420 instead of 380.
Nevertheless, check where you can the signs (evaluation,search), with
my first guess that material scores are summed up with wrong sign
or as mentioned already the evaluation does not pass the value
with the right perspective.

Michael

[hgm]

Well, as the sorting seems to make the difference, I would suspect the sorting. Apparently you don't just re-order the moves, but lose some in the process.

[Desperado]

Well, as the sorting seems to make the difference, I would suspect the sorting. Apparently you don't just re-order the moves, but lose some in the process.

Hi hgm,

well i am absolute sure it is _not_ (at least not only) a move ordering issue.
You only have to look at the scores of _both_ lines, where a score around
and more than a piece value is absolut wrong.

Or are you talking of _re-sorting_ the root moves and their values ?
(which could easily be of course, but anyway there shouldnt appear
values around 300 at the root...)


Michael

[hgm]

I am more worried about the scores being different than them being wrong. The latter can have many reasons. It is for instance not clear to me if QS is used here.