7
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you measured the memory usage of your solution? There are many good profilers out there, free and commercial. \$\endgroup\$ – Jesse C. Slicer Sep 10 '14 at 19:22
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Very nice. On x86, this reduces a board's memory footprint from 64 to 24 bytes. On x64, it reduces from 104 bytes to 32 bytes. \$\endgroup\$ – mjolka Sep 11 '14 at 0:48
  • \$\begingroup\$ This looks very good indeed, it completely removes the need for managed types. \$\endgroup\$ – Mephy Sep 11 '14 at 1:15
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't actually know how much space the BitArray uses, but since bool? is a managed type, it probably uses 5 bytes (4 for reference, 1 for a bool), doesn't it? \$\endgroup\$ – Mephy Sep 10 '14 at 18:13
  • \$\begingroup\$ After a less quick research than I thought, it seems that bool? is just a shorthand for Nullable<Boolean>. Which means we are inducing the standard overhead for objects.. This means your code is actually more memory efficient, than replacing the byte with a Nullable<Boolean> \$\endgroup\$ – Vogel612 Sep 10 '14 at 19:13
  • \$\begingroup\$ No, Nullable<bool> is still a struct, so there's no overhead for objects. And there's no 'Boolean', just 'bool'. \$\endgroup\$ – Dennis_E Sep 11 '14 at 10:16
  • \$\begingroup\$ @Dennis_E this is not c++... In c# there is the type System.Boolean,See MSDN: "The bool keyword is an alias of System.Boolean.". But yes, Nullable is a struct which makes it a value-type, I overread that ;) \$\endgroup\$ – Vogel612 Sep 11 '14 at 10:20
  • \$\begingroup\$ @Vogel612 Of course, you're right about System.Boolean. Ignore that part of what I said :) \$\endgroup\$ – Dennis_E Sep 11 '14 at 10:53
2
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.