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?