Transposition table random numbers

[wgarvin]

Worse in what way? There are a series of tests, poker test, runs test, uniformity test, etc, that should _all_ be used to screen PRNGs. The MT algorithm has been pretty thoroughly tested. Particularly since we only need a few numbers and not millions.

PRNG tests are pretty standard. But does it necessarily mean that something that is better in PRNG tests is better strength wise?
Not necessarily, at least according to what I've tested.
I've tested with 3 different hash sizes (8MB, 32MB, 128MB) and 3 different TCs (1'+1'', 40/4', 40/20') and never got a version with MT (I used the default seed) outperforming the original version (within error margins - it was 2k games self-test). As a matter of fact, the original version was almost always better (on one occasions even with LOS over 95%).

A couple of years ago we had a PRNG debate here. I tried several and found _zero_ differences with respect to Elo. You will find one set of random numbers that works better on a given set of positions, another set of random numbers that works best on a different set of positions. There is hardly any PRNG around that can't spit out 1,000 decent random numbers. The issues come way later when you get into cycles. I've never seen one that would think about cycling after just 1,000.

I think trying to measure effectiveness is hopeless for such tiny potential changes... 2K games is nowhere near enough as the potential gain is in the +/- 1 Elo or less, unless you have some horrible PRNG. The twister is hardly horrible. I use the PRNG from Knuth's book since the source (in C) was publicly available.

Yes, its been discussed here more than once. Maximum hamming distance between pairs of your 769 keys doesn't mean squat, because real board positions will have lots of those keys XORed together -- usually a dozen or more of them.

Choosing decent 64-bit pseudo-random numbers is all you need to do to get a very low collision rate. (I don't think anyone has demonstrated an alternate technique for choosing keys that gives significantly better collision rates than just using pseudo-random values).

If you have BAD psuedo-random numbers, you might get more collisions than you should (e.g. if you just used rand() and didn't notice that it only gives you a 15-bit number!). If you use a PRNG like the Mersenne Twister, and make sure you're actually putting 64 bits of output into your 64-bit keys, then everything will be fine.

[AlvaroBegue]

What is 769? It seems to be 64*12+1. I guess it's just the 12 piece types (although pawns on ranks 1 and 8 shouldn't matter much) plus one for whose turn it is?

If that's the case, you are missing en-passant information, which can be important (Ruy-López lost a game against Diep in WCCC'99 partly because of not doing this), and castling (I don't think castling matters in practice).

Also, you may want to use "0x0000000000000001" as the number for whose turn it is: It improves cache usage when you use null-move pruning, since both entries are in the same cache line.

[jdm64]

What is 769? It seems to be 64*12+1. I guess it's just the 12 piece types (although pawns on ranks 1 and 8 shouldn't matter much) plus one for whose turn it is?

If that's the case, you are missing en-passant information, which can be important (Ruy-López lost a game against Diep in WCCC'99 partly because of not doing this), and castling (I don't think castling matters in practice).

Also, you may want to use "0x0000000000000001" as the number for whose turn it is: It improves cache usage when you use null-move pruning, since both entries are in the same cache line.

Actually, the engine I'm creating is not traditional chess, but Genesis Chess. There is no en-passant or castling. So I should only need the 769.

[bob]

What is 769? It seems to be 64*12+1. I guess it's just the 12 piece types (although pawns on ranks 1 and 8 shouldn't matter much) plus one for whose turn it is?

If that's the case, you are missing en-passant information, which can be important (Ruy-López lost a game against Diep in WCCC'99 partly because of not doing this), and castling (I don't think castling matters in practice).

Also, you may want to use "0x0000000000000001" as the number for whose turn it is: It improves cache usage when you use null-move pruning, since both entries are in the same cache line.

There are 12 different piece types (counting black and white separately) with 64 squares the pieces can reach. So you start with 12 * 64 = 768. Then you have 4 castle status possibilities for each side, or a total of 8. Now you are at 776. Finally you need enpassant pawn capture indicators, 8 per side. 776 + 16 = 792. From this you can save 16 by getting rid of the numbers for pawns on 1st or 8th rank, so back to 776. You can reduce the EP indicator to just 1 value if you want, since you could never have two different ep targets in one position. All you need to do is differentiate between position P where an ep capture is possible and the same position where it is not. One random number is enough. In crafty, I have 4 castle randoms. I initially hash them in when the game starts, and if either rook moves, I XOR in that value (one of 2 for each side) while if the king moves I XOR in both.

Best reckoning, minimal number = 768 + 4 + 1 (pieces + castle status + ep) and you can lop 16 off the pawn values for 1st/8th rank as well, which will get you down to 757, total.

BTW I don't have a "side to move" random. It is easier (and faster) to just complement the hash signature if it is btm, and leave it alone if it is wtm. In 1/2 of the probes you don't do anything since it is wtm, in the other 1/2 you just complement the signature which guarantees it won't match with the same position other side to move. Then you avoid the xor for _every_ probe.

[bob]

What is 769? It seems to be 64*12+1. I guess it's just the 12 piece types (although pawns on ranks 1 and 8 shouldn't matter much) plus one for whose turn it is?

If that's the case, you are missing en-passant information, which can be important (Ruy-López lost a game against Diep in WCCC'99 partly because of not doing this), and castling (I don't think castling matters in practice).

Also, you may want to use "0x0000000000000001" as the number for whose turn it is: It improves cache usage when you use null-move pruning, since both entries are in the same cache line.

Actually, the engine I'm creating is not traditional chess, but Genesis Chess. There is no en-passant or castling. So I should only need the 769.

You mean 768, and what about castling?? That should add another 4 or 8.

[jdm64]

What is 769? It seems to be 64*12+1. I guess it's just the 12 piece types (although pawns on ranks 1 and 8 shouldn't matter much) plus one for whose turn it is?

If that's the case, you are missing en-passant information, which can be important (Ruy-López lost a game against Diep in WCCC'99 partly because of not doing this), and castling (I don't think castling matters in practice).

Also, you may want to use "0x0000000000000001" as the number for whose turn it is: It improves cache usage when you use null-move pruning, since both entries are in the same cache line.

Actually, the engine I'm creating is not traditional chess, but Genesis Chess. There is no en-passant or castling. So I should only need the 769.

You mean 768, and what about castling?? That should add another 4 or 8.

768 would be all (piece-type * square) combinations and the last 1 is side to move. Side to move is needed right?
And as I bolded in the quote above, there is no castling in my chess variant.

[hgm]

You will need keys to indicate the number of pieces you are still holding, though.

The simplest way to do this is to use an additive key, rather than an XOR based key. In that case you would only need one key for every (colored) piece type, because you can add that key multiple times (e.g. add 5 times the white Pawn key if you are still holding 5 white Pawns).

Basically the extra keys would be the keys for the "65-th square", i.e. the holdings. But unlike other squares, multiple pieces can be on that holdings 'square', so the XOR scheme would not work for it.

Of course you can work around that with a contrived system where you assigne independent keys to every (pieceType, number) combination, but that just leads to cumbersome extra table lookups during hash-key update. While changing ^ into + doesn't cost anything.

[bob]

What is 769? It seems to be 64*12+1. I guess it's just the 12 piece types (although pawns on ranks 1 and 8 shouldn't matter much) plus one for whose turn it is?

If that's the case, you are missing en-passant information, which can be important (Ruy-López lost a game against Diep in WCCC'99 partly because of not doing this), and castling (I don't think castling matters in practice).

Also, you may want to use "0x0000000000000001" as the number for whose turn it is: It improves cache usage when you use null-move pruning, since both entries are in the same cache line.

Actually, the engine I'm creating is not traditional chess, but Genesis Chess. There is no en-passant or castling. So I should only need the 769.

You mean 768, and what about castling?? That should add another 4 or 8.

768 would be all (piece-type * square) combinations and the last 1 is side to move. Side to move is needed right?
And as I bolded in the quote above, there is no castling in my chess variant.

Normally, 768 for the pieces, but you can shave 32 off of that since pawns can't sit on the 1st or 8th ranks. You don't need one for side to move, just complement the key if it is black to move and you are set.

Don't forget one for en passant, if you have that.

so 768 - 32 (736) + 1 for ep and you can get by with 737 since there is no castling. You can just put 0's in the 1st and 8th rank pawn values.

[bob]

One minor correction.

768 = 12 x 64. But you can save 32 since pawns can't sit on 1st/8th ranks. So 768 - 32 = 736. Add 4 for the 4 possible castle options, + 1 for enpassant, and you get 741 which is, I think, the minimum.

[hgm]

And as I bolded in the quote above, there is no castling in my chess variant.

Don't worry about Bob. He never reads what you write, so repeating it a few more times will not help either...

And when there would be e.p. capture, like in orthodox Chess, one would need 8 keys (one for each file) to indicate it, not one, of course.