14 replies to this topic

[mind in a box]

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

[Álvaro]

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

[mind in a box]

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.

[Álvaro]

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.

[mind in a box]

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?

[Álvaro]

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.

[mind in a box]

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)

[Álvaro]

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.

[mind in a box]

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?

[Álvaro]

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

What are all the things that a cell might contain?

[mind in a box]

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.

[Álvaro]

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.

[mind in a box]

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

[Álvaro]

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.

[mind in a box]

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