I've done all the programming (iOS, Android) for a game, only the A.I. is left.
It is basically a turn-based board game (see below description) with easy rules, hard to master ;)
I bet i need to use minimax, but i would like to discuss here possible solutions and strategies.

The game:
- 2 players board game , turn based
See Attachment for the playingfield

Each player has a home-base with 5 slots, inside each 3 figures (column 0 and 7)
Player1 (green) is playing from left to right and Player2 (magenta) right to left

The "~" are traps, figures moving on these fields are destroyed

On each move a player can do this:

- move 1 or more figures out a base
-> if there is a figure outside, that outside-figure is destroyed, doesn't matter friendly or not
- move figures (not in the base) 1 field to left/right,
-> 3 different moves possible: right, up-right, down-right. For top and bottom: If figure leaves the board it comes out on the other side.
e.g. figure at row=0,col=2 moving up-right will land at row=4 , col=3
-> all figures must move, there is no selective move
-> if a figure steps on a hostile figure, the hostile figure is destroyed
-> if a figure steps into hosilte base, all hostile figures inside that slot are destroyed, the figure returns to home base (same slot on the opposite side)

A player wins, once all hostile figures are destroyed.

To be honest, I've already implemented an A.I. with minimax + alpha/beta pruning, but its not playing very well.
One thing i need help is the evaluation function. I am not sure how handle it correctly.

Any help welcome!

Mmmkay... what ARE you using as your evaluation function? Also if in doubt it's worth checking your alpha-beta is working correctly. It seems easy to mess up.

My evaluation function right now only gives score for the number of figures remaining. Something like this:

score = own_figures - hostile_figures

Try to learn how to play the game decently. You should get some feel for what features of a position are desirable (e.g., is it better to concentrate your pieces or spread them around?). Then add terms to your utility function for those things.

Your description of the rules is two vague for me to give you more specific advice.

"Your description of the rules is two vague for me to give you more specific advice."

The rules of this games cann't be easier. What didn't you understand?
Actually, the game was originally made on C64, you can play it in the brower here: http://c64s.com/game/101117/piracy/

The game:
- 2 players board game , turn based
See Attachment for the playingfield

So far, so good (although your punctuation already has issues).

Each player has a home-base with 5 slots, inside each 3 figures (column 0 and 7)[/quote]
Does a "3" mean there are 3 pieces in that cell? Or is the game about moving "3"s around?

Player1 (green) is playing from left to right and Player2 (magenta) right to left

The "~" are traps, figures moving on these fields are destroyed[/quote]
That part is fine.

On each move a player can do this:

- move 1 or more figures out a base
-> if there is a figure outside, that outside-figure is destroyed, doesn't matter friendly or not[/quote]
What you are saying is that you can move figures out of a base, but they get destroyed because now they are outside.

- move figures (not in the base) 1 field to left/right,
-> 3 different moves possible: right, up-right, down-right.[/quote]
Those two statements are clearly contradictory. Can the player that starts on the left move only in those three directions and the other player only in the similar leftwards directions? I can't figure out whether your "->" are bullet points or comments on the previous statements.

For top and bottom: If figure leaves the board it comes out on the other side.
e.g. figure at row=0,col=2 moving up-right will land at row=4 , col=3[/quote]
OK.

-> all figures must move, there is no selective move[/quote]
I still don't know what you mean by "selective move".

-> if a figure steps on a hostile figure, the hostile figure is destroyed[/quote]
See, the word "figure" in English can refer to something like the number "3", so I don't know if you are talking about a piece or about a number.

-> if a figure steps into hosilte base, all hostile figures inside that slot are destroyed, the figure returns to home base (same slot on the opposite side)[/quote]
Finally, this is an indication that "figure" means "piece", not "number". How is the destruction of the hostile figures different than in a non-base cell?

EDIT: By my understanding of your rules, All of player 1's pieces will be on an odd-numbered column after an odd number of moves and on an even-numbered column after an even number of moves, and the opposite for player 2. This means that player 1 is the only one whose figures can step on player 2's figures, and he just has to sweep through the board once to win. Another EDIT: Oh, I guess the "all figures must move" rule only applies to figures that are not on bases, right?

I'll play the game tonight, when I get home.

Sorry for my bad (hasty) english and explantation ^^ (lets. even don't. talk. about punctation... ;)
Well, with figures i meant pieces, each player has 15 pieces in 5 slots. If a piece moves out of a base it can land on another piece (friendly or hostile) and will destroy it.
So outside the bases there can by only one piece in a cell. If you decide to move (instead of bringing 1 or more pieces out of the base) then all your pieces must move in the SAME direction (straight, diagonal up or diagonal down).
The "3" means 3 pieces in the base. There can never be more than 1 piece in the outside field. So the piece moving into a new field always destroy the piece that have been there. Obviously, this can never happen with own pieces (because all pieces move) except by moving out of the base.

do all figures move on a players turn? this will mean a huge branching factor which is why minimax + alpha/beta pruning may not be working well (even if you have a better evaluation function - which would be essential for large branching factor games). You may have to consider implementing some pruning mechanism to reduce the lines of inquiry when delving deeper into the search. For other ideas you can reference some of the papers on the arimaa site http://arimaa.com/arimaa/ which also deals with a large branching factor game that doesn't work with monte carlo methods.

Yes, all pieces (except those in the base) move one step in the same direction. For left player e.g. the movement starts with the pieces from right-to-left, so one cann't land at own piece.
Thankls for the link i will look at.

Meanwhile, here my minimax-code:


[source lang="cpp"]//--------------------------------------------------------------------------------
int cBoard::MiniMaxAB(tBoard& board, int depth, int alpha, int beta, int sumscore, bool left)
{
if (depth == _maxdepth) return sumscore;
std::vector<tMove> movelist;
GenerateMoves(&board, left, movelist);
if (movelist.size() == 0) return sumscore;

int this_alpha = -1000000;
int this_beta = +1000000;

// Max node
if (left == _cpuleft)
{
for (unsigned int i=0; i<movelist.size(); ++i)
{
tBoard board2;
memcpy(&board2, &board, sizeof(tBoard));
ExecuteMove(&board2, left, movelist);
int score = movelist.rating;
int val = MiniMaxAB(board2, depth+1, Max(alpha, this_alpha), beta, sumscore+score, !left);
this_alpha = Max(this_alpha, val);
if (this_alpha >= beta)
{
break;
}
}
return this_alpha;
} else
{
for (unsigned int i=0; i<movelist.size(); ++i)
{
tBoard board2;
memcpy(&board2, &board, sizeof(tBoard));
ExecuteMove(&board2, left, movelist);
int score = -movelist.rating;
int val = MiniMaxAB(board2, depth+1, alpha, Min(beta, this_beta), sumscore+score, !left);
this_beta = Min(this_beta, val);
if (alpha >= this_beta)
{
break;
}
}
return this_beta;
}
return 0;
}

//--------------------------------------------------------------------------------
tMove cBoard::MiniMaxAB(bool left, int maxdepth)
{
_cpuleft = left;
_maxdepth = maxdepth;
tMove bestmove;
bestmove.rating = -1000000;
int currentscore;
_bestmoves.clear();
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);
int rating = movelist.rating;
currentscore = MiniMaxAB(board2, 0, -1000000, +1000000, rating, !left);
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;
}[/source]

The starting function is MiniMaxAB(bool left, int maxdepth), where for "left"=true the cpu player is on the left side else right side.
The evaluation of a move is done in the function ExecuteMove(...)

P.S: My Code in the code snippet doesn't seem to be shon correctly, parts are missing, is that a known bug?
E.g. i can only see
"GenerateMoves(&m_fields, left, movelist);
for (unsigned int i=0; i bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist.move;
}
..."

but it should be

"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);
int rating = movelist.rating;
currentscore = MiniMaxAB(board2, 0, -1000000, +1000000, rating, !left);
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 rewrote my code a little and use now Negmax. I guess i can to reduce the problem to
- is MinMax is suited for this kind of board game?
- is my Negmax-code correct
- is my Evaluate-Code correct

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

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;
}


Evaluate just returns the number of pieces on the board for the given player (pieces in the base are slightly prefered).
The result right now is not satisfactory. One reason could be the simple Evaluation function or maybe some bugs in my NegMax (with alpha beta) code?