CookieCat's early search termination

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

CookieCat's early search termination

Post by sje » Sat Jan 07, 2012 10:14 am

CookieCat has a pair of early search termination conditions based on score and applied at the end of each completed iteration past the second iteration. The idea is to stop early if the last two iterations produced a mating score or if they produced a getting mated score.

Two questions:

1) Should the last three (or more) results be tested instead of only two?

2) Should the mate/lose distances be considered?

Code: Select all

    procedure SpookyIterationSequence;
    begin
      with ssc do
        begin

          { Initialize the iteration index }

          iter := itermin;

          { Loop with one iteration per cycle }

          while SscIsGoing&#40;ssc&#41; and &#40;iter <= itermax&#41; do
            begin

              &#123; Run one iteration &#125;

              SpookyIterate;

              &#123; Handle early mate detection &#125;

              if SscIsGoing&#40;ssc&#41; and &#40;iter > 1&#41; then
                if IsSvMating&#40;iirvec&#91;iter&#93;.sv&#41; and IsSvMating&#40;iirvec&#91;iter - 1&#93;.sv&#41; then
                  SscStop&#40;ssc, stforcedmate&#41;;

              &#123; Handle early lose detection &#125;

              if SscIsGoing&#40;ssc&#41; and &#40;iter > 1&#41; then
                if IsSvLosing&#40;iirvec&#91;iter&#93;.sv&#41; and IsSvLosing&#40;iirvec&#91;iter - 1&#93;.sv&#41; then
                  SscStop&#40;ssc, stforcedlose&#41;;

              &#123; Next iteration &#125;

              Inc&#40;iter&#41;

            end;

          &#123; Ensure search termination &#125;

          if SscIsGoing&#40;ssc&#41; then
            SscStop&#40;ssc, stlimitdepth&#41;

        end
    end; &#123; SpookyIterationSequence &#125;

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: CookieCat's early search termination

Post by mcostalba » Sat Jan 07, 2012 2:40 pm

sje wrote: The idea is to stop early if the last two iterations produced a mating score or if they produced a getting mated score.
Interesting but they have no impact in engine play, when first iterations show mate/mated score is too late for anything interesting: you arrive at party ended !

User avatar
lucasart
Posts: 3035
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: CookieCat's early search termination

Post by lucasart » Sun Jan 08, 2012 12:45 am

sje wrote:CookieCat has a pair of early search termination conditions based on score and applied at the end of each completed iteration past the second iteration. The idea is to stop early if the last two iterations produced a mating score or if they produced a getting mated score.

Two questions:

1) Should the last three (or more) results be tested instead of only two?

2) Should the mate/lose distances be considered?

Code: Select all

    procedure SpookyIterationSequence;
    begin
      with ssc do
        begin

          &#123; Initialize the iteration index &#125;

          iter &#58;= itermin;

          &#123; Loop with one iteration per cycle &#125;

          while SscIsGoing&#40;ssc&#41; and &#40;iter <= itermax&#41; do
            begin

              &#123; Run one iteration &#125;

              SpookyIterate;

              &#123; Handle early mate detection &#125;

              if SscIsGoing&#40;ssc&#41; and &#40;iter > 1&#41; then
                if IsSvMating&#40;iirvec&#91;iter&#93;.sv&#41; and IsSvMating&#40;iirvec&#91;iter - 1&#93;.sv&#41; then
                  SscStop&#40;ssc, stforcedmate&#41;;

              &#123; Handle early lose detection &#125;

              if SscIsGoing&#40;ssc&#41; and &#40;iter > 1&#41; then
                if IsSvLosing&#40;iirvec&#91;iter&#93;.sv&#41; and IsSvLosing&#40;iirvec&#91;iter - 1&#93;.sv&#41; then
                  SscStop&#40;ssc, stforcedlose&#41;;

              &#123; Next iteration &#125;

              Inc&#40;iter&#41;

            end;

          &#123; Ensure search termination &#125;

          if SscIsGoing&#40;ssc&#41; then
            SscStop&#40;ssc, stlimitdepth&#41;

        end
    end; &#123; SpookyIterationSequence &#125;
the way i do this in double-check is as follows:
if mate in X or mated in X was returned by the root search, then stop the iterative deepening look at depth X. Indeed if a search at depth 5 returns a mate in 8 (due to search extensions and/or quiescent search) we don't want to trust it. We know there is a mate, but searching up to ply 8 may refine the mating line and find a mate in 7, let's say. On the other hand if we have a mate in 4, there's no need to search to depth 15. Of course this will probably not impact elo strength, but it just makes your engine look a bit more professional...

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: CookieCat's early search termination

Post by sje » Sun Jan 08, 2012 1:41 am

lucasart wrote:the way i do this in double-check is as follows:
if mate in X or mated in X was returned by the root search, then stop the iterative deepening look at depth X. Indeed if a search at depth 5 returns a mate in 8 (due to search extensions and/or quiescent search) we don't want to trust it. We know there is a mate, but searching up to ply 8 may refine the mating line and find a mate in 7, let's say. On the other hand if we have a mate in 4, there's no need to search to depth 15. Of course this will probably not impact elo strength, but it just makes your engine look a bit more professional...
Back in 1987, my program Spector used a similar scheme with the added refinement of a premature termination of an iteration if a "sufficiently fast" mate was found.

The risk, which increases with an increase in selectivity, is that what was found on one search may not be found on a another search two ply later. There are several reasons for this including an unexpected opponent reply, a tricky extension which in granted in the first search but not in the second, and a difference in time allocation.

Post Reply