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).