repetition draw bug

Sven · Post by **Sven** » Wed Aug 24, 2011 10:27 am

stevemulligan wrote:My move generation is terrible. I get slow perft results too. I guess I should try and speed it up. I spend all most of my time checking for check.

I assume you are talking about legality checking ("is enemy king in check"), I hope I did not misunderstand you. The normal "is my king in check" should not consume a huge amount of time IMO.

Are you doing fully legal move generation, or do you generate pseudolegal moves and check for legality only after making it in the regular search?

The latter has some potential to be a lot faster than the former since you save many legality checks for those moves which are never made due to a cutoff.

For the "fully legal" approach, usually you can get a comparable performance only if you are using all the tricks to avoid calling some "isOpponentInCheck()" function for almost every move.

Even with the "check for legality only after makeMove()" approach you can be a lot smarter than always calling "isOpponentInCheck()" there. In my engine, for instance, I have some "last move may have been illegal" logic which reduces to something like:

Code: Select all

!lastMoveWasNullMove
&& &#40;lastMoveWasCheckEvasion || lastMoveWasKingMove || lastMovePossiblyMovedAPinnedPiece&#41;

and I only call "isOpponentInCheck()" if that expression is true.

Sven

hgm · Post by **hgm** » Wed Aug 24, 2011 11:24 am

In Joker (and qperft) I first detect pins (starting from the enemy slider list, so typically only 5 tests for King alignment), and then use special code to generate the moves for those pieces along the pin ray. This actually saves time compared to generating all moves with pinned pieces (and as a bonus tells you if you are in check by a slider), even before testing any of them for legality.

The only pseudo-legal moves generated by the move generator that can be illegal are then King moves and e.p. captures. So only for those moves I do an explicit check test after MakeMove.

Of course a bit could still be saved on this by 'bulk-testing' the King moves, i.e. once you see that a slider attacks a square in the King neighborhood, continue along the ray to see if it attacks more such squares. But the potential gain for this was so low I never bothered. If you have a proper King safety in the eval (so unlike Joker...

), you might have this info around anyway, even before you do move generation (if you do eval in every node), so the legality tests of the King moves become really fast. And e.p. of course is so rare in the tree that it doesn't matter much what you do there.

sje · Post by **sje** » Wed Aug 24, 2011 2:50 pm

A few more data points, this time from a single thread on 3.2 GHz Intel Core i3:

Code: Select all

&#91;&#93; rgstat 10000
Summary&#58;
  Checkmate 1,548 &#40;0.1548&#41;
  FiftyMoves 1,972 &#40;0.1972&#41;
  Insufficient 5,606 &#40;0.5606&#41;
  Repetition 263 &#40;0.0263&#41;
  Stalemate 611 &#40;0.0611&#41;
Count&#58; 10,000   Elapsed&#58; 1.58903  &#40;6293.13 Hz / 0.000158903 s&#41;
&#91;&#93; rgstat 1000000
Summary&#58;
  Checkmate 152,932 &#40;0.152932&#41;
  FiftyMoves 199,487 &#40;0.199487&#41;
  Insufficient 560,728 &#40;0.560728&#41;
  Repetition 25,414 &#40;0.025414&#41;
  Stalemate 61,439 &#40;0.061439&#41;
Count&#58; 1,000,000   Elapsed&#58; 158.99  &#40;6289.69 Hz / 0.00015899 s&#41;
&#91;&#93; rgstat 10000000
Summary&#58;
  Checkmate 1,528,885 &#40;0.152889&#41;
  FiftyMoves 1,998,095 &#40;0.19981&#41;
  Insufficient 5,606,350 &#40;0.560635&#41;
  Repetition 254,592 &#40;0.0254592&#41;
  Stalemate 612,078 &#40;0.0612078&#41;
Count&#58; 10,000,000   Elapsed&#58; 1589.45  &#40;6291.5 Hz / 0.000158945 s&#41;
&#91;&#93; rgstat 100000000
Summary&#58;
  Checkmate 15,297,427 &#40;0.152974&#41;
  FiftyMoves 19,986,647 &#40;0.199866&#41;
  Insufficient 56,060,201 &#40;0.560602&#41;
  Repetition 2,540,035 &#40;0.0254003&#41;
  Stalemate 6,115,690 &#40;0.0611569&#41;
Count&#58; 100,000,000   Elapsed&#58; 15885.4  &#40;6295.08 Hz / 0.000158854 s&#41;

stevemulligan · Post by **stevemulligan** » Fri Sep 16, 2011 12:45 pm

sje wrote:A few more data points, this time from a single thread on 3.2 GHz Intel Core i3:

Code: Select all

&#91;&#93; rgstat 10000
Summary&#58;
  Checkmate 1,548 &#40;0.1548&#41;
  FiftyMoves 1,972 &#40;0.1972&#41;
  Insufficient 5,606 &#40;0.5606&#41;
  Repetition 263 &#40;0.0263&#41;
  Stalemate 611 &#40;0.0611&#41;
Count&#58; 10,000   Elapsed&#58; 1.58903  &#40;6293.13 Hz / 0.000158903 s&#41;

Thanks for posting those. I was using fully-legal, uh, "extra-redundant" move generation when I was getting 1 game/sec. It was a mess.

I went back and did my best to speed up move generation using pseudo-legal moves and I'm up to 170 games/sec. (Core 2 duo 1.8GHz)

What engine are you using that has the rgstat command? I figured it would be a common feature but I can't find it in the engines I've tried. I want to compare rgstat performance on the same CPU to see exactly how slow I'm running.

Also, I appear to have a bug in my endgame calc

Code: Select all

rgstat 10000
 Checkmate&#58; 2872 &#40;0.2872&#41;
 FiftyMoves&#58; 1478 &#40;0.1478&#41;
 Insufficient&#58; 5378 &#40;0.5378&#41;
 Repetition&#58; 93 &#40;0.0093&#41;
 Stalemate&#58; 179 &#40;0.0179&#41;
Elapsed Time 67.24s &#40;148.721&#41;

sje · Post by **sje** » Fri Sep 16, 2011 1:40 pm

stevemulligan wrote:What engine are you using that has the rgstat command? I figured it would be a common feature but I can't find it in the engines I've tried. I want to compare rgstat performance on the same CPU to see exactly how slow I'm running.

The rgstat command name means "random game statistics". As far as I know, only my programs Symbolic and the CIL toolkit have it implemented. Both programs also have the rg command which generates a single random game. I recommend that all authors consider implementing these as the commands are useful for several purposes.

sje · Post by **sje** » Fri Sep 16, 2011 1:56 pm

There are some minor ambiguities concerning game termination prioritization.

Case 1: The situation where both the repetition rule and the fifty move rule trigger simultaneously.

I resolve this in favor of the fifty move rule.

Case 2: The situation where both the stalemate rule and any other rule trigger simultaneously.

I resolve this in favor of the stalemate rule.

Case 3: The situation where both the checkmate rule and any other rule trigger simultaneously.

I resolve this in favor of the checkmate rule.

The priority ranking is:

1) Checkmate
2) Stalemate
3) Fifty move rule
4) Repetition rule
5) Insufficient material rule

stevemulligan · Post by **stevemulligan** » Fri Sep 16, 2011 3:30 pm

sje wrote: The rgstat command name means "random game statistics". As far as I know, only my programs Symbolic and the CIL toolkit have it implemented. Both programs also have the rg command which generates a single random game. I recommend that all authors consider implementing these as the commands are useful for several purposes.

Is Symbolic or the CIL toolkit available as a windows exe? I can't tell from the wiki page if it's available for download.

sje · Post by **sje** » Fri Sep 16, 2011 3:40 pm

stevemulligan wrote:
sje wrote: The rgstat command name means "random game statistics". As far as I know, only my programs Symbolic and the CIL toolkit have it implemented. Both programs also have the rg command which generates a single random game. I recommend that all authors consider implementing these as the commands are useful for several purposes.
Is Symbolic or the CIL toolkit available as a windows exe? I can't tell from the wiki page if it's available for download.

Symbolic is not available. The CIL (Chess In Lisp) toolkit exists as a Common Lisp source available for download and requires a Common Lisp interpreter or compiler to run. I use the SBCL free Lisp package; it can be had for Mac OS/X and it also exists as a Debian package for Ubuntu Linux. I have no data at hand about Lisp compilers for Windows.

Actually, since I no longer use Apple's MobileMe web hosting, I'd have to email the CIL source on request. It's a single Lisp (text) file, 414 KB long.

stevemulligan · Post by **stevemulligan** » Fri Sep 16, 2011 5:31 pm

sje wrote: I'd have to email the CIL source on request. It's a single Lisp (text) file, 414 KB long.

I tried with GNU Lisp, clisp & steel bank common lisp. Steel Bank gave the best performance by a large factor. 33 games/sec on my cpu. But LISP on windows probably isn't the best benchmark. Being able to compare with other engines (C vs C#) would be extremely helpful.

Steel Bank

Code: Select all

* &#40;report-random-game-terminations 10000&#41;
Count&#58; 10,000   Elapsed&#58; 333.477   Frequency&#58; 29.987076 Hz   Period&#58; 33.3477 ms
Checkmate 1539 0.1539
FiftyMoves 1940 0.194
Insufficient 5656 0.5656
Repetition 291 0.0291
Stalemate 574 0.0574

clisp (cygwin)

Code: Select all

$ clisp CIL.lisp
Chess In Lisp Toolkit   Release 2011.05.17
Copyright &#40;C&#41; 2011 by c...@me.com
Ready
Count&#58; 100   Elapsed&#58; 148.79   Frequency&#58; 672.0882 mHz   Period&#58; 1.4878999 s
Checkmate 20 0.2
FiftyMoves 13 0.13
Insufficient 57 0.57
Repetition 5 0.05
Stalemate 5 0.05

GNU lisp

Code: Select all

>>&#40;report-random-game-terminations 100&#41;
Count&#58; 100   Elapsed&#58; 109.12   Frequency&#58; 916.42228739002928 mHz   Period&#58; 1.091
1999999999999 s
Checkmate 9 0.089999999999999997
FiftyMoves 22 0.22
Insufficient 56 0.56000000000000005
Repetition 7 0.070000000000000007
Stalemate 6 0.059999999999999998

Volker Annuss · Post by **Volker Annuss** » Fri Sep 16, 2011 5:37 pm

sje wrote:There are some minor ambiguities concerning game termination prioritization.

Case 1: The situation where both the repetition rule and the fifty move rule trigger simultaneously.

I resolve this in favor of the fifty move rule.

Case 2: The situation where both the stalemate rule and any other rule trigger simultaneously.

I resolve this in favor of the stalemate rule.

Case 3: The situation where both the checkmate rule and any other rule trigger simultaneously.

I resolve this in favor of the checkmate rule.

The priority ranking is:

1) Checkmate
2) Stalemate
3) Fifty move rule
4) Repetition rule
5) Insufficient material rule

Checkmate, stalemate and insufficient material terminate the game immediately by rule whereas one has to claim a draw by fifty move rule or repetition else the game will continue. So insufficient material should have a higher priority than fifty move rule and repetition.

repetition draw bug

Re: An easy test for repetition draw detection

Re: An easy test for repetition draw detection

Re: An easy test for repetition draw detection

Re: An easy test for repetition draw detection

The rg and rgstat commands

Some minor ambiguities concerning game termination

Re: The rg and rgstat commands

Re: The rg and rgstat commands

Re: The rg and rgstat commands

Re: Some minor ambiguities concerning game termination