TalkChess.com

[Vincent Diepeveen]

On keysize.

the classical approaches on how many bits of Zobrist you need for which application are all pretty flawed.

In Diep i'm using internal 128 bits Zobrist keys from which i store, together with the lookup bits, say around a 80 bits or so.

One key i use as a lookup, the other for storing bits from.

Sometimes if i change the hashtable lookup/store functions then this changes then i store a few bits more then a few less.

Now most will get away with 64 bits in chess, the real question you have to ask your self is not: "how big is the game", but "how big is the search space that a search could potentially hit while playing a game".

In the hashtable replacement system as i posted already around 1999-2000 on the forums, you can see that i'm using 8 probes and overwriting the entry with the count, where count = searchdepthleft + searchdoneingame

At start of game i reset the 'searchdoneingame' counter and each time its searching it gets incremented by 1. So in a normal game this is similar to number of moves from the openingsposition.

In short it's very likely if we play a few moves that we still have entries left from many moves ago.

That means that the effective searchspace you can reach is quite a lot larger than the simple minded '1 bit approach' from Ernst A Heinz.

To start with after 2 searches we get an overwrite 'collission' so to speak if we just use 1 bit and it's not likely that we did overwrite all entries of previous search already. Furthemore, it wouldn't be the first time that we pondered on the wrong move, a move that got us in a total different SEARCH SPACE.

As that's the crucial word. The size of the search space we can potentially reach is determining the size of the key we need. furthermore i'm of the opinion that i want 0 collissions let alone 0 errors.

Many chessprogrammers are fine with a bunch of collissions and a few errors in fact. If you assume that a few errors isn't a problem, then suddenly you can stick to 64 bits for any game for the coming 100 years

And o boy you'll lose some games in those years because of that as Murphy's law always applies in games.

Yet if we assume we want 0 collissions then suddenly the only relevant thing is the total search space we can reach within a single search.

Now the boardsize might seem impressive, it just means we got more legal moves. More legal moves means we can search at high sub dozen million nps figures, letting deep blue seem like a slow beancounter in fact. Parallellizing with so many legal moves possible is going to be easy, even for beginning software engineers.

Also in the displayed games, we have deep forced mating sequences dropping a bunch of pieces around the king in order to mate him.

So there is no discussion about the huge search space that you will be able to reach. Calculating how many bits you actually need for this game is yet another discussion. I just dropped '512' bits as an example.

If we compare chess: Using around a 70+ bits seems pretty safe right now.
The game has in theory a tad more than 10^40 possibilities, yet if we go

In itself 10^38 is 2^128 already.

With a 36x36 board and 200 pieces, knowing in shogi if you capture a piece you can drop it yourself again at the board, you will have a lot more possibilities i bet than that.

For sure this is a game that will take forever to play