Shame

[Henk]

Biggest mistake was that the wrong move generator code was not used in the perft tests. Perhaps because it was slower.

Hum perhaps it would not have made any difference for in remaining moves all moves were generated again and the captures subtracted. So it probably is all about bad move ordering that caused the problems.

[Henk]

I just tried the mate in 4 and Abbess solved it in well under a second.

Code: Select all

 1   -172       1        132 f2g1
 2   -252       2       3022 f2f1
 3   -231       8      51021 f2f1
 4  32760      28     367038 e4f6
 5  32760      63    1028552 e4f6

I've intentionally not added nullmove, hashtables or anything fancy yet, as I want to make sure the things I do are solid this time around. I do recaptures, check extensions, IID sorting, and that's about it. Pseudolegal move generation, with a not-in-check validation after the move.

I think one thing I realized from working on Beaches is that it is easy to hammer new features on early in the process, and they may improve the engine, even when they are broken.

But then it tends to be harder to go back and look at basic things later on, like move ordering. And after a few layers of these not-quite-right enhancements, your engine starts doing bad things at odd times, which is an even bigger nightmare to track down.

With check extensions plain AB + q search gives:

Code: Select all

Depth  Value   Time
  1  -11508.00   0.019          78   b2b4 
  2  -15171.00   0.046        2039   a3b3 
  3  -12228.00   0.307       25303   a3b3 
  4  9999997.00   2.500      220736   e4f6 
  5  9999997.00   24.172     2015883   e4f6 

Another bug: mate scores are not ok. Should not be mate in 3 but mate in 7 plies. So score should be 9999993 instead of 9999997. This is probably because of these check extensions.

[hgm]

Biggest mistake was that the wrong move generator code was not used in the perft tests. Perhaps because it was slower.

Perft has always been of very little use for me, to catch engine bugs. I have had plenty of search bugs, but they were always due to wrong alpha-beta pruning, moves getting lost or duplicated during sorting, killers disappearing from the move list in the next IID iteration... All those things an engine does, and perft wouldn't. I really recall only one instance where I had a bug in the move generator. That was when I converted Joker to play Knightmate, and I had overlooked the fact that although a pinned Knight in Chess never has any moves, its Knightmate equivalent, the Commoner, still has moves along the pin line. But I found that pretty fast even without perft (for which no numbers were known at the time anyway). So I don't even bother to implement perft in my engines anymore.

[op12no2]

I've been wanting to create an ID + alpha/beta + check-extension only version of my online Javascript engine Lozza for a while (as a kinda sanity check) and this thread pushed me into it.

Below is a real-time link to the alpha/beta version solving the mate puzzle discussed above (needs a modern browser).

http://op12no2.me/toys/lozza/fen.htm?e= ... 01&act=ana

(refresh the page is you don't see the board)

Eval is tapered material + PSTs. Move ordering is promotions, captures, killers etc and slides ordered using the eval PSTs. There is no PV other than the best move at each alpha raise. It does not do anything with the best moves other than display them (e.g. no shuffling to the front at the root).

Since the Javascript is being evaluated in real-time, it should be useful as a worst case performance-wise.

source is here:-

http://op12no2.me/toys/lozza/lozzaab.js

NB: the 'seldepth' reported is the deepest Q depth thus far, so 5/17 is ply 5 with Q getting down to -17 based on the check extension.

[Evert]

Perft has always been of very little use for me, to catch engine bugs. I have had plenty of search bugs, but they were always due to wrong alpha-beta pruning, moves getting lost or duplicated during sorting, killers disappearing from the move list in the next IID iteration... All those things an engine does, and perft wouldn't. I really recall only one instance where I had a bug in the move generator. That was when I converted Joker to play Knightmate, and I had overlooked the fact that although a pinned Knight in Chess never has any moves, its Knightmate equivalent, the Commoner, still has moves along the pin line. But I found that pretty fast even without perft (for which no numbers were known at the time anyway). So I don't even bother to implement perft in my engines anymore.

Perft has a very specific usefulness: to find bugs in the move generator. Sure, you can use it to measure performance of movegen+make/unmake as well, but a chess program spends a small fraction of its runtime at those anyway.

In order for it to be useful, you need a suitable set of test positions (the starting position is almost useless because you don't get en-passant, check evasion, castling, promotion, capture, drops or other interesting effects) and independently verified perft results. People have posted suitable positions for othochess, and a few for FRC, but in general they're hard to find - let alone finding independent results.

Nevertheless, I've found perft to be quite useful for Sjaak, where my usual approach has been to find buggy positions in games, fix the bug and then include them in the test suite. On a few occasions these have revealed issues when I added a new feature, or fixed another bug, which would have taken me a while to find otherwise. Of course I've also had to update the perft numbers in the test suite as I fixed bugs, since some of them turned out to be wrong!

So it's usefulness is rather limited and specific, but I've found it not completely useless.

[op12no2]

so 5/17 is ply 5 with Q getting down to -17 based on the check extension.

No, I mean -17 based on max captures in Q search at any point during the search.

[op12no2]

Had a lot of fun with Lozza alpha/beta today. I've added a PV and tweaked ID to shove the current PV in the nodes for the search to follow on the next iteration (no TT).

http://op12no2.me/toys/lozza/fen.htm?e= ... 01&act=ana

0.08 4/15 (3mate) Nf6 g7xf6 Qf8 Kxf8 Bh6 Kg8 Re8#
0.06 4/15 (-230cp) Qe7 Qd7 Qxd7 Nxd7
0.05 4/14 (-250cp) Qb3 Qxb3 c2xb3 Nc6
0.03 3/10 (-205cp) Qb3 Be6 Qxd5
0.02 2/10 (-206cp) Qb3 Qc6
0.01 2/10 (-315cp) Kg1 d3
0.01 1/5 (-195cp) Kg1
0.01 1/5 (-201cp) Bf4
0.01 1/2 (-423cp) Nxd4

43k nodes.

http://op12no2.me/toys/lozza/lozzaab.js

[op12no2]

I did one more tweak to the alpha/beta engine - to sort root moves by Q search and successively move root alpha raises to the front during ID. Slightly fewer nodes now - 37k.

http://op12no2.me/toys/lozza/fen.htm?e= ... 01&act=ana

Windows 64bit executable and source here if anybody is interested - possibly useful as a worst possible case performance(*)/node-wise for newly developing engines...

http://op12no2.me/toys/lozza/lozzaab.zip

(*) the exe is essentially node.js (https://nodejs.org) loading the lozzaab.js source (http://op12no2.me/toys/lozza/lozzaab.js) and evaluating it in real time when the search is done. Hence the exe is quite large for such a small engine. Any compiled engine will be faster than this.

[zd3nik]

Strange alpha beta search with TTable is able to solve this easily while PVS can't. Difference is only three lines of code. After a few moves the algorithm should see a mate in eight or so.

[d] 4k3/8/8/8/8/8/8/6KQ w - - 0 1

This is an interesting kind of test position. I'm curious if there's a common method of directing the search in situations like this.

Clubfoot takes about 4 and half seconds to solve this with TT + PVS + NMP + LMR on my i5 laptop. Without TT it's been searching for well over 5 minutes and still hasn't solved it.

Also, is Mate in 7 the correct answer?

Code: Select all

info depth 16 seldepth 25 nodes 5629326 time 4630 nps 1215837 score mate 7 pv h1b7 e8d8 g1f2 d8e8 f2e3 e8f8 e3d4 f8e8 d4e5 e8f8 e5f6 f8e8 b7e7

Thanks,
STC

[zullil]

Strange alpha beta search with TTable is able to solve this easily while PVS can't. Difference is only three lines of code. After a few moves the algorithm should see a mate in eight or so.

[d] 4k3/8/8/8/8/8/8/6KQ w - - 0 1

This is an interesting kind of test position. I'm curious if there's a common method of directing the search in situations like this.

Clubfoot takes about 4 and half seconds to solve this with TT + PVS + NMP + LMR on my i5 laptop. Without TT it's been searching for well over 5 minutes and still hasn't solved it.

Also, is Mate in 7 the correct answer?

Code: Select all

info depth 16 seldepth 25 nodes 5629326 time 4630 nps 1215837 score mate 7 pv h1b7 e8d8 g1f2 d8e8 f2e3 e8f8 e3d4 f8e8 d4e5 e8f8 e5f6 f8e8 b7e7

Thanks,
STC

Yes. It's mate-in-7 with Qb7 or Qh7.