Jump to content

  • Log In with Google      Sign In   
  • Create Account


#Actualalvaro

Posted 27 September 2012 - 08:09 AM

Last night I wrote an alpha-beta searcher for this game. It's probably pretty fast (in nodes visited per second) because I used a few bit tricks to make things fast. It turns out undoing moves is kind of messy in this game, so I am copying boards, just like your code is.

It's not super friendly to interact with, because moves have to be entered in the strange internal format I devised:
  • Bringing figures out of the bases is encoded as 1, 2, 4, 8, 16 (top to bottom). If you want to bring more than one figure out, just use the sum.
  • Moving is encoded by 32 to go up, 33 to go straight, 34 to do gown.
The code is written to be reasonably portable (assumes 32-bit unsigneds; I think that's all).
#include <iostream>
#include <algorithm>
#include <ctime>
double now() {
  return static_cast<double>(std::clock())/CLOCKS_PER_SEC;
}
typedef unsigned u32;
bool test(u32 x, int bit) {
  return (x >> bit) & 1;
}
unsigned int popcount(unsigned int w) {
  w -= (w >> 1) & 0x55555555u;
  w =  (w & 0x33333333u) + ((w >> 2) & 0x33333333u);
  w =  (w + (w >> 4)) & 0x0f0f0f0fu;
  return (w * 0x01010101u) >> 24;
}
const unsigned int de_Bruijn_table[32] = {
  0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,
  31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
};
unsigned int lowest_bit_set(unsigned int w) {
  w  &= -(int)w;
  return de_Bruijn_table[(w * 0x077cb531) >> 27];
}
const u32 holes = 00022002200u;
struct Board {
  u32 net[2];
  char base[5][2];

  Board() {
	for (int i=0; i<2; ++i) {
	  net[i] = 0;
	  for (int j=0; j<5; ++j)
		base[j][i] = 3;
	}
  }
};
std::ostream &operator<<(std::ostream &os, Board const &b) {
  for (int i=0; i<5; ++i) {
	os << 0+b.base[i][0] << ' ';
	for (int j=0; j<6; ++j) {
	  int bit = i*6+j;
	  os << "->< "[test(b.net[0],bit) + 2*test(b.net[1],bit) + 3*test(holes,bit)] << ' ';
	}
	os << 0+b.base[i][1] << '\n';
  }
  return os;
}
typedef char Move; // 1-31 are out-of-base moves, 32 is advance up, 33 is advance and 34 is advance down
int generate_moves(Board const &b, Move *m, int player) {
  Move *original_m = m;

  if (b.net[player] != 0) {
	*m++ = 32;
	*m++ = 33;
	*m++ = 34;
  }

  char mask_of_non_empty_bases = 0;
  for (unsigned i=0; i<5; ++i)
	mask_of_non_empty_bases |= (b.base[i][player]!=0) << i;
  char move_order[] = {1,2,4,8,16, 3,5,6,9,10,12,17,18,20,24, 7,11,13,14,19,21,22,25,26,28, 15,23,27,29,30, 31};
  for (unsigned i=0; i<31; ++i) {
	char c = move_order[i];
	if ((c & mask_of_non_empty_bases) == c)
	  *m++ = c;
  }

  return m - original_m;
}
u32 target[2] = {04040404040u, 00101010101u};
void make_move(Board &b, Move m, int player) {
  u32 &bnp = b.net[player];

  if (m<32) {
	for (unsigned i=0; i<5; ++i) {
	  if (test(m, i)) {
		b.base[i][player]--;
		bnp |= (077u<<(6*i)) & target[!player];
	  }
	}
  }
  else {
	u32 boarding = bnp & target[player];
	for (; boarding; boarding &= boarding-1) {
	  int row = lowest_bit_set(boarding) / 6;
	  b.base[row][!player] = 0;
	  b.base[row][player]++;
	}
	bnp &= ~target[player];
	bnp = player==0 ? bnp << 1 : bnp >> 1;
  
	if (m==32)
	  bnp = ((bnp & 00000000077u) << 24) + (bnp >> 6);
	else if (m==34)
	  bnp = ((bnp & 00077777777u) << 6) + ((bnp & 07700000000u) >> 24);
  
	bnp &= ~holes;
  }

  b.net[!player] &= ~bnp;
}
int eval(Board const &b) {
  int on_base_diff = 0;
  for (int i=0; i<5; ++i)
	on_base_diff += b.base[i][0] - b.base[i][1];

  int on_net_diff = popcount(b.net[0]) - popcount(b.net[1]);

  int score = 500*on_base_diff + 400*on_net_diff - 32 + std::rand()%64;
  return score;
}
int const cost[35] = {0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1};
int negamax(Board const &board, int alpha, int beta, int depth, int player) {
  if (depth <= 0)
	return player==0 ? eval(board) : -eval(board);

  Move moves[34];
  int n_moves = generate_moves(board, moves, player);
  for (int i=0; i<n_moves; ++i) {
	Board copy = board;
	make_move(copy, moves[i], player);
	int score = -negamax(copy, -beta, -alpha, depth-cost[static_cast<int>(moves[i])], !player);
	if (score > alpha) {
	  alpha = score;
	  if (score > beta)
		break;
	}
  }

  return alpha;
}
Move search_root(Board const &board, int player) {
  double start_time = now();
  Move moves[34];
  int n_moves = generate_moves(board, moves, player);
  if (n_moves == 0)
	return 0;
  int depth, alpha;
  for (depth = 1; depth < 5 || now() < start_time + 1.0; ++depth) {
	alpha = -999999;
	for (int i=0; i<n_moves; ++i) {
	  Board copy = board;
	  make_move(copy, moves[i], player);
	  int score = -negamax(copy, -999999, -alpha, depth-1, !player);
	  if (score > alpha) {
		alpha = score;
		std::rotate(moves, moves + i, moves + i + 1);
		std::cout << depth << ": (" << 0+moves[0] << ") " << alpha << ' ' << now()-start_time << '\n';
	  }
	}
	if (std::abs(alpha)>500000)
	  break;
	std::cout << depth << ". (" << 0+moves[0] << ") " << alpha << ' ' << now()-start_time << '\n';
  }
  return moves[0];
}
int main(int argc, char **argv) {
  int seed = argc == 2 ? atoi(argv[1]) : std::time(0);
  std::cout << "seed = " << seed << '\n';
  std::srand(seed);

  Board board;
  int player = 0;
  while (1) {
	std::cout << board << '\n';
	Move move;
	if (player == 0)
	  move = search_root(board, player);
	else {
	  int i;
	  std::cin >> i;
	  move = i;
	}
	if (move == 0)
	  break;
	make_move(board, move, player);
	player = !player;
  }
}

#1alvaro

Posted 27 September 2012 - 06:30 AM

Last night I wrote an alpha-beta searcher for this game. It's probably pretty fast (in nodes visited per second) because I used a few bit tricks to make things fast. It turns out undoing moves is kind of messy in this game, so I am copying boards, just like your code is.

It's not super friendly to interact with, because moves have to be entered in the strange internal format I devised:
  • Bringing figures out of the bases is encoded as 1, 2, 4, 8, 16 (top to bottom). If you want to bring more than one figure out, just use the sum.
  • Moving is encoded by 32 to go up, 33 to go straight, 34 to do gown.
The code is written to be reasonably portable (assumes 32-bit unsigneds; I think that's all).
#include <iostream>
#include <algorithm>
#include <ctime>
double now() {
  return static_cast<double>(std::clock())/CLOCKS_PER_SEC;
}
typedef unsigned u32;
bool test(u32 x, int bit) {
  return (x >> bit) & 1;
}
unsigned int popcount(unsigned int w) {
  w -= (w >> 1) & 0x55555555u;
  w =  (w & 0x33333333u) + ((w >> 2) & 0x33333333u);
  w =  (w + (w >> 4)) & 0x0f0f0f0fu;
  return (w * 0x01010101u) >> 24;
}
const unsigned int de_Bruijn_table[32] = {
  0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,
  31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
};
unsigned int lowest_bit_set(unsigned int w) {
  w  &= -(int)w;
  return de_Bruijn_table[(w * 0x077cb531) >> 27];
}
const u32 holes = 00022002200u;
struct Board {
  u32 net[2];
  char base[5][2];
 
  Board() {
    for (int i=0; i<2; ++i) {
	  net[i] = 0;
	  for (int j=0; j<5; ++j)
	    base[j][i] = 3;
    }
  }
};
std::ostream &operator<<(std::ostream &os, Board const &b) {
  for (int i=0; i<5; ++i) {
    os << 0+b.base[i][0] << ' ';
    for (int j=0; j<6; ++j) {
	  int bit = i*6+j;
	  os << "->< "[test(b.net[0],bit) + 2*test(b.net[1],bit) + 3*test(holes,bit)] << ' ';
    }
    os << 0+b.base[i][1] << '\n';
  }
  return os;
}
typedef char Move; // 1-31 are out-of-base moves, 32 is advance up, 33 is advance and 34 is advance down
int generate_moves(Board const &b, Move *m, int player) {
  Move *original_m = m;
 
  if (b.net[player] != 0) {
    *m++ = 32;
    *m++ = 33;
    *m++ = 34;
  }
 
  char mask_of_non_empty_bases = 0;
  for (unsigned i=0; i<5; ++i)
    mask_of_non_empty_bases |= (b.base[i][player]!=0) << i;
  char move_order[] = {1,2,4,8,16, 3,5,6,9,10,12,17,18,20,24, 7,11,13,14,19,21,22,25,26,28, 15,23,27,29,30, 31};
  for (unsigned i=0; i<31; ++i) {
    char c = move_order[i];
    if ((c & mask_of_non_empty_bases) == c)
	  *m++ = c;
  }
 
  return m - original_m;
}
u32 target[2] = {04040404040u, 00101010101u};
void make_move(Board &b, Move m, int player) {
  u32 &bnp = b.net[player];
 
  if (m<32) {
    for (unsigned i=0; i<5; ++i) {
	  if (test(m, i)) {
	    b.base[i][player]--;
	    bnp |= (077u<<(6*i)) & target[!player];
	  }
    }
  }
  else {
    u32 boarding = bnp & target[player];
    for (; boarding; boarding &= boarding-1) {
	  int row = lowest_bit_set(boarding) / 6;
	  b.base[row][!player] = 0;
	  b.base[row][player]++;
    }
    bnp &= ~target[player];
    bnp = player==0 ? bnp << 1 : bnp >> 1;
   
    if (m==32)
	  bnp = ((bnp & 00000000077u) << 24) + (bnp >> 6);
    else if (m==34)
	  bnp = ((bnp & 00077777777u) << 6) + ((bnp & 07700000000u) >> 24);
   
    bnp &= ~holes;
  }
 
  b.net[!player] &= ~bnp;
}
int eval(Board const &b) {
  int on_base_diff = 0;
  for (int i=0; i<5; ++i)
    on_base_diff += b.base[i][0] - b.base[i][1];
 
  int on_net_diff = popcount(b.net[0]) - popcount(b.net[1]);
 
  int score = 500*on_base_diff + 400*on_net_diff - 32 + std::rand()%64;
  return score;
}
int const cost[35] = {0, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1};
int negamax(Board const &board, int alpha, int beta, int depth, int player) {
  if (depth <= 0)
    return player==0 ? eval(board) : -eval(board);
 
  Move moves[33];
  int n_moves = generate_moves(board, moves, player);
  for (int i=0; i<n_moves; ++i) {
    Board copy = board;
    make_move(copy, moves[i], player);
    int score = -negamax(copy, -beta, -alpha, depth-cost[static_cast<int>(moves[i])], !player);
    if (score > alpha) {
	  alpha = score;
	  if (score > beta)
	    break;
    }
  }
 
  return alpha;
}
Move search_root(Board const &board, int player) {
  double start_time = now();
  Move moves[33];
  int n_moves = generate_moves(board, moves, player);
  if (n_moves == 0)
    return 0;
  int depth, alpha;
  for (depth = 1; depth < 5 || now() < start_time + 120.0; ++depth) {
    alpha = -999999;
    for (int i=0; i<n_moves; ++i) {
	  Board copy = board;
	  make_move(copy, moves[i], player);
	  int score = -negamax(copy, -999999, -alpha, depth-1, !player);
	  if (score > alpha) {
	    alpha = score;
	    std::rotate(moves, moves + i, moves + i + 1);
	    std::cout << depth << ": (" << 0+moves[0] << ") " << alpha << ' ' << now()-start_time << '\n';
	  }
    }
    if (std::abs(alpha)>500000)
	  break;
    std::cout << depth << ". (" << 0+moves[0] << ") " << alpha << ' ' << now()-start_time << '\n';
  }
  return moves[0];
}
int main(int argc, char **argv) {
  int seed = argc == 2 ? atoi(argv[1]) : std::time(0);
  std::cout << "seed = " << seed << '\n';
  std::srand(seed);
 
  Board board;
  int player = 0;
  while (1) {
    std::cout << board << '\n';
    Move move;
    if (player == 0)
	  move = search_root(board, player);
    else {
	  int i;
	  std::cin >> i;
	  move = i;
    }
    if (move == 0)
	  break;
    make_move(board, move, player);
    player = !player;
  }
}

PARTNERS