Skip to content

Instantly share code, notes, and snippets.

@vladbazon
Created Dec 4, 2013
Embed
What would you like to do?
Implement a Hex Monte Carlo player
// 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";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment