![tongue.png](http://public.gamedev.net//public/style_emoticons/default/tongue.png)
Last thing left now is extending the board structure to store the "blown door" state and the make_move(...) logic.
Your code was written very well and smart !
Thanks again
![smile.png](http://public.gamedev.net//public/style_emoticons/default/smile.png)
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
#include <iostream>
#include <algorithm>
#include <ctime>
// A function to measure time in seconds. I usually implement it wigh
// gettimeofday, but I am posting this one because it's standard.
double now() {
return static_cast<double>(std::clock())/CLOCKS_PER_SEC;
}
typedef unsigned u32;
bool test(u32 x, int bit) {
return (x >> bit) & 1;
}
// Count number of set bits
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;
}
int lowest_bit_set(unsigned int w) {
static int const 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
};
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 = 0;
for (int j=0; j<5; ++j)
base[j] = 3;
}
}
};
std::ostream &operator<<(std::ostream &os, Board const &b) {
for (int i=0; i<5; ++i) {
os << "*0123"[1+b.base[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 << "*0123"[1+b.base[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;
// Move figures on the net (put these moves first because they are often the best)
if (b.net[player] != 0) {
*m++ = 32;
*m++ = 33;
*m++ = 34;
}
// Now generate moves bringing out figures from bases
char mask_of_non_empty_bases = 0;
for (unsigned i=0; i<5; ++i)
mask_of_non_empty_bases |= (b.base[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;
if ((c & mask_of_non_empty_bases) == c)
*m++ = c;
}
return m - original_m;
}
void make_move(Board &b, Move m, int player) {
static u32 const target[2] = {04040404040u, 00101010101u};
u32 &bnp = b.net[player];
if (m<32) {
for (unsigned i=0; i<5; ++i) {
if (test(m, i)) {
b.base[player]--;
bnp |= (077u<<(6*i)) & target[!player];
}
}
}
else {
// Loop over the figures that are boarding the enemy bases
for (u32 boarding = bnp & target[player]; boarding; boarding &= boarding-1) {
int row = lowest_bit_set(boarding) / 6;
b.base[row][!player] = -1;
if (b.base[row][player] >= 0 && b.base[row][player] < 3)
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) {
static int const base_value_table[5] = {-200, 0, 500, 1000, 1500};
int on_base_diff = 0;
for (int i=0; i<5; ++i)
on_base_diff += base_value_table[b.base[0]+1] - base_value_table[b.base[1]+1];
int on_net_diff = 400 * (popcount(b.net[0]) - popcount(b.net[1]));
int noise = -32 + std::rand() % 64;
int score = on_base_diff + on_net_diff + noise;
return score;
}
int negamax(Board const &board, int alpha, int beta, int depth, int player) {
static int const depth_reduction[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};
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, player);
int score = -negamax(copy,
-beta,
-alpha,
depth-depth_reduction[static_cast<int>(moves)],
!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 + 2.0; ++depth) {
alpha = -999999;
for (int i=0; i<n_moves; ++i) {
Board copy = board;
make_move(copy, moves, 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';
}
--depth;
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 computer;
std::cout << "Which player am I? (0=pirates (left), 1=sailors (right)) ";
std::cin >> computer;
int player;
std::cout << "Who goes first? (0=pirates (left), 1=sailors (right)) ";
std::cin >> player;
while (1) {
std::cout << board << '\n';
Move move;
if (player == computer)
move = search_root(board, player);
else {
int i;
std::cin >> i;
move = i ? i : search_root(board, player);
}
if (move == 0)
break;
make_move(board, move, player);
player = !player;
}
}
Well, I think there is only one rule that you didn't get right: It is OK for an attacker to enter a destroyed enemy base (the piece simply goes back to the corresponding base at the other side of the board). I've played enough games against the program that I am fairly confident I have the rules right.[/quote]
The rule works like this:
As you already wrote, attacker can enter destroyed base but an attacker cann't come back to destroyed base.
E.g.: attacker is at height 3 beside enemy's base, he can go through it, doesn't matter destroyed or not, but if his home base at height 3 is destroyed he will be also destroyed.
As i see now in your source code above you already implemented this rule correctly. So base[]=-1 means destroyed base (and is drawn with "*").