Jump to content

  • Log In with Google      Sign In   
  • Create Account


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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
36 replies to this topic

#1 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 21 September 2012 - 06:27 AM

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!Posted Image

Attached Thumbnails

  • board.JPG

Edited by AticAtac, 21 September 2012 - 06:28 AM.


Sponsor:

#2 jefferytitan   Members   -  Reputation: 1642

Like
0Likes
Like

Posted 21 September 2012 - 08:58 AM

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.

#3 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 21 September 2012 - 09:01 AM

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

score = own_figures - hostile_figures

#4 Álvaro   Crossbones+   -  Reputation: 11861

Like
1Likes
Like

Posted 21 September 2012 - 09:13 AM

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, 21 September 2012 - 09:13 AM.


#5 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 21 September 2012 - 09:19 AM

"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/

#6 Álvaro   Crossbones+   -  Reputation: 11861

Like
1Likes
Like

Posted 21 September 2012 - 09:35 AM

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)

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

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

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.

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

OK.

-> all figures must move, there is no selective move

I still don't know what you mean by "selective move".

-> if a figure steps on a hostile figure, the hostile figure is destroyed

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)

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, 21 September 2012 - 09:43 AM.


#7 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 21 September 2012 - 11:33 AM

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.

#8 Druzil   Members   -  Reputation: 562

Like
0Likes
Like

Posted 23 September 2012 - 05:13 PM

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.

#9 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 24 September 2012 - 01:32 AM

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, 24 September 2012 - 03:40 AM.


#10 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 26 September 2012 - 08:57 AM

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, 26 September 2012 - 09:03 AM.


#11 Álvaro   Crossbones+   -  Reputation: 11861

Like
1Likes
Like

Posted 26 September 2012 - 09:46 AM

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).

#12 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 26 September 2012 - 02:15 PM

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!

#13 Álvaro   Crossbones+   -  Reputation: 11861

Like
1Likes
Like

Posted 26 September 2012 - 05:02 PM

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.

#14 Druzil   Members   -  Reputation: 562

Like
0Likes
Like

Posted 26 September 2012 - 05:47 PM

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.

#15 Álvaro   Crossbones+   -  Reputation: 11861

Like
1Likes
Like

Posted 26 September 2012 - 08:37 PM

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


#16 Álvaro   Crossbones+   -  Reputation: 11861

Like
1Likes
Like

Posted 26 September 2012 - 09:15 PM

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

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

Edited by alvaro, 26 September 2012 - 10:32 PM.


#17 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 27 September 2012 - 04:19 AM

Thanks for the help folks Posted Image

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.

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?

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

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.

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 Posted Image

Once again, thanks for your help!

Edited by AticAtac, 27 September 2012 - 04:22 AM.


#18 Álvaro   Crossbones+   -  Reputation: 11861

Like
2Likes
Like

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

Edited by alvaro, 27 September 2012 - 08:09 AM.


#19 AticAtac   Members   -  Reputation: 309

Like
0Likes
Like

Posted 27 September 2012 - 07:28 AM

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, 27 September 2012 - 08:04 AM.


#20 SimonForsman   Crossbones+   -  Reputation: 5753

Like
1Likes
Like

Posted 27 September 2012 - 07:48 AM

Move moves[33]; shouldn't this be Move moves[35] for this ?
I don't suffer from insanity, I'm enjoying every minute of it.
The voices in my head may not be real, but they have some good ideas!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS