ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Skipping duplicat moves
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 21538
Location: Amsterdam

PostPost subject: Skipping duplicat moves    Posted: Sun Dec 03, 2017 10:30 pm Reply to topic Reply with quote

My engines often search hash moves or killers before move generation has been done. That leads to the annoying complication that duplicats of these moves will be generated later. To prevent those from being searched a second time, you would have to compare each move against a hash move and two killers before you search it. Or when you generate it. (With the risk that you never would get to it because of a cutoff.)

In micro-Max I take the lazy approach, and rely on the duplicats causing a hash hit on their initial search result. That leads to redundant make/unmake and hash probe for one move (micro-Max doesn't use killers), but make/unmake is very fast (mailbox without piece list), and the hash entry should still be cached from the previous search of the move. So you won't lose much compared to doing a simpler test (than a hash probe) on all the moves.

But this starts to fail under large hash pressure. And it would of course not work at all without hash tables. (Where this is still an issue, because the move of a previous IID iteration will serve as 'hash move' in the next iteration, and you still have to deal with killers.)

Another problem is that I often use an IID scheme that first verifies if a beta cutoff in a non-final iteration will hold all the way up to the requested depth, before stepping up the iteration depth. (So that when the move fails low after all, the search for an alternative can continue at the lower depth, preserving the advantages of IID.) This creates another situation where a move has already been sufficiently searched. E.g. in the d=2 iteration of a d=6 node, where the move still seemed to cut at d=5, but then failed low at d=6. The IID then resumes the d=2 iteration, and after that finishes without a cutoff, it will revisit the move for d=6 (or perhaps d=4), while redoing searches at those depth is pointless, as the d=6 result was already obtained. Again, you can hope for the hash hit on the 'over-deep' result to save the day.

But now I am programming for a machine where hash tables are unaffordable (32KB RAM). So I cannot ignore the problem anymore. Move lists are still affordable, though. So the IID problem could be solved by keeping a depth and score with each move in the move list, to hold the deepest result obtained for it so far. This acts as a sort of private cache for the hash entries of all daughters, which canot be overwritten, and the parent could cheaply probe that table before embarking on a search of the move. It would not help against moves that are in the list twice. And of course it makes some overhead to initialize the extra info in the move list.

This consideration, plus the fact that the machine I am writing for has difficulty crossing (256-byte) memory page boundaries, and handling data types longer than 8 bits, made me look for a more compact idea than a move list. Finally I came up with the following:

In a give position, each move can be encoded in a single byte. This can be done reasonably efficiently, if from-square, to-square and the piece number (the index in the piece table) of the moved piece are all known. (As they must be at the start of MakeMove.) It just requires two lookups in small tables:

moveCode = stepCode[fromSqr - toSqr] + pieceCode[pieceNr];

A move along (say) a file needs only 7 codes to be unique, although the distance moved can range from -7 to +7, because for any location at most 7 of these 14 possible targets can be on the board. So a Queen needs 4*7 = 28 codes to unambiguously identify her move, and a Rook or Bishop only 14. Pawns need 4 (because of the double push), and Knights and King 8. The numbering of the step vectors can be done such that all the codes for Knight jumps, as well as white and black Pawn moves are contiguous, and the King moves only have a single hole (so it spans 9 codes). Rooks and Bishops are perfectly complementary, so no matter how you assign the stepCodes, a Rook and Bishop with the same pieceCode will never have any of their moves collide; it is just encoded like a Queen, and depending on whether the described move is orthogonal or diagonal you kow if the Rook or Bishop was meant. A full FIDE army needs only 141 codes, and even allowing an extra Queen gives only 169.

So a 256-byte page could hold this no problem. But memory is not that abundant, and I would need to hold at least a two-byte score and a depth. And usually there would be only 30-40 moves in the position, and usually only a small fraction of those would have been searched deeper than the current depth iteration requested. (And at most 3 would be hash or killer.) So it seems better to map the move code into a 128-entry table. Only 13 entries then could suffer a collision, and by picking the codes in a clever way it can be arranged that Pawn moves collide with distant (4-step) slider moves. Pawns only rarely have their capture moves, and on a board full of Pawns sliders usually do not move very far.

Still, there must not be any ambiguity, so the collisions must be resolvable by a signature in the table, for which we could use the from-square. Perhaps we can even afford to use a 64-byte table that way. This would typically map 2 (and rarely 3) moves to the same entry. One memory page could then hold 64 entries consisting of from-square, depth and 2-byte score.

Such a table could have another interesting application, namely storing counter moves. When we immediately deepen cut moves until they fail low or reach final depth, the first IID iteration will either fail high (to full depth), in which case we are done, or fail low after searching all moves (some possibly to higher depth). In the latter case each move would have been refuted by a cut move in the respective daughter. We could make the daughter return that cut move, and store it in the table. And then, in the next IID iteration, pass it to the daughter as hash move.

This would require us to add a fifth byte to the table entries, though. (The packed move encoded in the daughter position could be stored there.) This is a bit awkward. But each ply level would need some local variables anyway, in addition to this private hash cache, and there should be 64 spare bytes in that second page. Then each ply level would use two 256-byte memory pages, which is affordable.

Note that on entering the node, it would find the table as another node at the same ply level would have left it. We'd rather not spend time on clearing the table. This seems to be possible through the following code:

Code:

Search(alpha, beta, depth, hashMove)
{
  int8 moveDepth[256]; int16 moveScore[256];
  int mCode, hCode;
  iterDepth = 0;
  keyMove = 64;
  moveDepth[hCode] = 0; // clear any hash move we might have inherited
  while(iterDepth++ < depth) { // IID
    if(hashMove) { // we have a 'hash move' (from previous iter, or PV)
      MakeMove(hashMove);
      d=iterDepth-1;
      while(d++ <depth) {
        score = -Search(-beta, -alpha, d-1, NOMOVE);
        depthReached = d;
        if(score < beta) break;
      }
      UnMake();
      if(score > alpha) {
        alpha = score;
        if(score >= beta) return beta;
      } else hashMove = NOMOVE; // it failed low, don't keep it     
      mCode = hCode = Pack(hashMove);
      moveDepth[mCode] = depthReached + keyMove; // label as hash move; d could be > iterDepth
      moveScore[mCode] = score;
    }
    for(ALL_MOVES) {
      mCode = Pack(move);
      oldDepth = moveDepth[mCode];
      if(oldDepth >= keyMove) { // in first iter, keyMove = 64 and only the hash move can beat that
        moveDepth[mCode] &= ~64; // clear the hash marker, but leave its depth
        score = moveScore[mCode]; // use the previously calculated result for the duplicat or previously over-deep searched move
      } else { // on first iter, all other moves than hash go here
        MakeMove(move);
        d = iterDepth-1;
        while(d++ < depth) {
          score = -Search(-beta, -alpha, d-1, NOMOVE);
          depthReached = d;
          if(score < beta) break;
        }
        UnMake();
        if(depthReached > iterDepth) { // move has had an extra deep 'preview'
          moveDepth[mCode] = depthReached; // remember that for next iter
          moveScore[mCode] = score;
        } else
           moveDepth[mCode] = 0; // this makes sure we overwrite any uninitialized stuff
     }
      if(score > alpha) {
        alpha = score;
        if(score >= beta) return beta; // stop iterating after cutoff
        hashMove = move; // found new best move
      }
    } // iteration failed low
    keyMove = 0; // all data in table is now from this node; allow its use
  }
}

This has very little overhead; calculating the mCode is not more work than comparing with hash and killers to see if we have a duplicate (or remove those from the move list). If mCode is hashed to a smaller index, there should be some more work for vetting a hit, but I care little how much it costs to treat a hit, as it saves an enormous amount of work by skipping a search. What worries me is the overhead on misses, what you do on every move for no payback.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Skipping duplicat moves H.G.Muller Sun Dec 03, 2017 10:30 pm
      Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 9:08 am
      Re: Skipping duplicat moves Steve Maughan Mon Dec 04, 2017 2:00 pm
            Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 2:52 pm
                  Re: Skipping duplicat moves Steve Maughan Mon Dec 04, 2017 3:07 pm
                        Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 6:16 pm
      Re: Skipping duplicat moves Álvaro Begué Mon Dec 04, 2017 6:17 pm
            Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 6:50 pm
                  Re: Skipping duplicat moves Sven Schüle Mon Dec 04, 2017 10:19 pm
                        Re: Skipping duplicat moves H.G.Muller Tue Dec 05, 2017 10:35 am
                              Re: Skipping duplicat moves Michael Sherwin Mon Dec 11, 2017 10:48 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads