Repetition Detection Without Hashing

[Karatorian]

I'm developing a Shogi Engine for the Game Boy Advanced. As the GBA has a very small amount of memory (32k CPU internal, 256k external), I haven't bothered with transposition tables or hashing of any kind as of yet.

The engine has implemented pretty much all of the rules of Shogi, except those related to repetition. The rules for repetition in Shogi are pretty similar to those of chess, except that four-fold, rather than three-fold repetition is required to draw, and that giving perpetual check is a loss for the check giver.

The techniques I've read about for repetition detection involve either storing some info in the transposition table, using a dedicated hash table, or using a list of hashes of previous positions. In all cases, this requires hashing to be implemented.

Due to the limited memory availible on the GBA, I'm not sure if I'm going to bother implementing a transposition table. In that case, I'm not sure I really want to implement hashing at all, as it's likely to slow down my move making and unmaking functions.

Furthermore, as there's no concept of a halfmove clock in shogi, one cannot use that to reduce the depth of the history list one needs to search.

So I was wondering if anyone could point me at an alternative scheme for detecting repetitions. Or am I just being silly? Is there enough memory availible to make a transposition table workable, so I should just implement hashing?

[Aaron Becker]

You don't need to use an actual transposition table to keep track of your position hash and use it for repetition detection. Just keep a list of the hash of each position seen so far in the game, and use that. The amount of memory needed is very small.

[Karatorian]

I realize that I don't need an actual transposition table. However, since I don't have one, I was wondering if there was an alternative method I could use to avoid the overhead of generating hashes every move.

Doh, I just realized I accidentally posted this in the wrong forum. If a mod reads this, could it please be moved over to the programming forum. Thanks in advance.

[hgm]

You have too little memory for a TT t have any use. But you can still calculate Zobrist keys for the positions, and store tem in an array of som 200 positions, that you clear on every irreversible move. That has nothing to do with a hash table, except that people who do implement a hash table use the same key for this, for convenience. A 32-bit key wuld long enough for this.

In Shogi you would need lot of Zobrist keys, as you have 13 piece types (times 2 colors) and 81 board squares, and holdings on top of it. So it would probably best to use a table of overlapping keys, so that you only need 1 byte per piece-square combination, and use an additive key in stead of an XOR'ed key to allow multiple pieces of the same type in the holdings. Then you can do with 82 x 2 x 13 ~2KB of Zobrist table.

[Graham Banks]

Doh, I just realized I accidentally posted this in the wrong forum. If a mod reads this, could it please be moved over to the programming forum. Thanks in advance.

Moved.

[hgm]

I realize that I don't need an actual transposition table. However, since I don't have one, I was wondering if there was an alternative method I could use to avoid the overhead of generating hashes every move.

Generating the hashes is an extremely cheap way to characterize a position, as yo do it differebtially. And comparing it with other positions (which you have to do quite a number of times, for each new hash you calculate) is is very cheap, as it is just an integer comparison. So I would be very surprised if anything could beat that.

To cut down on comparisons, you could use the lowest 8 bits as an index in your history table and start a linear search for an empty position or a repetition from that location (possibly, but not necessarily wrapping around). I.e. organize the history as a very small hash table, only listing the number of times a position occurred so far.

[Karatorian]

You have too little memory for a TT t have any use. But you can still calculate Zobrist keys for the positions, and store tem in an array of som 200 positions, that you clear on every irreversible move.

Except, in shogi there are no irreversable moves ^_^

That has nothing to do with a hash table, except that people who do implement a hash table use the same key for this, for convenience.

I know that, I was just wondering, since my engine doesn't have much use for hashing, if I could avoid it completely.

So it would probably best to use a table of overlapping keys, so that you only need 1 byte per piece-square combination, and use an additive key in stead of an XOR'ed key to allow multiple pieces of the same type in the holdings.

I'll have to look into that, thanks.

[jwes]

You have a few possibilities.
1. You can use Zobrist hashes. This is the fastest, though the tables can be large (H.G. Muller has posted ideas about making them smaller).
2. You could use another hashing method. This would use the least memory, but would be slower (I can't think of a way to do hashing incrementally except Zobrist).
3. You could use copy rather than make/unmake for positions. This is the simplest, but might be slow.
4. You could ignore repetitions. This is the easiest, but would hurt play. I don't know enough about Shogi to know how bad this would be.

Another idea is to only check for repetitions the first few plies. This would almost eliminate the speed penalty but might weaken play.

[brianr]

Older versions of GNUChess used a hashless repetition approach with some lists of from/to squares, obviously resetting for non-reversible moves.
I found some code in version 4.0 in search.c It takes some time to figure out, IIRC

Code: Select all

inline
int
repetition ()

/*  Check for draw by threefold repetition.  */

{
  register SHORT i, c, cnt;
  register SHORT f, t;
  SHORT b[64];

  cnt = c = 0;
  /* try to avoid work */
  memset ((CHAR *) b, 0, sizeof (b));
  for (i = GameCnt; i > Game50; i--)
    {
      f = GameList[i].gmove >> 8;
      t = GameList[i].gmove & 0x3f;

      if (b[f]) c--;
      if (b[t]) c--;
      b&#91;f&#93; = &#40;board&#91;f&#93; + &#40;color&#91;f&#93; << 8&#41;)
	     - &#40;board&#91;t&#93; + &#40;color&#91;t&#93; << 8&#41;) + b&#91;t&#93;;
      b&#91;t&#93; = &#40;board&#91;t&#93; + &#40;color&#91;t&#93; << 8&#41;) - &#40;no_piece + &#40;neutral << 8&#41;);
      if &#40;b&#91;f&#93;) c++;
      if &#40;b&#91;t&#93;) c++;
      if &#40;c == 0&#41;
        if ((&#40;i ^ GameCnt&#41; & 1&#41;)
	  cnt++;
    &#125;
  return &#40;cnt&#41;;
&#125;

[Karatorian]

1. You can use Zobrist hashes. This is the fastest, though the tables can be large (H.G. Muller has posted ideas about making them smaller).

Actually, size of the zobrist tables probably wouldn't be an issue. While RAM is limited, I can use quite a bit of ROM. So I could simply precompute the zobrist tables.

2. You could use another hashing method. This would use the least memory, but would be slower (I can't think of a way to do hashing incrementally except Zobrist).

Well, if I'm gonna hash, I'd do it right and use Zobrist hashing.

3. You could use copy rather than make/unmake for positions. This is the simplest, but might be slow.

I actually have had both copy and unmake implemented at one point to chase down bugs in my unmake code. Unfortunatly, I'm using bitboards (96 bit ones, no less), so memory usage again becomes an issue.

4. You could ignore repetitions. This is the easiest, but would hurt play. I don't know enough about Shogi to know how bad this would be.

That's what I'm currently doing. I don't know enough about shogi myself to know how much ignoring repetitions would hurt either. However, as perpetual check is a loss (for the check giver), it's not as though it simply makes the engine more drawish. However, I suppose this would only really matter when playing against something that enforces this rule (i.e not on the GBA). On the other hand, just ignoring a rule of the game seems wrong somehow.

Another idea is to only check for repetitions the first few plies. This would almost eliminate the speed penalty but might weaken play.

I'll have to think about that, or, I suppose, test it.

Older versions of GNUChess used a hashless repetition approach with some lists of from/to squares, obviously resetting for non-reversible moves.

I can't make heads or tails of that code. I guess I'd have to poke about the rest of the GNUchess source to figure it out.

However, it it does what I think it does, then it has a bit of an issue. That being, that it doesn't properly handle positions that arise from, for example, rooks switching places. (I read about something similar.) On the other hand, handling repetition by hash has the possibilty of hash collisions. So which is worse, false positives, or false negatives? And which is more likely?

It's looking like I'm gonna end up using Zobrist hashing. I suppose I should implement it and see how much of a slowdown it really is.