Sign in to follow this  
mind in a box

Too many Zobrist-Numbers

Recommended Posts

Hi GDNet!

I was writing some Alpha-Beta-Search for a game and came to the point where I thought a transposition-table could be helpful.
The problem is not that I don't know how those are working, but more that the table of random numbers I need to generate the hash-values will get too big!

When I got it right I would have to initialize this array with random numbers to save my whole "battlefield":
[CODE]__int64 ZobristNumbers [2] // [Turncolor (Player/Enemy)]
[20*5] // [Location]
[20] // [NumPlayerPoints (Max 20)]
[20] // [NumEnemyPoints (Max 20)]
[2] // [PlaceOwner]
[4][5] // [PlayerCards]
[4][5]; // [EnemyCards][/CODE]

So:
2*20*5*20*20*2*4*5*4*5 = 64000000
64000000 * 64bit = 4096000000 bytes = 4000000kbyte = 3906,25mbyte

And almost 4GB of memory are just too much. Is there any help for me or should I just drop the transposition-tables?

Regards,
Mind in a box

Share this post


Link to post
Share on other sites
You need to compute a hash key of a position in your game. For some games, a Zobrist key is a very convenient way to go about it, but perhaps this isn't the case for your game.

Can you describe what a position in your game looks like?

EDIT: Also, your Math seems wrong: 2*20*5*20*20*2*4*5*4*5 entries * 8 bytes/entry ~= 488 MB

Share this post


Link to post
Share on other sites
Basically I have a field of 4*5 positions to set on. The players can put their marks on those, and the player who got more marks than the other owns the field.
Also every player has 4 cards, describing on which of the 5 fields they can set.

Share this post


Link to post
Share on other sites
You can compute a hash key for the board in the usual way, XORing together numbers from a table of size [2][4*5*5] or something like that. Then you can compute a hash key of the cards, and the details depend on things like whether you may have more than one card of one type or if they are distinct. Then you can combine both hashes by XORing them together.

Share this post


Link to post
Share on other sites
I didn't know you could have more than one mark in each position. If you give me a complete description of the game, I'll give you a correct method for computing a hash key, but I can't guess.

Yes, you can just XOR the hash of the cards and the hash of the field, as I said earlier.

Share this post


Link to post
Share on other sites
That would be very nice, indeed.

Every player has 6 blocks in their hands (That are the "marks" I was talking of). They can have a height of 1 to 4.
Now they put those blocks into the field, trying to get more than the enemy and to become the owner of the field.
When you place a block you have to look at your cards if you have the right one for the place you want to build on. They can show the rows 1 to 5.
When you place on that field you have to throw the card away, so I'd have to keep track of the cardstack too, but let's just put that aside.

After all 6 blocks were placed the players can choose 6 new ones from their library, until it is empty. (Contains 24 blocks)

Share this post


Link to post
Share on other sites
You definitely need to encode the contents of the deck and of the library of blocks for each player. What is the importance of the heights?

So how many fields do you have, how many cells does each field have and what can a cell contain?

An example of position would be very helpful to understanding your description.

Share this post


Link to post
Share on other sites
The game is divided in 4 parts, so the library doesn't matter, since you choose those blocks at the beginning of the parts.
As for the height: You can not build onto a block when you don't get the building afterwards.

The field is 4*5. 4 lines with 5 rows. Each cell contains one building.

But I'm starting to understand... I can generate random numbers for the cards and random numbers for the buildings and probably random numbers for the locations and just XOR them all together afterwards?

Share this post


Link to post
Share on other sites
A block is that what you can set. A building is the whole thing. If you put more blocks onto the building, it will grow.

I'm not sure what you mean by "cell". I guess it's one place of the field where you can set on?

Edit:
So, what I actually need to store is:
Buildings: Number of Enemy-Blocks on the Building + Number of Player-Blocks on the Building + Buildings
Cards: 4 Cards with 5 possible values for each player + Graveyard + Deck

And I got 1.5gb of RAM to use.

Share this post


Link to post
Share on other sites
Sorry, but I still don't get what a cell may contain.

If you don't like the word "cell", you can pick a different one. I don't understand "set on" (the dictionary says "attack someone physically or emotionally").

If you would just post an example of the description of a typical position in the game, I think everything would be clear.

Share this post


Link to post
Share on other sites
OK, I think I got it.

Have a table zobrist_key_buildings[2][20][MAX_BLOCKS_PER_BUILDING+1]. I think from your description MAX_BLOCKS_PER_BUILDING is 24, or something like that. even if it is 100, this table is not too large.

Have a table zobrist_key_cards[2][5][5].

Have a table zobrist_pieces_on_hand[2][4][7].

When you place blocks in a building, do
[code]zobrist_key ^= zobrist_key_buildings[player][cell][number_of_blocks[player][cell]];
number_of_blocks[player][cell] += piece_height;
zobrist_key ^= zobrist_key_buildings[player][cell][number_of_blocks[player][cell]];[/code]

When you get a card, do
[code]zobrist_key ^= zobrist_key_cards[player][card_type][number_of_cards[player][card_type]];
number_of_cards[player][card_type]++;
zobrist_key ^= zobrist_key_cards[player][card_type][number_of_cards[player][card_type]];[/code]

When you lose a card, do
[code]zobrist_key ^= zobrist_key_cards[player][card_type][number_of_cards[player][card_type]];
number_of_cards[player][card_type]--;
zobrist_key ^= zobrist_key_cards[player][card_type][number_of_cards[player][card_type]];[/code]

When you get a block, do
[code]zobrist_key ^= zobrist_pieces_on_hand[player][piece_height-1][number_of_pieces_on_hand_by_height[piece_height-1]];
number_of_pieces_on_hand_by_height[piece_height-1]++;
zobrist_key ^= zobrist_pieces_on_hand[player][piece_height-1][number_of_pieces_on_hand_by_height[piece_height-1]];[/code]

When a block leaves your hand, do
[code]zobrist_key ^= zobrist_pieces_on_hand[player][piece_height-1][number_of_pieces_on_hand_by_height[piece_height-1]];
number_of_pieces_on_hand_by_height[piece_height-1]--;
zobrist_key ^= zobrist_pieces_on_hand[player][piece_height-1][number_of_pieces_on_hand_by_height[piece_height-1]];[/code]

I am not dealing with the graveyard or the deck, so try to figure those out yourself. If you need help, post again and please describe what the graveyard and the deck might contain, together with an example.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this