A typical starting point for a TT entry might be
4 bytes zobrist hash key portion unused by the index (upper bits if using simple and-mask and power-of-2 entry hash table, lower bits if using multiplication to obtain the index(table size can be anything you please))
2 bytes move
2 bytes score
1 byte depth
1 byte entry type
1 byte age
you might try to pad that out to 16 bytes so that 4 entries make a cache line (could store more of your hash key, or just add some unused bytes to your TT entry) but that's not really an important worry for first implementation. Some engines try to squish that down to get more entries by removing some of the hash key bits, using smaller move formats and squishing in fields like age and entry type into the unused bits of the move format, but again not important for a starting point.
Starting with Hash Tables.
Moderators: hgm, Rebel, chrisw
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with Hash Tables.
Thanks Kevin!kbhearn wrote:A typical starting point for a TT entry might be
4 bytes zobrist hash key portion unused by the index (upper bits if using simple and-mask and power-of-2 entry hash table, lower bits if using multiplication to obtain the index(table size can be anything you please))
2 bytes move
2 bytes score
1 byte depth
1 byte entry type
1 byte age
you might try to pad that out to 16 bytes so that 4 entries make a cache line (could store more of your hash key, or just add some unused bytes to your TT entry) but that's not really an important worry for first implementation. Some engines try to squish that down to get more entries by removing some of the hash key bits, using smaller move formats and squishing in fields like age and entry type into the unused bits of the move format, but again not important for a starting point.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with Hash Tables.
Sorry if is a too stupid question:
At this moment I think in make my TT as an array like:
Dim TT(key, piece, move, score, typescore, turn, remainingdepth, age)
Where:
key have 4 bytes
score have 2 bytes and all others 1 byte.
I use many other arrays in my code too.
If the rule for example for CCRL test is that you could have a 256MB hash tables.
All my code will could not use more than 256MB of RAM in any moment?
There is no way the ruler knows wich array I´m using!
At this moment I think in make my TT as an array like:
Dim TT(key, piece, move, score, typescore, turn, remainingdepth, age)
Where:
key have 4 bytes
score have 2 bytes and all others 1 byte.
I use many other arrays in my code too.
If the rule for example for CCRL test is that you could have a 256MB hash tables.
All my code will could not use more than 256MB of RAM in any moment?
There is no way the ruler knows wich array I´m using!
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with Hash Tables.
I made a fast test and actually the engine never use more than 50MB.
I must have this as a margin? I mean, if the rule is max 256MB I must take care to not overtake for example 200MB using the TT?
EDIT: I think I measured the memory used wrongly.
It could be know from here?:
https://dl.dropboxusercontent.com/s/aow ... a.jpg?dl=0
(Is a screen capture while two Soberango´s versions are playing in 40/30 time control mode.)
That means around 6MB?
I must have this as a margin? I mean, if the rule is max 256MB I must take care to not overtake for example 200MB using the TT?
EDIT: I think I measured the memory used wrongly.
It could be know from here?:
https://dl.dropboxusercontent.com/s/aow ... a.jpg?dl=0
(Is a screen capture while two Soberango´s versions are playing in 40/30 time control mode.)
That means around 6MB?
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Starting with Hash Tables.
I think the rule is that you can't allocate more than 256MB to the hash table. I'm reasonably sure they'll be okay with the 6MB or so your executable uses for other things.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with Hash Tables.
How to know wht is a hash table and what is other think?ZirconiumX wrote:I think the rule is that you can't allocate more than 256MB to the hash table. I'm reasonably sure they'll be okay with the 6MB or so your executable uses for other things.
May be there is some lack of programming knowledge in me.
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Starting with Hash Tables.
Your transposition table is your hash table. I don't know what your other things are, because you program is closed source, but it usually involves tables and things like that.Luis Babboni wrote:How to know wht is a hash table and what is other think?ZirconiumX wrote:I think the rule is that you can't allocate more than 256MB to the hash table. I'm reasonably sure they'll be okay with the 6MB or so your executable uses for other things.
May be there is some lack of programming knowledge in me.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Starting with Hash Tables.
This would not be "the TT" but only the structure of one entry of that table, so I suggest that you do not call it "TT" but "TTEntry" or similar. The whole TT would itself be an array of many "TTEntry" items (e.g. 256 MB / 12 byte = about 22 million entries - you might also want to arrange the size of an entry to be 16 bytes so that both the total TT size and the number of TT entries are a power of 2).Luis Babboni wrote:Sorry if is a too stupid question:
At this moment I think in make my TT as an array like:
Dim TT(key, piece, move, score, typescore, turn, remainingdepth, age)
Where:
key have 4 bytes
score have 2 bytes and all others 1 byte.
I would also like to know
a) how you would use "piece" and "turn" in this context, and
b) how you would manage to represent a move in 1 byte?
I suggest to consider using user-defined data types (keyword TYPE in FreeBasic) where appropriate, instead of arrays. In fact it would be appropriate for many concepts in a chess engine like TTEntry, Move, Board, and some others. It would improve the program's readability and would simplify changing the code as well as debugging it.Luis Babboni wrote:I use many other arrays in my code too.
-
- Posts: 2487
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Starting with Hash Tables.
The usage goes up with higher thinking time. With the fast time controls of the CCRL, it is no wonder that the table usage stays low.Luis Babboni wrote:I made a fast test and actually the engine never use more than 50MB.
-
- Posts: 464
- Joined: Sat Feb 28, 2015 4:37 pm
- Location: Argentina
Re: Starting with Hash Tables.
I think was not those 50MB.Ras wrote:The usage goes up with higher thinking time. With the fast time controls of the CCRL, it is no wonder that the table usage stays low.Luis Babboni wrote:I made a fast test and actually the engine never use more than 50MB.
I tried in 40/30 (usually I´m use just 40/3) and in the resources monitor I saw this (and not vary so much along a game):
https://dl.dropboxusercontent.com/s/aow ... a.jpg?dl=0
Could I see there how many memorie I´m using?