Memory usage in Reversi board state 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) &amp;&amp; IsValidCoordinate(y))) {
                throw new IndexOutOfRangeException();
            }
            int position = GetPosition(x, y);
            bool majorBit = State[position];
            bool minorBit = State[position + 1];
            if (majorBit &amp;&amp; !minorBit) {
                return SlotState.Black;
            } else if (!majorBit &amp;&amp; minorBit) {
                return SlotState.White;
            } else {
                return SlotState.Empty;
            }
        }
        set {
            if (!(IsValidCoordinate(x) &amp;&amp; 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 &gt;= 0 &amp;&amp; coordinate &lt;= 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) &amp;&amp; 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).
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.