Implement a Hex Monte Carlo player

hw5.cc

// I use g++ (Ubuntu) 4.6.3 (with  --std=gnu++0x and -O3  optimisation):
// g++ --std=gnu++0x -O3 hw5.cc -o play 

/* *******************************************************************
move (<LETTER><letter>): Bk
Think (not deeply, but we see...)
                     o
   a   b   c   d   e   f   g   h   i   j   k
 A  .   .   .   .   .   .   .   .   .   x   o  A
   B  .   .   .   .   .   .   o   x   x   o   o  B
     C  .   .   .   .   .   .   o   o   x   x   x  C
       D  .   .   .   .   .   o   .   x   o   .   .  D
         E  .   .   .   o   .   .   o   x   .   .   .  E
       x   F  .   o   x   x   o   .   o   x   .   .   .  F   x
             G  o   x   o   x   x   x   x   o   .   .   .  G
               H  x   .   .   .   .   .   .   .   .   .   .  H
                 I  .   .   .   .   .   .   .   .   .   .   .  I
                   J  .   .   .   .   .   .   .   .   .   .   .  J
                     K  .   .   .   .   .   .   .   .   .   .   .  K
                         a   b   c   d   e   f   g   h   i   j   k
                                               o

Computer (x) win!
********************************************************************/

/*      "graf.h"        */

#include <fstream>
#include <vector>
#include <string>
#include <bitset>

using namespace std;

class HexBoard { // giving up :public Graf (wich we have in HW4)
public:
    HexBoard(int dim=11): _dim(dim) { 
        _init_board(); 
        _init_adjacency(); 
    }
    int get_dim() { return _dim; }
    void set_cell(int, int, int); // will register 'x'|'o'|' ' into _board[] string
    void display();
protected:
    int _dim;
    vector<vector<int> > _adj_list; // the (2,3,4 or 6) adjacents for every cell (vertex)
private:
    string _head; // will be "   a   b   c   d   e   f   g   h   i   j   k" (on 11x11 board)
    vector<string> _board;

    void _init_board(); // register the initial string-diagram (_head, _board)
    void _init_adjacency(); // precalculate the adjacency lists of the cells
};


typedef bitset<128> Occupy; // 11*11 = 121

class HexGame: public HexBoard {
public:
    HexGame(int dim): HexBoard(dim), _end(false) { _init_borders(); }
    
    bool is_taken(int, int);
    void make_move(int, int); // really (affecting _player[], _tomove and _board[])
    
    bool get_end() { return _end; }
    void set_end() { _end = true; }
    int get_turn() { return _tomove; }
    
    bool succeed(int); // return true if there is a winner
    void gen_moves(vector<int>&); // obtains the list of all free cells

    void your_move(); // get the move (<LETTER><letter>) from "Human"
    bool my_win(const Occupy&); // Computer is the winner, in the given position?
    void my_move(); // Monte Carlo search a move in the current position
    
protected:
    void make_move(int); // without affecting _tomove and _board[]
    void undo_move(int);
    int _BFS(const Occupy &, int); // Best-First-Search from a cell (used in succeed() and my_win())

    Occupy _player[2]; // current positions for the players
    Occupy _border[4]; // bit masks for the "borders" (first line, right line, etc.)
    int _tomove; // 0 ('x') / 1 ('o')
private:
    bool _end;
    void _init_borders();
};


/******************************************************************************/

/*      "graf.cc"       */
// #include "graf.h"

#include <queue>
#include <iostream>
#include <sstream>
#include <random>
#include <algorithm>

static std::random_device rd;
static unsigned long seed = rd();
static std::mt19937 Mersenne(seed);

template <typename T> 
inline string _to_str (T a) { // convert <char> or <int> to string
    string str; ostringstream temp;
    temp << a;
    return temp.str();
}

void HexBoard::_init_board() { // <LETTER><letter> (instead of A0..A10, or A17...)
    string h;
    for(int i=0; i < _dim-1; i++)
        h += (_to_str<char>('a' + i) + "   ");
    h += (_to_str<char>('a' + _dim-1) + '\n');
    _head = h;
    for(int i=0; i < _dim; i++) {
        string ist = _to_str<char>('A' + i) + "  ";
        string row = ".   ";
        for(int j=0; j < _dim-1; j++)
            ist += row;
        ist += (".  " + _to_str<char>('A' + i) + "\n");
        _board.push_back(ist);
    }
}

void HexBoard::_init_adjacency() { // precalculate the adjacency lists
    int n = _dim*_dim, xu, yu, xv, yv;
    _adj_list.resize(n, vector<int>());
    for(int u=0; u < n; u++)
        for(int v=u+1; v < n; v++) { // only at right
            xu = u % _dim; yu = u / _dim;
            xv = v % _dim; yv = v / _dim;
            if(((xu == xv) && ((yu-yv == 1) || (yv-yu == 1))) ||
               ((yu == yv) && ((xu-xv == 1) || (xv-xu == 1))) ||
               ((xv-xu == 1) && (yv-yu == -1)) || ((xv-xu == -1) && (yv-yu == 1))) {
                _adj_list[u].push_back(v);
                _adj_list[v].push_back(u); // using symmetry
            }
        }
}

void HexBoard::set_cell(int row, int col, int X_O) { // registering 'x', 'o' or eventually, deleting
    _board[row][3+4*col] = (X_O == 0? 'x': (X_O == 1? 'o':' '));
}

void HexBoard::display() {
    string vxo(2*_dim-1, ' ');
    cout << vxo + "o\n";
    cout << ("   " + _head);
    string left = " ";
    for(int i=0; i < _dim; i++) {
        if(i == _dim/2)
            cout << (left.substr(0, left.size()-4) + "x   " + _board[i].substr(0, _board[i].size()-1) + "   x\n");
        else
            cout << (left + _board[i]);
        left += "  ";
    }
    cout << (left + "  " + _head);
    cout << (left + vxo + "   o\n");
}



void HexGame::_init_borders() { // initialize the "border" bitmaps 
    for(int i=0; i < _dim; ++i) {
        _border[0].set(i*_dim);          // left border
        _border[2].set((i+1)*_dim-1);    // right border
        _border[1].set(i);              // top border
        _border[3].set((_dim-1)*_dim+i); // bottom border
    }
    _tomove = 0; // 'x' is the first to move
}

bool HexGame::is_taken(int row, int col) {
    int bit = _dim*row + col; // test if the cell is occupied
    return _player[0].test(bit) || _player[1].test(bit);
}

void HexGame::make_move(int row, int col) {
    int cell = _dim*row + col;
    _player[_tomove].set(cell); // set the corresponding bit of the occupied field
    set_cell(row, col, _tomove);
    if(succeed(cell))
        set_end();  // player (human/computer) win the game
    else _tomove = 1 - _tomove; // the other player is to move
}

void HexGame::make_move(int cell) { // don't set_cell() and don't change _tomove
    _player[_tomove].set(cell); // only set the bit for the occupied field
    if(succeed(cell))
        set_end();
}
void HexGame::undo_move(int cell) {
    _player[_tomove].reset(cell);
}

int HexGame::_BFS(const Occupy& pos, int cell) {
    Occupy seen; // 'seen' will contain the connected component which include 'last'
    queue<int> Q; // when 'seen' intersect the borders then the corresponding player wins
    Q.push(cell);
    seen.set(cell);
    while(! Q.empty()) { // best first search mechanism
        int t = Q.front();
        Q.pop();
        for(int i=0, n = _adj_list[t].size(); i < n; ++i) {
            int k = _adj_list[t][i];
            if(pos.test(k) && !seen.test(k)) {
                seen.set(k);
                Q.push(k);
            }
        }
    }
    if(((_border[0] & seen).any()) && ((_border[2] & seen).any())) return 0; 
    if(((_border[1] & seen).any()) && ((_border[3] & seen).any())) return 1;
    return -1; // no winner (we have unoccupied cells)
}

bool HexGame::succeed(int last) {
    return _BFS(_player[_tomove], last) == _tomove;
}

void HexGame::gen_moves(vector<int>& moves) {
    Occupy occ = _player[0] | _player[1];
    for(int i=0, n = _dim*_dim; i < n; ++i)
        if(! occ.test(i))
            moves.push_back(i);
}

void HexGame::your_move() {
    string move;
    char row, col;
    do {
        cout << "move (<LETTER><letter>): "; // "Ak" instead of "A10"
        cin >> move;
        row = move.at(0), col = move.at(1);
    } while((row < 'A') || (row > 'A'+_dim-1) || 
            (col < 'a') || (col > 'a'+_dim-1) || 
            is_taken(row-'A', col-'a'));
    make_move(row-'A', col-'a');  
}

bool HexGame::my_win(const Occupy& pos) {
    int scal = _tomove? _dim : 1; // "North-South", "East-West" respectively
    for(int j=0; j < _dim; ++j) {
        int last = scal*j;
        if(pos.test(last) && (_BFS(pos, last) == _tomove)) return true;
    }
    return false;
}

const int MC_SIM = 1000; // 10; the number of Monte Carlo simulations

void HexGame::my_move() {
    vector<int> moves;
    gen_moves(moves); // the possible legal moves
    int best = 0; // the "best" response in the current position
    int resp = moves[0]; // if 'best' will be 0 (!!), however will make  a move (it know that is lost) 
    int rest = moves.size() - 1; // How many moves remain after the first next move
    Occupy my;
    for(int curr=0; curr <= rest; ++curr) {
        int move = moves[curr];
        make_move(move);  // and finally undo_move()
        if(get_end()) {
            undo_move(move); // conclude if it is a winning move
            resp = move;
            break;
        }
        vector<int> cand;
        gen_moves(cand); // get all opponent's moves (simple than removing from moves[] and finally restoring)
        int n_wins = 0; // counts the number of "Computer"-winning positions
        for(int t=0; t < MC_SIM; ++t) {
            shuffle(cand.begin(), cand.end(), Mersenne); // Thanks <random>!
            my = _player[_tomove]; // _tomove remained set to "Computer"!
            for(int i=0; i < rest; i+=2) // "Computer" make half of the available moves
                my.set(cand[i]);
            if(my_win(my))
                n_wins++;
        }
        if((n_wins > best) && (n_wins != MC_SIM)) { // double score = static_cast<double>(n_wins)/MC_SIM;
            best = n_wins; // update 'best', 'resp'
            resp = move;
        }
        undo_move(move); // reconstruct the initial position, for to probe another possible move 
    }
    // cout << best << '\t'<<resp<<'\n'; // best==0 ==> 'Computer' forfeit (!)
    if(best==0) cout << "I know that You win!\n";
    make_move(resp / _dim, resp % _dim); // respond the "best" resulting move from the above simulations
}

/******************************************************************************/

    /* "graf_test.cc" */
//#include "graf.cc"

int main(int argc, char** argv) {
    int dim = 11;
    cout << "Hex dimension (4..11): "; cin >> dim;
    if((dim > 11) || (dim < 4)) dim = 11; // I opted for 128 bits (11*11 = 121)
    HexGame H(dim);

    cout << '\n';
    H.display();
    cout << "player 'x' moves First to connect Left and Right\n";
    cout << "'o' follow to move and tries to connect Top-Bottom\n";
    cout << "Two cells are connected if are neighboring horizontally or diagonally\n\n";
    int you = 0; 
    cout << "by default You are First to move ('x');\nif you want to change this press 'y': "; 
    char resp; cin.get();
    if((resp=cin.get()) == 'y') you = 1;
    cout << '\n';
    int to_move;
    do {
           to_move = H.get_turn();
           if(to_move == you) {
               H.display(); // show diagram only when "Human" is to move
               H.your_move();
           } else {
               cout << "Think (not deeply, but we see...)\n";
               H.my_move();
           }
    } while(H.get_end() == false);
    H.display();
    char xo = to_move? 'o':'x';
    cout << (to_move == you? "\nYou (":"\nComputer (") << xo << ") win!\n\n";
}