Repetition Detection Without Hashing

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Karatorian

Repetition Detection Without Hashing

Post by Karatorian » Sat Feb 13, 2010 10:16 pm

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
Posts: 292
Joined: Tue Jul 07, 2009 2:56 am

Re: Repetition Detection Without Hashing

Post by Aaron Becker » Sat Feb 13, 2010 10:27 pm

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

Re: Repetition Detection Without Hashing

Post by Karatorian » Sat Feb 13, 2010 10:31 pm

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.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition Detection Without Hashing

Post by hgm » Sat Feb 13, 2010 10:38 pm

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.
Last edited by hgm on Sat Feb 13, 2010 10:39 pm, edited 1 time in total.

User avatar
Graham Banks
Posts: 33138
Joined: Sun Feb 26, 2006 9:52 am
Location: Auckland, NZ

Re: Repetition Detection Without Hashing

Post by Graham Banks » Sat Feb 13, 2010 10:38 pm

Karatorian wrote: 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. 8-)
My email addresses:
gbanksnz at gmail.com
gbanksnz at yahoo.co.nz

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetition Detection Without Hashing

Post by hgm » Sat Feb 13, 2010 10:45 pm

Karatorian wrote: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

Re: Repetition Detection Without Hashing

Post by Karatorian » Sat Feb 13, 2010 11:00 pm

hgm wrote: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
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Repetition Detection Without Hashing

Post by jwes » Sat Feb 13, 2010 11:34 pm

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
Posts: 356
Joined: Thu Mar 09, 2006 2:01 pm

Re: Repetition Detection Without Hashing

Post by brianr » Sat Feb 13, 2010 11:39 pm

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

Re: Repetition Detection Without Hashing

Post by Karatorian » Sun Feb 14, 2010 1:51 am

jwes wrote: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.
brianr wrote: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.

Post Reply