How many moves do you have available in a typical position? If the answer is hundreds or thousands, you probably can't use minimax to play this decently. I would try with Monte-Carlo Tree Search (MCTS) instead. It's relatively easy to get something working (assuming random moves lead to a finished game eventually, which I guess would be the case). You may have to program some non-randomness from the beginning, if there are trivial decisions in some cases that are important to get right (in go, you shouldn't plug your own eyes).

The number of possible moves is not so high because there are always 3 moves for all outside pieces and 31 moves for bringing pieces out of the base. But since bringing too many pieces out is strategically not so good, my move generator only generates 5 moves for bases (+additional moves if hostile pieces are beneath the bases). So a typical position will have ~8 moves!

Oooh! You mean that all outside figures move in lockstep? So if you move up-right it means that all the external figures move up-right? That makes the problem much more tractable.

I will take a look at your alpha-beta code and see if I find any problems with it. I have written this type of thing enough times that I should be able to spot most common mistakes.

to test your search code, write a trivial game like tic-tac-toe and test it on that. that way you can see very quickly if it making obvoius mistakes.

My new code (without source-tag, since its not working correct):

Let's try with code tags instead:
int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta)
{
cEvaluation eval;
int best = -INFINITY;
int check_win = CheckWin(board, eval, left);
if (check_win != 0)
return check_win;
if (depth <= 0)
return Evaluate(board, left, eval);
std::vector<tMove> movelist;
GenerateMoves(&board, left, movelist);
if (movelist.size() == 0)
throw "No more moves!"; // how to handle?
int max = -INFINITY;
for (unsigned int i = 0; i<movelist.size(); ++i)
{
tBoard board2;
memcpy(&board2, &board, sizeof(tBoard));
ExecuteMove(&board2, left, movelist, eval);
int val = -NegMax(board2, depth-1, !left, -beta, -alpha);
if (val > max)
max = val;
if (val > alpha)
alpha = val;
if (alpha >= beta)
return alpha;
}

return max;
}

tMove cBoard::AlphaBetaStart(bool left, int maxdepth)
{
cEvaluation eval;
tMove bestmove;
bestmove.rating = -INFINITY;
int currentscore;
_bestmoves.clear();
_cpuleft = left;

std::vector<tMove> movelist;
GenerateMoves(&m_fields, left, movelist);
for (unsigned int i=0; i<movelist.size(); ++i)
{
tBoard board2;
memcpy(&board2, &m_fields, sizeof(tBoard));
ExecuteMove(&board2, left, movelist, eval);
currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY);
if (currentscore > bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist.move;
}
tMove move;
move.move = movelist.move;
move.rating = currentscore;
_bestmoves.push_back(move);
}
return bestmove;
}

int cBoard::Evaluate(const tBoard& b, bool left, cEvaluation& eval)
{
int score = eval.pirates_base * 5 + eval.pirates_outside * 4;
if (left != _cpuleft)
score = -score;
return score;
}


Here's your code with a couple of edits and comments:
int cBoard::NegMax(tBoard& board, int depth, bool left, int alpha, int beta) {
cEvaluation eval;
// int best = -INFINITY; <-- unused
int check_win = CheckWin(board, eval, left); // <-- Why does this take a cEvaluation?
if (check_win != 0)
return check_win;
if (depth <= 0)
return Evaluate(board, left, eval);
std::vector<tMove> movelist;
GenerateMoves(&board, left, movelist);

//if (movelist.size() == 0)
// throw "No more moves!"; // how to handle? <-- No need to handle. If you don't have moves, you lose, which doesn't require special handling

int max = -INFINITY; // <-- The code is a bit simpler if you don't have `max' and simply use alpha, but I think this is still correct.
for (unsigned int i = 0; i<movelist.size(); ++i) {
tBoard board2;
memcpy(&board2, &board, sizeof(tBoard)); // If you could undo moves, you wouldn't need to make copies and things would be faster
ExecuteMove(&board2, left, movelist, eval); // <-- Why does this take a cEvaluation?
int val = -NegMax(board2, depth-1, !left, -beta, -alpha);
if (val > max) {
max = val;
if (val > alpha) {
alpha = val;
if (alpha >= beta)
return alpha;
}
}
}
return max;
}
tMove cBoard::AlphaBetaStart(bool left, int maxdepth) {
cEvaluation eval;
tMove bestmove;
bestmove.rating = -INFINITY;
int currentscore;
_bestmoves.clear();
_cpuleft = left;

std::vector<tMove> movelist;
GenerateMoves(&m_fields, left, movelist);
for (unsigned int i=0; i<movelist.size(); ++i) {
tBoard board2;
memcpy(&board2, &m_fields, sizeof(tBoard));
ExecuteMove(&board2, left, movelist, eval);
currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, -bestmove.rating); // <-- Use "-alpha" instead of a fixed +INFINITY
if (currentscore > bestmove.rating) {
bestmove.rating = currentscore;
bestmove.move = movelist.move;
}
tMove move;
move.move = movelist.move;
move.rating = currentscore;
_bestmoves.push_back(move); // <-- I am not sure what this is for. It might contain crappy moves.
}
return bestmove;
}
int cBoard::Evaluate(const tBoard& b, bool left, cEvaluation& eval) {
int score = eval.pirates_base * 5 + eval.pirates_outside * 4; // <-- You should be computing the number of figures for the player to move minus the number of figures for the opponent. This one-sided evaluation seems suspect.
if (left != _cpuleft)
score = -score;
return score;
}


Other than your evaluation function possibly being broken, I don't see anything particularly wrong with your code.

Thanks for the help folks

to test your search code, write a trivial game like tic-tac-toe and test it on that. that way you can see very quickly if it making obvoius mistakes.[/quote]
Good idea, i will try that!

@alvaro
How did my code correctly with the source tag?
The "{code}" didn't work properly for me.

int check_win = CheckWin(board, eval, left); // <-- Why does this take a cEvaluation?[/quote]
cEvaluation just contains information about number of remaining pieces for both side, etc. This is needed first time in the CheckWin() function and later in the Evaluation() function.

currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, -bestmove.rating); // <-- Use "-alpha" instead of a fixed +INFINITY[/quote]
You mean:
currentscore = -NegMax(board2, maxdepth, !left, -alpha, -bestmove.rating);
?

int score = eval.pirates_base * 5 + eval.pirates_outside * 4; // <-- You should be computing the number of figures for the player to move minus the number of figures for the opponent. This one-sided evaluation seems suspect.[/quote]
I was doing this originally and the result was even stranger.
I know that the evaluation-function is probably the main component to focus on. This might by the real challenge to do this properly for this game.

You are welcome to play the game and brainstorm with me possible ways for the evaluation function

Once again, thanks for your help!

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 = 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 << 0+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 << 0+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;

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[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;
}
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[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[0] - b.base[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, player);
int score = -negamax(copy, -beta, -alpha, depth-cost[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 + 1.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';
}
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;
}
}


Wow ... great code!
I tried to run it and get the following error:

"Run-Time Check Failure #2 - Stack around the variable 'moves' was corrupted"
Edit: found the problem, since there can be maximum of 34 moves the declarations of "Move moves[33];" must be changed to "Move moves[34];" !


P.S: there are 2 additional rules i idn't mention cuz of simplicity:
- once a piece moves into hostile base, that hostile base is broken, which means that any pieces moving into it will be destroyed
- a piece located directly beside a base will always move into it regardless of the move-type, e.g. if piece is on 3rd row beside the hosile base and the chossen move is "up", then the piece will go into the base on 3rd row and not , as expected, into base on 4th row.

PPS: i am not sure but bringing out too many pieces out of a base may strategically not be so good. So in my move generation i only consider moves with only one base (in your case 1,2,4,8,16) with additional base moves only if there is a hostile piece outside beside the base. This reduces the number of possible moves a lot.
I might also be wrong with this consideration ... i have to get a better player with this game.