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?
Repetition Detection Without Hashing
Moderators: hgm, Rebel, chrisw
-
- Posts: 292
- Joined: Tue Jul 07, 2009 4:56 am
Re: Repetition Detection Without Hashing
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.
Re: Repetition Detection Without Hashing
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.
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.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Repetition Detection Without Hashing
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.
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 11:39 pm, edited 1 time in total.
-
- Posts: 41451
- Joined: Sun Feb 26, 2006 10:52 am
- Location: Auckland, NZ
Re: Repetition Detection Without Hashing
Moved.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.
gbanksnz at gmail.com
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Repetition Detection Without Hashing
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.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.
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.
Re: Repetition Detection Without Hashing
Except, in shogi there are no irreversable moves ^_^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.
I know that, I was just wondering, since my engine doesn't have much use for hashing, if I could avoid it completely.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'll have to look into that, thanks.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.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Repetition Detection Without Hashing
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.
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.
-
- Posts: 536
- Joined: Thu Mar 09, 2006 3:01 pm
Re: Repetition Detection Without Hashing
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
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[f] = (board[f] + (color[f] << 8))
- (board[t] + (color[t] << 8)) + b[t];
b[t] = (board[t] + (color[t] << 8)) - (no_piece + (neutral << 8));
if (b[f]) c++;
if (b[t]) c++;
if (c == 0)
if (((i ^ GameCnt) & 1))
cnt++;
}
return (cnt);
}
Re: Repetition Detection Without Hashing
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.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).
Well, if I'm gonna hash, I'd do it right and use Zobrist hashing.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).
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.3. You could use copy rather than make/unmake for positions. This is the simplest, but might be slow.
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.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.
I'll have to think about that, or, I suppose, test it.Another idea is to only check for repetitions the first few plies. This would almost eliminate the speed penalty but might weaken play.
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.brianr wrote:Older versions of GNUChess used a hashless repetition approach with some lists of from/to squares, obviously resetting for non-reversible moves.
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.