# A.I. for a turn-based board game ...

This topic is 1935 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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![img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Edited by AticAtac

##### Share on other sites
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.

##### Share on other sites
My evaluation function right now only gives score for the number of figures remaining. Something like this:

score = own_figures - hostile_figures

##### Share on other sites
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. Edited by alvaro

##### Share on other sites
"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/

##### Share on other sites
[quote name='AticAtac' timestamp='1348230476' post='4982345']
The game:
- 2 players board game , turn based
See Attachment for the playingfield[/quote]

[quote]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?

[quote]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.

[quote]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.

[quote]- 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.

[quote]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.

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

[quote] -> 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.

[quote] -> 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. Edited by alvaro

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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[i]);
int score = movelist[i].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[i]);
int score = -movelist[i].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[i]);
int rating = movelist[i].rating;
currentscore = MiniMaxAB(board2, 0, -1000000, +1000000, rating, !left);
if (currentscore > bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist[i].move;
}
tMove move;
move.move = movelist[i].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[i].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[i]);
int rating = movelist[i].rating;
currentscore = MiniMaxAB(board2, 0, -1000000, +1000000, rating, !left);
if (currentscore > bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist[i].move;
}
tMove move;
move.move = movelist[i].move;
move.rating = currentscore;
_bestmoves.push_back(move);
}
" Edited by AticAtac

##### Share on other sites
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[i], 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[i], eval);
currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY);
if (currentscore > bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist[i].move;
}
tMove move;
move.move = movelist[i].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? Edited by AticAtac

##### Share on other sites
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).

##### Share on other sites
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!

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
[quote name='AticAtac' timestamp='1348671455' post='4983993']
My new code (without source-tag, since its not working correct):[/quote]

Let's try with code tags instead:
[code]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[i], 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[i], eval);
currentscore = -NegMax(board2, maxdepth, !left, -INFINITY, +INFINITY);
if (currentscore > bestmove.rating)
{
bestmove.rating = currentscore;
bestmove.move = movelist[i].move;
}
tMove move;
move.move = movelist[i].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;
}
[/code]

##### Share on other sites
[code]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[i], 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[i], 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[i].move;
}
tMove move;
move.move = movelist[i].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;
}
[/code]

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

##### Share on other sites
Thanks for the help folks [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

[quote]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.

[quote]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.

[quote]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);
?

[quote]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 [img]http://public.gamedev.net//public/style_emoticons/default/biggrin.png[/img]

Once again, thanks for your help! Edited by AticAtac

##### Share on other sites
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:[list]
[*]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.
[/list]
The code is written to be reasonably portable (assumes 32-bit unsigneds; I think that's all).
[code]#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;
}

for (unsigned i=0; i<5; ++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;
}
}
[/code] Edited by alvaro

##### Share on other sites
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. Edited by AticAtac

##### Share on other sites
Move moves[33]; shouldn't this be Move moves[35] for this ?

##### Share on other sites
[quote name='SimonForsman' timestamp='1348753705' post='4984347']
Move moves[33]; shouldn't this be Move moves[35] for this ?
[/quote]

Ooops! I shouldn't post code that I wrote late at night.

I think it should actually be 34 (31 non-empty combinations for bringing figures out of the base plus 3 moves). But 35 wouldn't hurt anything.

##### Share on other sites
Oh, also, the code I posted had
[code] for (depth = 1; depth < 5 || now() < start_time + 120.0; ++depth) {[/code]

That means that it will dare explore more depth if less than two minutes have elapsed. I had that in there for a test. I will edit the post and change it to something more tolerable. I will also make the 33->34 change.

##### Share on other sites
[quote name='AticAtac' timestamp='1348752512' post='4984342']
Wow ... great code![/quote]
Thanks.

[quote]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];" ![/quote]
Yup, thanks for caching that. I guess my compiler probably reserves 36 bytes when asked for 33, which is what "saved" me in my tests.

[quote]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[/quote]
I did not implement that, and the rule didn't come up in the games I played. This is an important rule because without it there are infinite games (draws, I would say). I'll implement it later.

[quote]- 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.[/quote]
Yes, I figured this out from playing with the emulator.

[quote]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.
[/quote]
That seems a little harsh. My program picks one of these moves that you forbid occasionally. What I did was penalize them as costing 2 plies in depth. So the nominal depth that my program searches to is only for normal moves (1,2,4,8,16,32,33,34 in my notation). I have a table called "cost" (bad name, sorry) to encode that.

EDIT: Oh, I also generate normal moves before multiple-figures-out-of-base moves, in the hopes that this order will speed up alpha-beta. Edited by alvaro

##### Share on other sites
Once again great work!

Next I will try to play you A.I. against the CPU in the emulator game (level 1-5) and see how it performs ;)

##### Share on other sites
[quote name='alvaro' timestamp='1348754760' post='4984355']
[quote name='SimonForsman' timestamp='1348753705' post='4984347']
Move moves[33]; shouldn't this be Move moves[35] for this ?
[/quote]

Ooops! I shouldn't post code that I wrote late at night. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

I think it should actually be 34 (31 non-empty combinations for bringing figures out of the base plus 3 moves). But 35 wouldn't hurt anything.
[/quote]

ah yes, i just thought, highest move value = 34 so 35 moves, (gotta learn to actually read the code and not just skim through it), you're right that it should be 34.