2
\$\begingroup\$

This is my first time trying solve a game using these techniques.

I've looked at pseudocode of alpha-beta pruning with transposition tables and rewritten it in c++.

I'm also using bitboards inspired by Connect4.java as explained in John's Connect Four Playground.

I'm not solving Connect4, but instead a 5 by 5 variation of tic-tac-toe where the winner is the player that gathers most 3-in-a-row's (vertical, horizontal or diagonal) before the entire board is full.

I have managed to solve this game with this code (I believe there should not be any bugs in my code), but now I'm wondering if this could've been faster.

Can either the bitboard Board class or the alpha-beta Solver class be more optimized? Either to be faster or to use less memory, or both?


Here is the main code containing those two classes: (Size of transposition tables is set to around 1 GB, so you might want or need to reduce that to a lower value if you are running the code. Also notice that there is an option for a 4 by 4 version, which was used for testing before moving onto the 5 by 5 version.)

#include <iostream>
#include <cctype>
#include <algorithm>

#include "TranspositionTable.hpp"

// https://stackoverflow.com/a/109025
int numberOfSetBits(uint32_t i)
{
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

// Inspired by https://tromp.github.io/c4/Connect4.java (https://tromp.github.io/c4/c4.html)
#define N 5
class Board
{
    private:
        unsigned int moves[25] = {0};

    public:
        uint32_t color[2];
        static const unsigned int ROW = 3;
        static const unsigned int ROW1 = ROW-1;
        #if N == 5
            static const unsigned int WIDTH = 5;
            static const unsigned int HEIGHT = 5;
            static constexpr unsigned int bitid[5][5] = 
            {
                {0,   1,  2,  3,  4},
                {5,   6,  7,  8,  9},
                {10, 11, 12, 13, 14},
                {15, 16, 17, 18, 19},
                {20, 21, 22, 23, 24}
            };
            static constexpr unsigned int directions[3][4] = {
                {1, 4, 5, 6},
                {2, 8, 10, 12},
                {7576807, 29596, 32767, 7399}
            };
        #elif N == 4
            static const unsigned int WIDTH = 4;
            static const unsigned int HEIGHT = 4;
            static constexpr unsigned int bitid[4][4] = 
            {
                { 0,  1,  2,  3},
                { 4,  5,  6,  7},
                { 8,  9, 10, 11},
                {12, 13, 14, 15}
            };
            static constexpr unsigned int directions[3][4] = {
                {1, 3, 4, 5},
                {2, 6, 8, 10},
                {13107, 204, 255, 51}
            };
        #endif
        static const unsigned int HEIGHT1 = HEIGHT-1;
        static const unsigned int WIDTH1 = WIDTH-1;
        unsigned int move;
        val_t ptsX;
        val_t ptsO;

        Board()
        {
            reset();
        }

        void reset()
        {
            color[0] = 0;
            color[1] = 0;
            move = 0;
            ptsX = 0;
            ptsO = 0;
        }

        bool isplayable(unsigned int col, unsigned int row) const 
        {
            unsigned int n = bitid[col][row];
            return !((color[0] & (1 << (n))) || (color[1] & (1 << (n))));
        }

        bool isplayable(unsigned int n) const 
        {
            return !((color[0] & (1 << (n))) || (color[1] & (1 << (n))));
        }

        void backmove()
        {
            unsigned int n = moves[--move];
            color[move&1] ^= (1 << (n));
        }

        void makemove(unsigned int col, unsigned int row) 
        {
            unsigned int n = bitid[col][row];
            color[move&1] ^= (1 << (n));
            moves[move++] = n;
        }

        void makemove(unsigned int n) 
        {
            color[move&1] ^= (1 << (n));
            moves[move++] = n;
        }

        void updatePointCount() {
            ptsX = 0;
            ptsO = 0;
            for (int j=0; j<HEIGHT1; j++) {
                uint32_t bitboard0 = color[0];
                uint32_t bitboard1 = color[1];
                for (int i=0; i<ROW1; i++) {
                   bitboard0 &= (color[0] >> directions[i][j]);
                   bitboard1 &= (color[1] >> directions[i][j]);
                } 
                bitboard0 &= (directions[ROW1][j]);
                bitboard1 &= (directions[ROW1][j]);
                ptsX += numberOfSetBits(bitboard0);
                ptsO += numberOfSetBits(bitboard1);
            }
        }

        static val_t getPointCount(uint32_t bitboard) {
            val_t pts0 = 0;
            for (int j=0; j<HEIGHT1; j++) {
                uint32_t bitboard0 = bitboard;
                for (int i=0; i<ROW1; i++) {
                   bitboard0 &= (bitboard >> directions[i][j]);
                } 
                bitboard0 &= (directions[ROW1][j]);
                pts0 += numberOfSetBits(bitboard0);
            }
            return pts0;
        }

        val_t maxPossiblePointCount(bool player_color) {
            return getPointCount(~color[!player_color]);
        }

        key_t key() {
            return (((key_t) color[0]) << 32) | ((key_t)color[1]);
        }

        friend void operator<<(std::ostream& os,  const Board &b) {
            for (int i=0; i<b.WIDTH; i++) {
                os << i << ". ";
                for (int j=0; j<b.HEIGHT; j++) {
                    unsigned int n = b.bitid[i][j];
                    os << ((b.color[0] & (1 << (n))) ? 'X' : ((b.color[1] & (1 << (n))) ? 'O' : '_')) << ' ';
                }
                os << std::endl;
            }
        }
};
// https://stackoverflow.com/a/8016853
#if N == 5
    constexpr unsigned int Board::bitid[5][5];
#elif N == 4
    constexpr unsigned int Board::bitid[4][4];
#endif
constexpr unsigned int Board::directions[3][4];

// Inspired by https://en.wikipedia.org/wiki/Alpha–beta_pruning 
// Inspired by http://people.csail.mit.edu/plaat/mtdf.html#abmem
class Solver {
    private:
        val_t maxPossibleScore;
        unsigned long long nodeCount; 
        #if N == 5
            unsigned int moveOrder[Board::WIDTH*Board::HEIGHT] = {12,6,7,8,11,13,16,17,18,1,2,3,5,10,15,9,14,19,21,22,23,0,4,20,24};
        #elif N == 4
            unsigned int moveOrder[Board::WIDTH*Board::HEIGHT] = {5,6,10,9,1,2,4,7,8,11,13,14,0,3,12,15};
        #endif
        TranspositionTable transTable;

        val_t alphabeta(Board &P, val_t alpha, val_t beta, bool firstPlayer, val_t depth = 0) {
            //std::cout << "a: " << (int)alpha << ", b: " << (int)beta << std::endl;
            assert(alpha < beta);
            nodeCount++;

             // game ended
            if(P.move == Board::WIDTH*Board::HEIGHT) {
                P.updatePointCount();
                return P.ptsX - P.ptsO;
            }

            /* Transposition table lookup */
            val_t n_lowerbound = transTable.getLower(P.key());
            val_t n_upperbound = transTable.getUpper(P.key());
            if (n_lowerbound != 127) {
                if (n_lowerbound >= beta) return n_lowerbound;
                alpha = std::max(alpha, n_lowerbound);
            }
            if (n_upperbound != 127) {
                if (n_upperbound <= alpha) return n_upperbound;
                beta = std::min(beta, n_upperbound);
            }

            val_t value, a, b;
            if (firstPlayer) {
                value = -maxPossibleScore;
                a = alpha;
                for (unsigned int k=0; k<Board::WIDTH*Board::HEIGHT; k++) {
                    unsigned int n = moveOrder[k];
                    if(P.isplayable(n)) {
                        P.makemove(n); 

                        val_t newValue = alphabeta(P, a, beta, false, depth+1);
                        value = std::max(value, newValue);

                        P.backmove();
                        a = std::max(a, value);
                        if (a >= beta)
                            break; // β cutoff 
                    }
                }
                return value;
            } else {
                value = maxPossibleScore;
                b = beta;
                for (unsigned int k=0; k<Board::WIDTH*Board::HEIGHT; k++) {
                    unsigned int n = moveOrder[k];
                    if(P.isplayable(n)) {
                        P.makemove(n); 

                        val_t newValue = alphabeta(P, alpha, b, true, depth+1);
                        value = std::min(value, newValue);

                        P.backmove(); 
                        b = std::min(b, value);
                        if (b <= alpha)
                            break; // α cutoff 
                    }
                }
            }

            /* Traditional transposition table storing of bounds */
            /* Fail low result implies an upper bound */
            if (value <= alpha) {
                transTable.put(P.key(), 127, value);
            }
            /* Found an accurate minimax value - will not occur if called with zero window */
            if (value > alpha && value < beta) {
                transTable.put(P.key(), value, value);
            }
            /* Fail high result implies a lower bound */
            if (value >= beta) {
                transTable.put(P.key(), value, 127);
            }
            return value;
        }

    public:
        int solve(Board &P, bool weak, bool firstPlayer) 
        {
            if(weak) 
                return alphabeta(P, -1, 1, firstPlayer);
            else 
                return alphabeta(P, -maxPossibleScore, maxPossibleScore, firstPlayer);
        }

        int solveEach(Board &P, bool weak, bool firstPlayer) {
            val_t score;
            val_t maxScore = -maxPossibleScore;
            val_t minScore = maxPossibleScore;
            for (unsigned int k=0; k<Board::WIDTH*Board::HEIGHT; k++) {
                unsigned int n = moveOrder[k];
                if(P.isplayable(n)) {
                    P.makemove(n);
                    if(weak) 
                        score = alphabeta(P, -1, 1, !firstPlayer);
                    else 
                        score = alphabeta(P, -maxPossibleScore, maxPossibleScore, !firstPlayer);
                    if (score > maxScore) maxScore = score;
                    if (score < minScore) minScore = score;
                    P.backmove();
                    std::cout << "Move " << n << " yields " << (int)score << "." << std::endl;
                }
            }
            if (firstPlayer)
                return maxScore;
            else
                return minScore;
        }

        unsigned long long getNodeCount() 
        {
            return nodeCount;
        }

        void reset() 
        {
            nodeCount = 0;
            transTable.reset();
        }

        // Constructor
        Solver() : maxPossibleScore{4*(N-2)*(N-1)}, nodeCount{0}, 
                   transTable(67108747) { 
                  // select a prime: 8388593, 16777199, 33554383, 67108747,... to setup maximal memory.
                  // The last prime in above list corresponds to 1 GB of transposition table memory.
                  // (The Board::key() can be optimized to reduce this, but I haven't bothered with that.)
            assert(4*(N-2)*(N-1) < 127);
            reset();
        }
};


// https://stackoverflow.com/a/19555298
#include <chrono>
using namespace std::chrono;
milliseconds getTimeSec() {
  return duration_cast< milliseconds >(
      system_clock::now().time_since_epoch()
  );
}

int main() 
{
    Board board;
    std::cout << board.WIDTH<<"x"<<board.HEIGHT<<" Cumulative-Tic-Tac-Toe" << std::endl;

    Solver solver;
    bool weak = false;
    bool solveIndividually;
    std::cout << "Solve Individually? Type 1 (yes) or 0 (no): ";
    std::cin >> solveIndividually;

    // Test case 5x5
    // cin:  2 2 3 2 1 2 1 1 1 3 1 4 2 3 2 4 0 2 0 3 0 4 3 4 0 1 2 1 3 1 3 3 0 0 4 4 1 0 4 3 2 0 4 2 3 0 4 1 4 0
    // cout: X: 9, O: 7
    // Test case 4x4
    // cin:  0 0 3 3 0 1 3 2 0 2 3 1 0 3 3 0 1 1 2 1 2 0 1 2 1 0 2 2 2 3 1 3
    // cout: X: 4, O: 5
    char c;
    unsigned int col, row;
    unsigned int lastMove = Board::WIDTH*Board::HEIGHT;
    while (true) {
        std::cout << std::endl;
        board.updatePointCount();
        val_t maxX = board.maxPossiblePointCount(0);
        val_t maxO = board.maxPossiblePointCount(1);
        std::cout << "X: " << (int)board.ptsX << " (" << (int)maxX << ")" << ", O: " << (int)board.ptsO << " (" << (int)maxO << ")" << std::endl; 
        std::cout << board;
        if (board.move==lastMove) {
            std::cout 
                << "Board full, player" 
                << ((board.ptsX > board.ptsO) ? " X wins!" : ((board.ptsX < board.ptsO) ? " O wins!" : "s drew!")) 
            << std::endl;
            break;
        }
        std::cout << ">> ";
        std::cin >> c;
        bool moving = std::isdigit(c);
        if (c == 'm' || moving) {
            if (moving)
                col = (unsigned int)c - 48;
            else
                std::cin >> col;
            std::cin >> row;
            if (col<board.WIDTH && row<board.HEIGHT) {
                if (board.isplayable(col, row))
                    board.makemove(col, row);
                else
                    std::cout << "That square is already occupied." << std::endl;
            }
            else {
                std::cout << "That square is out of bounds." << std::endl;
            }
        } else if (c == 'u') {
            if (board.move > 0)
                board.backmove();
            else
               std::cout << "Nothing to undo." << std::endl;  
        } else if (c == 'x') {
            //
            solver.reset();
            milliseconds start_time = getTimeSec();
            val_t score;
            if (solveIndividually)
                score = solver.solveEach(board, weak, board.move%2==0);
            else
                score = solver.solve(board, weak, board.move%2==0);
            milliseconds end_time = getTimeSec();
            std::cout 
                << "Position Score:" << " " << (int)score 
                << ", nodes searched: " << solver.getNodeCount() 
                << ", time: " << (end_time - start_time).count() << "ms" 
            << std::endl;
            //
        } else {
            std::cout << "Command (" << c << ") is invalid. Use ('m' x y) for move or ('u') for undo or ('x') for solving." << std::endl;
        }
    }
    c = ' ';
    while(c==' ') {std::cin >> c;}
    return 0;
}

Here is the transposition table class: (heavily inspired by blog.gamesolver.org)

// Inspired by http://blog.gamesolver.org/solving-connect-four/07-transposition-table/

#ifndef TRANSPOSITION_TABLE_HPP
#define TRANSPOSITION_TABLE_HPP

#include<vector>
#include<cstring>
#include<cassert>

typedef uint64_t key_t;
typedef int8_t val_t;

/**
 * Transposition Table is a simple hash map with fixed storage size.
 * In case of collision we keep the last entry and overide the previous one.
 */
class TranspositionTable {
    private:

        struct Entry {
            key_t key;
            val_t upper;
            val_t lower;
        };

        std::vector<Entry> T;

        unsigned int index(key_t key) const {
            return key%T.size();
        }

    public:

        TranspositionTable(unsigned int size): T(size) {
            assert(size > 0);
        }

        /*
        * Empty the Transition Table.
        */
        void reset() { // fill everything with 0, because 0 value means missing data
            memset(&T[0], 0, T.size()*sizeof(Entry));
        }

        void put(key_t key, val_t low, val_t up) {
            unsigned int i = index(key); // compute the index position
            T[i].key = key;              // and overide any existing value.
            //if (up != 127)
                T[i].upper = up;
            //if (low != 127) 
                T[i].lower = low;       
        }

        val_t getLower(key_t key) const {
            unsigned int i = index(key);  // compute the index position
            if(T[i].key == key) 
                return T[i].lower;          // and return value if key matches
            else 
                return 127;                //  signal missing entry
        }

        val_t getUpper(key_t key) const {
            unsigned int i = index(key);  // compute the index position
            if(T[i].key == key) 
                return T[i].upper;          // and return value if key matches
            else 
                return 127;                //  signal missing entry
        }

};

#endif

Here is an example output of how to use the compiled code: (Where I setup first four moves, then solve each of the following possible moves and print out the score for each, in less than a minute.)

5x5 Cumulative-Tic-Tac-Toe
Solve Individually? Type 1 (yes) or 0 (no): 1

X: 0 (48), O: 0 (48)
0. _ _ _ _ _
1. _ _ _ _ _
2. _ _ _ _ _
3. _ _ _ _ _
4. _ _ _ _ _
>> r
Command (r) is invalid. Use ('m' x y) for move or ('u') for undo or ('x') for solving.

X: 0 (48), O: 0 (48)
0. _ _ _ _ _
1. _ _ _ _ _
2. _ _ _ _ _
3. _ _ _ _ _
4. _ _ _ _ _
>> m 2 2

X: 0 (48), O: 0 (36)
0. _ _ _ _ _
1. _ _ _ _ _
2. _ _ X _ _
3. _ _ _ _ _
4. _ _ _ _ _
>> 3 2

X: 0 (39), O: 0 (36)
0. _ _ _ _ _
1. _ _ _ _ _
2. _ _ X _ _
3. _ _ O _ _
4. _ _ _ _ _
>> 2 3

X: 0 (39), O: 0 (29)
0. _ _ _ _ _
1. _ _ _ _ _
2. _ _ X X _
3. _ _ O _ _
4. _ _ _ _ _
>> 21

X: 0 (32), O: 0 (29)
0. _ _ _ _ _
1. _ _ _ _ _
2. _ O X X _
3. _ _ O _ _
4. _ _ _ _ _
>> x
Move 6 yields 1.
Move 7 yields 1.
Move 8 yields 1.
Move 16 yields 1.
Move 18 yields 1.
Move 1 yields 0.
Move 2 yields 1.
Move 3 yields 0.
Move 5 yields 1.
Move 10 yields 1.
Move 15 yields 1.
Move 9 yields 0.
Move 14 yields 1.
Move 19 yields 0.
Move 21 yields 0.
Move 22 yields 1.
Move 23 yields 1.
Move 0 yields 0.
Move 4 yields 0.
Move 20 yields 0.
Move 24 yields 0.
Position Score: 1, nodes searched: 166118770, time: 49715ms

An optimization that comes to my mind is to optimize the keys used in the transposition class. I have a feeling that their size can be reduced?

Also note that I'm not exploiting the symmetry of positions (boards) in the code (in the implementation of keys), so I'm doing repeated work when an equivalent but rotated position is being calculated. We can call the Solver only on non-symmetric positions, but those can still sometimes lead again into symmetric positions in some branches. Would rotating bitmaps and checking for symmetry be a significant improvement, or is there some other best way to do this?

Can anything else be improved?

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Avoid code duplication

There is a lot of code duplication going on, based on whether N is 4 or 5. It would be even worse if you wanted to support other board sizes as well. There are several ways to reduce it. The most trivial thing is to use N directly in the code, so instead of writing:

#if N == 5
    constexpr unsigned int Board::bitid[5][5];
#elif N == 4
    constexpr unsigned int Board::bitid[4][4];
#endif

You can just write:

constexpr unsigned int Board::bitid[N][N];

4 lines eliminated, and now this line of code supports arbitrary board sizes. Of course, this only goes so far. You can't just simplify the intialization of bitid this way. But you can if you start using std::array and templates. You can make constexpr functions that return std::arrays with the values initialized with anything that can be done in a constexpr function. For example:

template<size_t N>
constexpr auto make_bitid() {
    std::array<std::array<unsigned int, N>, N> bitid;

    for (std::size_t col = 0; col < N; col++)
        for (std::size_t row = 0; row < N; row++)
            arr[col][row] = i * N + j;

    return arr;
}

And then use this inside class Board as follows:

#define N 5
class Board {
    ...
    static constexpr auto bitid = make_bitid<N>();
    ...
};

Perhaps even the arrays directions and moveOrder could be computed at compile time, and then you don't need to use #defines and #ifs anymore, and then you can make Board and Solver templates themselves, with size_t N as the template argument. As a bonus, this would remove a lot of magic constants from the code.

Avoid look-up tables for trivially computable values

It can be faster for a computer to do a simple calculation on values that are already in registers than it is to read something from memory, even if it is in the cache. So don't create look-up tables for things that are trivial to calculate, such as bitid. I would replace it with a simple function:

constexpr unsigned int bitid(unsigned int col, unsigned int row) {
    return col * N + row;
}

Be consistent with the types of integers

I see both uint32_t, unsigned int and int being used, sometimes in the same expressions. Try to be more consistent. First, I strongly suggest you use size_t for all sizes, counts, and indices. Furthermore, anything that should never be negative should be unsigned. If you know exactly how large the range of integers used is,

Use constexpr where possible

Why is bitid constexpr but WIDTH and HEIGHT only const? You should make those constexpr as well. Also note that if you have a separate WIDTH and HEIGHT, and you made them constexpr, then you could have written bitid[WIDTH][HEIGHT].

Make member functions const where possible

You made some member functions const, but you missed a few opportunities, such as getPointCount(), maxPossiblePointCount(), key() and getNodeCount().

Where to define key_t and val_t

It is a bit strange to see key_t and val_t being typedef'ed inside TranspositionTable.hpp, but used to declare variables in both files. Having the very generic names key_t and val_t defined in global scope is quite bad. First, I would declare key_t and val_t inside the main file, and perhaps even create a namespace to put those types, class Board and class Solver in. Then, make TranspositionTable a template that takes the key and value type as template parameters, like so:

template<typename key_t, typename val_t>
class TranspositionTable {
    ...
    // no changes necessary here
    ...
};

And inside Solver just pass it the actual types:

class Solver {
    ...
    TranspositionTable<key_t, val_t> transTable;
    ...
};

Also prefer creating type aliases with using instead of typedef, while the semantics are almost identical, the former has the benefit that it can also be templated.

Use '\n' instead of std::endl

Prefer using '\n' instead of std::endl, the latter is identical to the former, but it also forces the output to be flushed, which is often unnecessary and can have a performance impact.

Use static_assert() instead of assert() where possible

If you want to assert something that can be checked at compile-time, use static_assert(). For example:

static_assert(4 * (N - 2) * (N - 1) < 127, "Board too large for val_t");

Avoid magic numbers

You use 127 a number of times as a special value. However, consider that if you ever want to change the type of val_t (for example, if you want to solve 8x8 or larger boards), that you'd have to find and replace every occurence of 127, and hope there are no other things that use the number 127.

Give magic numbers a name by declaring a static constexpr variable for them. Also, if there is a way to derive that number from something else programmatically, do that. For example, here you can use std::numeric_limit<>::max() to get the maximum value of val_t:

static constexpr MISSING_ENTRY = std::numeric_limit<val_t>::max();

This is also a case where you might want to explore other ways of signalling a missing value, for example by using std::optional when returning the lower and upper bound:

std::optional<std::pair<val_t, val_t>> getBounds(key_t key) const {
    unsigned int i = index(key);
    if (T[i].key == key)
        return std::make_pair<T[i].lower, T[i].upper>;
    else
        return std::nullopt;
}

And then use it like so:

if (auto bounds = transTable.getBounds(P.key())) {
    auto [n_lowerbound, n_upperbound] = *bounds;
    if (n_lowerbound >= beta)
        return n_lowerbound;
    alpha = std::max(alpha, n_lowerbound);
    if (n_upperbound <= alpha)
         return n_upperbound;
    beta = std::min(beta, n_upperbound); 
}

Use std::fill() instead of memset()

There is often no need to use C functions when C++ has perfectly capable, and usually more safe alternatives. For example, if you want to clear an array, then instead of using memset(), you can use std::fill() or std::fill_n(), like so in class Solver:

void reset() {
    std::fill(T.begin(), T.end(), Entry{});
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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