chessjoker

[mcostalba]

But because today I am in a good mood I want to give the correct solution:

An even better solution is to use instead of a joker piece, one of the following different zobrist pseudo-piece keys:

Code: Select all

JOKER_0, JOKER_P, JOKER_N, JOKER_B, JOKER_R, JOKER_Q, JOKER_K

Where JOKER_0 is used at game start.

When my opponent moves I update the position hash key in the usual way, but at the end I do:

Code: Select all

pos_key ^= Zobrist::psq[joker_current_value][joker_sq] ^ Zobrist::psq[joker_new_value][joker_sq];

The resulting pos_key, updated as described, can be used flawless in all the cases.

[hgm]

Code: Select all

Key tt_key() {
  return pos_key ^ Zobrist::psq[joker][joker_sq] 
                 ^ Zobrist::psq[joker_alias][joker_sq];
}

Before storing a position in TT remove the joker and substitute it with its alias piece, compute the resulting key and store that.

Upon probing the TT, compare the retrieved TT key with the pos key after having replaced the joker, if key matches you have a hit.

Not sure what exactly you describe here; "before storing a position in TT" is a bit ambiguous. Are you proposing to use the original pos_key to derive the index, and replace the Joker only in the signature you store there? Or is the replacement already done before you decide where to store?

The latter seems plain wrong: a position with a Joker mascarading as a Queen will be a quite different position as one with a true Queen on that same square, as the Joker will revert to something else on the next move. They should not be mapped to the same key. In the former case it seems just a cumbersome way to store the 'current Joker type' in the TT at the expense of a number of key bits (possibly a number of key bits that was redundantly stored anyway). With the disadvantage that all different transpositions (differing only in the current Joker type because of the preceding move) now map all to the same entry/bucket, overwriting each other.

[mcostalba]

Not sure what exactly you describe here;

Please do continue reading, there is a follow up post...did you missed it?

[hgm]

An even better solution is to use instead of a joker piece, one of the following different zobrist pseudo-piece keys:

Code: Select all

JOKER_0, JOKER_P, JOKER_N, JOKER_B, JOKER_R, JOKER_Q, JOKER_K

Where JOKER_0 is used at game start.

Indeed, this would certainly work.

Updating such 'transient' key components (like e.p. square and stm) incrementally is usually counterproductive, though: you would have to apply it and then remove it for the next move. 'Copy-make' beats 'do-undo' in this case.

Using a square-dependent key for the Joker alias is a bit redundant, however. It is used here as a kludge to make sure that in absence of a Joker the 'Joker alias' does not affect the key. But the price is high, because you have to update joker_sqr, and use some trick to let it point to a dummy key that is zero when no Joker is present. Plus that it gets you into trouble when there would be multiple Jokers on the board.

In fact, all you would want is a signature of the current Joker piece type in the key when there is at least one Joker. So having an extra transient key jokerKey[pieceType][nrOfJokers] seems the cleanest solution, where the tabulated value would be 0 for nrOfJokers=0, and otherwise some random value independent of nrOfJokers. To save some table space you could calculate the key on the fly as jokerKey[piecetype]*!!nrOfJokers. or jokerKey[pieceType] & -(nrOfJokers > 0).

[mcostalba]

Using a square-dependent key for the Joker alias is a bit redundant, however. It is used here as a kludge to make sure that in absence of a Joker the 'Joker alias' does not affect the key. But the price is high, because you have to update joker_sqr, and use some trick to let it point to a dummy key that is zero when no Joker is present. Plus that it gets you into trouble when there would be multiple Jokers on the board.

No you have not understood at all. JOKER_0 is _not_ to be used when there are no jokers, but at starting position when the type of joker is not defined because there is not an opponent's previous move.

In fact, all you would want is a signature of the current Joker piece type in the key when there is at least one Joker. So having an extra transient key jokerKey[pieceType][nrOfJokers] seems the cleanest solution

This is completely broken, but I will let you to figure it out yourself.

I just add that an alternative solution to avoid multiple joker pseudo-pieces per-square hash keys is to use only one per-square JOKER zobrist key set, considering it just another piece and then update the hash key upon opponent move in this way:

Code: Select all

pos_key ^= Zobrist::psq[piece_old][joker_sq] ^ Zobrist::psq[piece_new][joker_sq]; 

So for instance if opponent moves a rook and current joker aliases a bishop the key is updated, after usual updating code, as following:

Code: Select all

pos_key ^= Zobrist::psq[bishop][joker_sq] ^ Zobrist::psq[rook][joker_sq]; 

This scheme has the disadvantage that when you move a joker, you have to move also the corresponding piece, so, in the above example, if I move the rook-joker from old_sq to new_sq, after the usual key updating I have to add:

Code: Select all

pos_key ^= Zobrist::psq[rook][old_sq] ^ Zobrist::psq[rook][new_sq]; 

So all in all I still prefer my previous scheme.

[hgm]

No you have not understood at all. JOKER_0 is _not_ to be used when there are no jokers, but at starting position when the type of joker is not defined because there is not an opponent's previous move.

Yes, that was obvious to me, and I don't see how what I wrote could make you think otherwise. I did not even mention JOKER_0. My point was that when there is no Joker your code would not work. Unless Zobrist::psq[joker_value][???] would somehow contain 0 for some invalid square number ??? to which you set joker_sqr when there are no Jokers.

I just add that an alternative solution to avoid multiple joker pseudo-pieces per-square hash keys is to use only one per-square JOKER zobrist key set, considering it just another piece and then update the hash key upon opponent move in this way:

Code: Select all

pos_key ^= Zobrist::psq[piece_old][joker_sq] ^ Zobrist::psq[piece_new][joker_sq]; 

What value would joker_sq have, then, when you had two Jokers?

So for instance if opponent moves a rook and current joker aliases a bishop the key is updated, after usual updating code, as following:

Code: Select all

pos_key ^= Zobrist::psq[bishop][joker_sq] ^ Zobrist::psq[rook][joker_sq]; 

This scheme has the disadvantage that when you move a joker, you have to move also the corresponding piece, so, in the above example, if I move the rook-joker from old_sq to new_sq, after the usual key updating I have to add:

Code: Select all

pos_key ^= Zobrist::psq[rook][old_sq] ^ Zobrist::psq[rook][new_sq]; 

Well, you bring that on yourself by doing things incrementally. When you had just done none of what you write, but in stead replace HashProbe(pos_key) by

HashProbe(pos_key ^ Zobrist::psq[piece_moved][joker_sq])

you would not have to undo anything, and moving the Joker would require no correction at all. One would have to be careful what piece-moved was when the previous ply mover a Joker. (Perhaps I did not look careful enough, but I couldn't find anything in the rules about this.)

[mcostalba]

My point was that when there is no Joker your code would not work. Unless Zobrist::psq[joker_value][???] would somehow contain 0 for some invalid square number ??? to which you set joker_sqr when there are no Jokers.

Look, I have a new wonder for you. It is called 'for statement'

Code: Select all

  
  for (Jokers* j = jokers().begin(); j != jokers().end(); ++j)
  {
      pos_key ^=  Zobrist::psq[j.piece][j.sq]
                ^ Zobrist::psq[joker_new_piece][j.sq];

      j.piece = joker_new_piece;
  }

[mcostalba]

And because all jokers have same piece type and same new piece we can do even better:

Code: Select all

 
  Bitboard b = pos.pieces(us, JOKER);
  
  while (b)
  {
      Square sq = pop_lsb(&b);
      pos_key ^=  Zobrist::psq[joker_cur_value][sq]
                ^ Zobrist::psq[joker_new_value][sq];
  }

[hgm]

OK, so you want to loop over it. That makes it even more inefficient. And it doesn't really affect the incremental vs temporary-from-scratch issue

Still, the game state of this game seems only determined by the usual board state plus current joker_alias (and the latter only when there actually are Jokers). Not by where the last-moved piece was located. While the location of the Jokers is already encoded in the board position, so there is no need to encode it a second time.

So the use of a per-square key for this seems redundant, and looping over it even more so.

[mcostalba]

So the use of a per-square key for this seems redundant, and looping over it even more so.

Once you have some working code, I'd be glad to see your solution. Please only working code, no bla bla. Thanks.