•      Sign In
• Create Account

Awesome job so far everyone! Please give us your feedback on how our article efforts are going. We still need more finished articles for our May contest theme: Remake the Classics

# Too many Zobrist-Numbers

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

14 replies to this topic

### #1mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 10:53 AM

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":
```__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]```

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

Ad:

### #2Álvaro  Members   -  Reputation: 5801

Like
0Likes
Like

Posted 25 April 2012 - 11:02 AM

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

### #3mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 11:12 AM

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.

### #4Álvaro  Members   -  Reputation: 5801

Like
0Likes
Like

Posted 25 April 2012 - 11:17 AM

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.

### #5mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 11:25 AM

Why do I not need the number of marks they have? And do I XOR the hash of the cards to the hash of the field then or do I store both separately?

### #6Álvaro  Members   -  Reputation: 5801

Like
0Likes
Like

Posted 25 April 2012 - 11:30 AM

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.

### #7mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 11:39 AM

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)

### #8Álvaro  Members   -  Reputation: 5801

Like
0Likes
Like

Posted 25 April 2012 - 11:57 AM

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.

### #9mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 12:05 PM

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?

### #10Álvaro  Members   -  Reputation: 5801

Like
0Likes
Like

Posted 25 April 2012 - 12:44 PM

I am not sure what "blocks" and "buildings" are.

What are all the things that a cell might contain?

### #11mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 01:10 PM

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.

### #12Álvaro  Members   -  Reputation: 5801

Like
0Likes
Like

Posted 25 April 2012 - 01:38 PM

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.

### #13mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 01:43 PM

Here's a screenshot. Hope it's clear now

### #14Álvaro  Members   -  Reputation: 5801

Like
1Likes
Like

Posted 25 April 2012 - 01:55 PM

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
```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]];```

When you get a card, do
```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]];```

When you lose a card, do
```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]];```

When you get a block, do
```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]];```

When a block leaves your hand, do
```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]];```

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.

### #15mind in a box  Members   -  Reputation: 358

Like
0Likes
Like

Posted 25 April 2012 - 02:13 PM

Awesome! I'll see if I can get that working. Many thanks for your help!

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS