Memory usage in Reversi board state

Question

I'm coding a Reversi game, with an artificial intelligence using the MinMax as the search algorithm. My concern is that (most) search algorithms needs to store a lot of instances of "states", in my case, board states. What I want is to represent a BoardState with 64 SlotState (Empty, White Disk or Black Disk), with the minimum RAM usage as possible. My current implementation uses a System.Collections.BitArray for storage.

public enum SlotState : byte {
    Empty = 0,
    White = 1,
    Black = 2
}
public sealed class BoardState {

    private const int BitsPerSlot = 2;
    private const int SlotsPerRow = 8;
    private const int SlotsInBoard = 64;
    private const int BitsPerRow = SlotsPerRow * BitsPerSlot;
    private const int BitsInBoard = SlotsInBoard * BitsPerSlot;

    // stores state in big-endian row-major
    private BitArray State;

    public BoardState() {
        State = new BitArray(BitsInBoard);
        this[3, 3] = SlotState.White;
        this[4, 4] = SlotState.White;
        this[3, 4] = SlotState.Black;
        this[4, 3] = SlotState.Black;
    }

    public BoardState(BoardState original) {
        State = new BitArray(original.State);
    }


    public SlotState this[int x, int y] {
        get {
            if (!(IsValidCoordinate(x) && IsValidCoordinate(y))) {
                throw new IndexOutOfRangeException();
            }
            int position = GetPosition(x, y);
            bool majorBit = State[position];
            bool minorBit = State[position + 1];
            if (majorBit && !minorBit) {
                return SlotState.Black;
            } else if (!majorBit && minorBit) {
                return SlotState.White;
            } else {
                return SlotState.Empty;
            }
        }
        set {
            if (!(IsValidCoordinate(x) && IsValidCoordinate(y))) {
                throw new IndexOutOfRangeException();
            }
            int position = GetPosition(x, y);
            State[position] = false;
            State[position + 1] = false;
            if (value == SlotState.White) {
                State[position + 1] = true;
            } else if (value == SlotState.Black) {
                State[position] = true;
            }
        }
    }

    private int GetPosition(int x, int y) {
        return BitsPerSlot * x + BitsPerRow * y;
    }

    private bool IsValidCoordinate(int coordinate) {
        return coordinate >= 0 && coordinate <= 7;
    }

}

More specific questions could be: Is there any way to reduce memory usage even further (does BitArray have a memory overhead)? Is it excessive const declarations? Should I break the get/set into smaller pieces of code? Are the naming and general coding style all right?

I also tried this implementation of the get method. I didn't like it, but couldn't find a reason to use either over the other. Is it any better/worse than the other implementation, in terms of ease of understanding?

get {
    if (!(IsValidCoordinate(x) && IsValidCoordinate(y))) {
        throw new IndexOutOfRangeException();
    }
    int position = GetPosition(x, y);
    bool majorBit = State[position];
    bool minorBit = State[position + 1];
    byte value = 0;
    if (majorBit) value += 2;
    if (minorBit) value += 1;
    return (SlotState)value;
}

If you're going to suggest a library or anything like that, keep in mind this is a XNA project (thus the memory concern).

Answer 1

The most concise storage format which would be easy to work with would be a pair of UInt64 values, one of which would indicate which squares were occupied by white pieces, and one of which would indicate which squares were occupied by black pieces. One could find e.g. the set of white squares that also have white squares to their left by white & (white>> 1) & 0x7F7F7F7F7F7F7F7FUL, or the set of black squares that have black squares up and to the right via black & (black >> 7) & 0x00FEFEFEFEFEFEFEUL. While working with bitmasks may be intimidating, it's a very powerful technique since operations can act upon the entire board at once.

Answer 2

I agree with other commenters that you should have your memory usage measured first, so you know for sure you need to solve this. That said, I don't think MinMax requires storing all board states of the tree. Why do you need to have more boards in the memory than the level of the tree search? That should be 10-15 boards in the memory tops, no? I would even think about storing just one board in the memory and passing just the "moves" down the recursion. You will perform the move when you go down the recursion and undo the move when going up.

Answer 3

DISCLAIMER: All advice in this answer is possibly "dangerous" to readability and maintainability of code.

Nitpicks

Your boolean checks sometimes seem superfluous:

if (minorBit && !majorBit)

could be

if (minorBit)

You could simplify like this by making the condition for SlotState.Empty

if (minorBit == majorBit) 
{
    return SlotState.Empty;
}

But! you'd need to make this the first condition (which is effectively obfuscation)

Saving memory

If you want to be hackish (and it seems like you do) you could replace your SlotState by a simpler construct for 3 states, namely bool?. Nullable booleans also have three states:

 null, true, false;

And suddenly the complete state-representation (and querying) of you board becomes "simpler".

Caveat!

If you would use this approach, and I advise strongly against doing so, you must document which boolean state represents which SlotState

Answer 4

Your code looks good, constants are good for understanding and possible future changes. BitArray is memory-optimal (if we don't count the overhead of the very object). Using it is limiting your getter.

The only thing that could improve your code would be to use byte[] directly. That would need few shifts and masking, e.g. return (State)((data[index] >> subIndex) & 3), but that may get less readable for somebody. For 8x8 board, ushort[] may be even better: return (State)((data[row] >> (col << 1)) & 3)