CODEWITHSUNDEEP
javaalgorithmtreeminimax
zallexy
zallexy

Reputation: 131

Representation of a state in Ataxx game

I have already asked a question about the subject in here:
https://stackoverflow.com/questions/19916951/generating-a-tree-form-array-for-ataxx-game-in-java

But let me go step by step:

What is the best way (or the best data structure) to represent a state of the Ataxx game (with 7x7 grid board)?

* The state is represented by a node of the game tree but what's in the node? A value? A string? Another data structure?

Upvotes: 0

Views: 404

Answers (2)

Zong
Zong

Reputation: 6230

I would employ a very effective representation taken from chess and checkers: bitboards. The concept is to represent pieces with bits, and so the set of pieces of a player can be represented with a field of bits. We need at least 49 bits, so a 64-bit integer would work nicely.

This is an extremely memory and computational efficient representation, and it is also more expressive than other representations. You can easily work with both single pieces as well entire sets at once with bitwise operations. With array based representations such as the byte[][] suggested, you have to loop way too much for operations that can be represented by a single operator with bitboards (&, |, ^, <<, >>>, etc).

The set bits give the player's pieces. For example, this might be bitboard for one player. You will need another bitboard for the other player. 

0000000000000000000000000000000010000000001000000

In decimal, this would be long bitboard = 65600;. If we insert some new lines, it looks like this: 

0000000
0000000
0000000
0000000
0000100
0000000
1000000

To work with this efficiently, we can precompute some tables. Thus for the piece in the center on the 32nd bit/square, we might have a surrounding table that when used as surrounding[square] gives:

0000000
0000000
0000000
0001110
0001010
0001110
0000000

We can then find the intersection of this with the opponent's bitboard with the bitwise & operator, or takes its union with |, or difference with ^, etc. You can shift the entire the bitboards one row up with << 7, or do any number of complex operations easily. It's has lot of expressive power, and most of these operations only take a single clock cycle, so it is also incredibly efficient.

Upvotes: 2

Bernhard Barker
Bernhard Barker

Reputation: 55609

The entire board can be represented by a 2D array of some integral type (i.e. byte[][]), or perhaps an enum[][]. Then 0 can, for example, represent an empty cell, 1 can represent a cell with player 1's piece and 2 can represent a cell with player 2's piece.

A node in the game tree would typically be the entire board (so the byte[][] or enum[][]).

If you're looking for a more compact representation of a board, you can also represent a board using base-3 or base-4 (2 bits, easier to work with) notation, but that's a bit complex (you can probably stick to the 2D array until you start having memory / running time issues - as long as you abstract it into a class, the conversion should be fairly simple, and easy to test).

Upvotes: 2

Related Questions