janggi pass move implementation: question to HGM mainly

[maksimKorzh]

Mr. Muller

I really stuck at pass move implementation. I mean conceptually.
So the rules state that more than 2 pass moves in the row results the end of game (end of a branch traversal in perft)
and I feel very lost regarding picking up the proper implementation concept.
My problem is that the matter of pass move detection regards to different plies within the search (perft),
let's say PV: blueMove redMove bluePass redPass blueMove is legal
while this one: blueMove redMove bluePass redPass blueBass is not

I can detect if previous move was redPass - I did it the same way as null move detection to avoid 2 null moves in the row,
however this is wrong, I need to check something like: "if ply-2 movelist contained pass move (assert(ply-2 move sideToMove == current ply move sideToMove)) then prune current passMove"
but this already involves an additional data structure to associate root moves of a certain depth (root pass move in this case) with a certain plies - similarly how it's done in triangular PV table, but this seems to be too complicated for just a move generator.

Of course I could've go for pruning the illegal passes during search basing on PV line itself but fairy stockfish does this pruning on move generation stage,
hence the eventual number of traversed nodes rely on the pruning of the illegal pass moves. So to calibrate my movegen I need to prune illegal pass moves on move generation stage but I have no clue how properly to do that.

Can you please suggest something?

[hgm]

I haven't really thought about this, because my engine does not pass at all.

But it seems wrong to consider the second consecutive repetition a move. It seems more like an opportunity to claim a draw. If the rule is as you say, I would immediately scoe a null move as 0 (or whatever draw score the rules prescribe), rather than searching it, in a node reached through a null move.

[maksimKorzh]

I haven't really thought about this, because my engine does not pass at all.

But it seems wrong to consider the second consecutive repetition a move. It seems more like an opportunity to claim a draw. If the rule is as you say, I would immediately scoe a null move as 0 (or whatever draw score the rules prescribe), rather than searching it, in a node reached through a null move.

re: I haven't really thought about this, because my engine does not pass at all.
- I would be happy to drop that as well if only this didn't affect the perft results.
I just can't sleep well if my movegen can potentially make illegal moves.

re: It seems more like an opportunity to claim a draw
- exactly, but your work around implements it in search, not perft and that's the issue.

The way fairy stockfish does it in essence is:

Code: Select all

/// Position::is_immediate_game_end() tests whether the position ends the game
/// immediately by a variant rule, i.e., there are no more legal moves.
/// It does not not detect stalemates.

bool Position::is_immediate_game_end(Value& result, int ply) const {
  ...
  // Check for bikjang rule (Janggi) and double passing
  if (st->pliesFromNull > 0 && ((st->bikjang && st->previous->bikjang) || ([b]st->pass && st->previous->pass[/b])))
  {
      result = var->materialCounting ? convert_mate_value(material_counting_result(), ply) : VALUE_DRAW;
      return true;
  }
}

And then in movegen:

Code: Select all

template<>
ExtMove* generate<LEGAL>(const Position& pos, ExtMove* moveList) {

  if (pos.is_immediate_game_end())
      return moveList;

  ExtMove* cur = moveList;

  moveList = pos.checkers() ? generate<EVASIONS    >(pos, moveList)
                            : generate<NON_EVASIONS>(pos, moveList);
  while (cur != moveList)
      if (!pos.legal(*cur))
          *cur = (--moveList)->move;
      else
          ++cur;

  return moveList;
}

Here's what I do.

Code: Select all

// perft driver
void perftDriver(int depth, int lastMove) {  
  if  (depth == 0) {
    nodes++;
    return;
  }
  
  Moves moveList[1];
  generateMoves(moveList, ALL_MOVES);
  
  for (int count = 0; count < moveList->count; count++) {      
    int move = moveList->moves[count].move;
    //if (lastMove == move) in this case current move is pass and lastMove is pass;
    // current move CAN be done and it would be a draw offer (or resign in some variants if material score of passing side is < score of winning side)
    // however after this move is made on board opponent (no matter if he is better or worse) can't pass in return
    // and I have no idea of how to implement this in movegen and perft, but not in search
    if (makeMove(move) == 0) continue; // printBoard(); getchar();
    perftDriver(depth - 1, lastMove);
    takeBack(move); // printBoard(); getchar();
  }
}

// perft test (pass move is counted as the node)
void perftTest(int depth) {
  printf("   Performance test:\n");
  
  nodes = 0;
  uint64_t startTime = getTimeMs();
  
  Moves moveList[1];
  generateMoves(moveList, ALL_MOVES);
  
  for (int count = 0; count < moveList->count; count++) {
    int move = moveList->moves[count].move; // if (move != 39578) continue; 
    if (makeMove(move) == 0) continue; // printBoard(); getchar();
    uint64_t cumNodes = nodes;
    perftDriver(depth - 1, move == 39578 ? move : -1); // 39578 is a constand for "pass" move
    takeBack(move); // printBoard(); getchar();
    uint64_t oldNodes = nodes - cumNodes;
    printf("   move: %s%s  nodes: %lld\n", // print only one square for pass move
                                           move == 39578 ? "" : 
                                           COORDINATES[getSourceSquare(move)],
                                           COORDINATES[getTargetSquare(move)],
                                           oldNodes);
  }
  
  printf("\n   Depth: %d", depth);
  printf("\n   Nodes: %lld", nodes);
  printf("\n    Time: %lld ms\n\n", getTimeMs() - startTime);
}

I don't know... Without implementing this damned pass rule I'm just loosing the motivation to proceed.

[maksimKorzh]

I've just disabled pass move in fairy stockfish and for now at very least I can calibrate my movegen without pass moves.

[hgm]

The problem seems not so much that you don't get a correct perft, but that you want to exactly mimic whatever strange things Stockfish does.

[maksimKorzh]

The problem seems not so much that you don't get a correct perft, but that you want to exactly mimic whatever strange things Stockfish does.

After disabling fairy stockfish's pass move feature I started getting correct perft results for specific positions like 9/4k4/9/9/9/9/9/9/4K4/9 w - - 0 1.
So from now on I would be able to debug just as if it was xiangqi without bikjang.
However the problem is that "pass move" is a legal move and without having it generated normally like all pseudo-legal moves
that gets pruned in case if two passes has already occurred within the current branch. Without having this I'll need to hack in the search
to say somehow allow to pass a move in case of stalemate (I don't even say that passing a move potentially might be better, say in zugzwang).
And also I would probably need to handle null move pruning somewhat different for pass moves.

So I just want to keep the structure as clear and as didactic as possible so that move generation with pass moves is the matter of move generation only while search is the matter of search. I understand that even king captures can be pruned via beta-cuttoffs like you do in microMax type engines but
that is too obfuscated from the code structure perspective and I'm trying to make dead simple implementation of whatever.
See my xiangqi engine for instance(movegen): https://github.com/maksimKorzh/wukong-x ... ng.js#L541

With janggi I'm forced to implement something that only exists in fairy stockfish but the way it's done there is too complicated.
The problem is I start being especially dumb when it comes to implementing something on my own from scratch.
That's the reason why I initially asked this question.

[hgm]

Well, you should count nullmoves in perft, but I think it is against the spirit of perft to terminate a branch merely because of a repetition rule. (And this consecutive passing is a case of repetition.) We don't do that in perfts for Chess either. You might argue that in that case the draw is merely claimable, and not forced. But that would not be true for a 5-fold repetiton, and the option to claim the draw is not counted as an extra move.

So I think the proper counting methodology for Janggi would be to treat turn pass as a move that is always valid, no matter how many null moves were played before. You also don't take into account other repetition rules, don't you? Like that it would be illegal to play a Pawn 3 times in a row between e4 and d4.

BTW, I always thought that the King capture is really the most clean and fundamental way to do it. It is the entire basis of Chess: you win by capturing the opponent's King. That it is illegal to expose yourself to immediate loss, that is an obfuscation. And in fact a strange quirk of FIDE rules that it makes a distinction between immediate loss and illegal. (In Shogi that is exactly the same. But in Chess illegal moves have to be taken back. And even that is what a King-capture search does. With a score that is so bad that the move can never be chosen.)