Sign in to follow this  
cryo75

Negamax AI and staying on the same turn

Recommended Posts

Hi all,

 

Currently what I'm doing if I want the AI to make a second move while on the same turn is:

 

            if (board.sameTurn)
                val = negamax(board, depth, alpha, beta);
            else
                val = -negamax(board, depth - 1, -beta, -alpha);

 

However, if I plan to move to Negascout, PVS, etc it gets more tricky and I'll end up having lots of 'if' conditions in the search. So is there a better way for the AI to handle a second move on the same turn outside of the search?

 

Thanks

Share this post


Link to post
Share on other sites

What I'm doing is that I have a game state (place, move, remove). When a remove is to be done on the same turn as place or move, I set the game state accordingly but I do not switch players.

 

However I can suspect that this is a problem because the search will then try to get the best moves for min when it should get them for max again.

Share this post


Link to post
Share on other sites
I am not very familiar with nine men morris, but I think this can be treated like multiple jumps in checkers. As I said before, you can treat everything that happens in a turn as a move. Your move-generation function can be implemented using recursion.

EDIT: You don't need to make the move generation recursive (I thought you were saying that you could go again after removing an opponent's piece). So instead of setting the game state, make the move representation indicate the piece to be removed and do the whole operation in one bout. Edited by Álvaro

Share this post


Link to post
Share on other sites

Hmmm I should consider that solution. I will need to add a property to the move so that it can hold the piece that can be removed. Also, when generating the first set of moves, I will need to determine if a move results in a remove, and if yes, get the pieces that can be removed.

Share this post


Link to post
Share on other sites

For the purposes of Nine men morris I would make the 'move' include all actions as a single unit, for simplicity so that you can continue using negamax.  If you intend to use your search engine for other types of games where it becomes necessary to break moves into different steps (e.g. Arimaa) then I suggest abandoning negamax and implementing a more generic search.  Negamax is a coding optimisation which works for 2-player single step move type games.  Once you breach that realm you can't really use negamax as you have broken its assumptions about the type of search that is being performed.

Share this post


Link to post
Share on other sites

If I implement move & remove as a single move unit, I could have for example 9x9 moves that I need to generate. Has this performance issues instead of first generating 9 moves, make the move, and then generate another 9 moves for the remove?

Share this post


Link to post
Share on other sites

If I implement move & remove as a single move unit, I could have for example 9x9 moves that I need to generate. Has this performance issues instead of first generating 9 moves, make the move, and then generate another 9 moves for the remove?

9x9 moves? Can you have that many mill-completing moves available? Since you are worrying about performance, you should primarily be concerned with the average performance of the program in positions where the game hasn't been decided yet. So I expect you typically will have very few mill-completing moves and the actual list of moves will be short.

If generating a lot of useless moves (because a beta cut-off will prove them useless) becomes an issue, you could use an object that generates the moves in stages, using a pattern that old geese like me call a "co-routine". That way your code just asks for a next move from the object, and the object can internally only generate the removals as they are needed. But it's almost certainly not worth the effort in this case.

If you are worried about performance, the alpha-beta algorithm performs much much better if you are clever about how you sort the moves. Having all the moves available in a list will allow you more flexibility as to the types of heuristics you can use for move ordering, so that's another argument for generating the complete list.

Share this post


Link to post
Share on other sites

9x9 is a little exagerated because even if both players have all their pieces on the board, most would have already formed mills and they can't be removed. So I'm sure the list will be much shorted.

 

Would using bitboards speed up the search and/or move generation? How would I set up a bitboard for such a board? Currently I keep an array of 24 items that represent a node on the board.

Share this post


Link to post
Share on other sites
I would use a representation that has either bitboards or an array for the board, and two "magic sums" (one per player) to quickly detect mill formation. I will write a little test and post the code to detect mills really really fast.

Share this post


Link to post
Share on other sites

The reality is that the number of moves will be way less than 9x9.  The remove only happens when there are 3-in-a-row which is going to be 1 or 2 times per move if at all.  For the purposes of 9 men morris.  You won't get any benefit from breaking up the move because an evaluation for an intermediate position (i.e. evaluating after the move and before the removal of a piece) doesn't really make sense - at least not to me :)

 

Other games an intermediate evaluation might be useful depending on the type of game

Share this post


Link to post
Share on other sites
Initialize `magic_sum[2] = {0x1111111111111111ull, 0x1111111111111111ull}'. Accumulate on them the magic_table entries for the squares occupied by each player. You can then use the code below to see if putting a new stone creates a new mill.
u64 magic_table[24] = {
  0x1000000010000000ull,
  0x1000000000010000ull,
  0x1000000000000001ull,
  0x0100000001000000ull,
  0x0100000000010000ull,
  0x0100000000000010ull,
  0x0010000000100000ull,
  0x0010000000010000ull,
  0x0010000000000100ull,
  0x0001000010000000ull,
  0x0001000001000000ull,
  0x0001000000100000ull,
  0x0000100000000100ull,
  0x0000100000000010ull,
  0x0000100000000001ull,
  0x0000010000100000ull,
  0x0000010000001000ull,
  0x0000010000000100ull,
  0x0000001001000000ull,
  0x0000001000001000ull,
  0x0000001000000010ull,
  0x0000000110000000ull,
  0x0000000100001000ull,
  0x0000000100000001ull
};

u64 new_mills(u64 magic_sum, int square) {
  u64 before_mills = magic_sum & 0x4444444444444444ull;
  u64 after_mills = (magic_sum + magic_table[square]) & 0x4444444444444444ull;
  return after_mills & ~before_mills;
}
EDIT: I fixed a mistake in the code. Edited by Álvaro

Share this post


Link to post
Share on other sites
I am using 64-bit integers as groups of 16 four-bit integers ("nibbles") which count how many pieces a player has in each possible mill on the board. The table indicates which mills each square participates in (one horizontal, one vertical). Since I want to detect situations where the mill counts reach 3, I use a trick where I initialize all the counters to 1 instead of 0, because detecting if a nibble has reached 4 is a bit simpler than detecting if it has reached 3: That's what "& 0x4444444444444444ull" does. Edited by Álvaro

Share this post


Link to post
Share on other sites
 


I am using 64-bit integers as groups of 16 four-bit integers ("nibbles") which count how many pieces a player has in each possible mill on the board. The table indicates which mills each square participates in (one horizontal, one vertical). Since I want to detect situations where the mill counts reach 3, I use a trick where I initialize all the counters to 1 instead of 0, because detecting if a nibble has reached 4 is a bit simpler than detecting if it has reached 3: That's what "& 0x4444444444444444ull" does.

 

So to make sure I'm following how did you define the board in order to find out the bits in the table?

I defined my board as a 1D array of 24 positions and it set it up like this:
// 0 1 2
// 3 4 5
// 6 7 8
// 9 10 11 12 13 14
// 15 16 17
// 18 19 20
// 21 22 23

So, taking as an example the first entry (ie. 0x1000000010000000ull), why did you decide to set the 1st and 8th bit?

By accumulating do you mean adding?

Also I had to change the code to Java. Java has 64bit long but not unsigned. I tried to do the following:

long m1 = magic_sum[0] + magic_table[0] + magic_table[1] + magic_table[2];
long m2 = magic_sum[1];

long t1 = new_mills(m1, 0);
long t2 = new_mills(m2, 1);

The result of m1 is 4688547452336345362, m2 is 1229782938247303441 whilst both t1 and t2 return 0. I don't think is correct.

Share this post


Link to post
Share on other sites
I think our boards are the same. I have this diagram in my code:
/*                                                                                                            
 0--------1--------2                                                                                          
 |  3-----4-----5  |                                                                                          
 |  |  6--7--8  |  |                                                                                          
 9-10-11    12-13-14                                                                                          
 |  | 15-16-17  |  |                                                                                          
 | 18----19----20  |                                                                                          
21-------22-------23                                                                                          
*/
`unsigned' is not important. I use unsigned integers in C/C++ when I am going to manipulate bits, because there are some surprises when you shift signed integers and because the C++ standard doesn't guarantee that overflow will behave nicely for signed integer types. But we are not shifting and we are not using the sign bit for anything in this case.

So, taking as an example the first entry (ie. 0x1000000010000000ull), why did you decide to set the 1st and 8th bit?

That's not right. I didn't set the 1st and the 8th bit. Each hexadecimal digit represents four bits, and bits are numbered from the least-significant, starting with 0. So I set bits 28 and 60, but that's not a useful description of what I did. I indicated which two mills the square participates in by putting a hexadecimal digit 1 in two spots. Reading the numbers from left to right, I am listing all horizontal mills first, top to bottom, and all vertical mills next, left to right.

By accumulating do you mean adding?

Yes.

`new_mills' returns the new mills formed by adding a piece at the second argument. In your example, `m1' already has the first mill completed, and you can't play at `0' anyway.
long m1 = 0x1111111111111111l + magic_table[0] + magic_table[1];
long t1 = now_mills(m1, 2); // This should return 0x1000000000000000l, because 2 completes the first horizontal mill.

Share this post


Link to post
Share on other sites
Yes that's the same board I'm using. OK now I understand the magic_table. The digits 1 at positions 0 and 15 of the first entry denote the mills having squares 0,1,2 and 0,9,11. long m1 = 0x1111111111111111l + magic_table[0] + magic_table[1]; long t1 = now_mills(m1, 2); // This should return 0x1000000000000000l, because 2 completes the first horizontal mill. When I do the above, t1 is 4611686018427387904. How can this translate to 0x1000000000000000l? So basically the new_mills function will return the same value as the magic_table entry for that square and this would mean that the mill has been closed by that stone. Would the above table work if I would include diagonal mills such as (0,3,6), (2,5,8), (15,18,21) and (17,20,23)?

Share this post


Link to post
Share on other sites
Ooops! It returns 0x4000000000000000l, of course. Sorry about that.

If you want to include diagonal mills, you need more digits. You would think that 64 bits isn't enough, but we are actually only using 3 out of every 4 bits. You can just use octal instead of hexadecimal and it would work the same.

Let me know if anything is still not clear.

Share this post


Link to post
Share on other sites
 

Ooops! It returns 0x4000000000000000l, of course. Sorry about that.

If you want to include diagonal mills, you need more digits. You would think that 64 bits isn't enough, but we are actually only using 3 out of every 4 bits. You can just use octal instead of hexadecimal and it would work the same.

Let me know if anything is still not clear.

 

I think it should return 0x4000000000000000 which I'm interpreting that the horizontal mill for square 1 is closed.

Using the same concept, is it possible to determine:

1. if mills are open (1 square is still empty, 2 owned by the player)
2. if mills are blocked (2 squares owned by the player, 1 by the opponent)
3. get adjacent squares for a square
4. get empty squares
5. etc....

And if this would be possible, I'm assuming that shifting bits needs to be done and it wouldn't work on signed values.

Share this post


Link to post
Share on other sites


Ooops! It returns 0x4000000000000000l, of course. Sorry about that.

I think it should return 0x4000000000000000 which I'm interpreting that the horizontal mill for square 1 is closed.


That's what I was saying. If the `l' at the end of the constant confused you, just ignore it: It's just C syntax for "long constant".
 

Using the same concept, is it possible to determine:

1. if mills are open (1 square is still empty, 2 owned by the player)

Yes.

2. if mills are blocked (2 squares owned by the player, 1 by the opponent)

Yes.

3. get adjacent squares for a square

You can create a table of 24 numbers that contains bitboards indicating the adjacent squares for each square.

4. get empty squares

  long empties = ~(bitboard[0]|birboard[1]);

5. etc....

Basically, yes.

And if this would be possible, I'm assuming that shifting bits needs to be done and it wouldn't work on signed values.

No, I am sure you can work around that.

Try to write code to solve one of these problems (say, find blocked mills). If you can't figure it out, ask again and I'll post some code.

EDIT: If you are going to perform all these other operations as well, I would forget about the trick of initializing the counters to 1, because it will complicate matters. So initialize to 0 instead, and now checking for mills becomes
  long mills = (magic_sum + 0x1111111111111111l) & 0x4444444444444444l;
Edited by Álvaro

Share this post


Link to post
Share on other sites
Ok, I think I will start small with using bitboards because I need to understand what the code is doing. So I read up on bitboards but all the resources I found relate to chess. However I didn't give up!!

As this game has just 24 positions I was thinking of using int. I will also have to handle signed because Java doesn't support unsigned. So I did the following:

int[] bb = {0, 0};

bb[0] = bb[0] | (1 << 0) | (1 << 1) | (1 << 2);
bb[1] = bb[1] | (1 << 9) | (1 << 21);

int free = ~(bb[0] | bb[1]) & 0xFFFFFF;

In the above code, I'm setting the positions' bits for each player, then I get the free spaces. This works fine because the result is:

110111111111110111111000

Now my question is: Do I have to loop through each bit in the result and check if the bit is set? If set, then it's free. If I use bitboards in this case what's the advantage over using a 1D array if I'm not going to get rid of the loops?

Share this post


Link to post
Share on other sites

You don't have loop over all the bits.  There is a trick to loop over just the bits that are set.

if

b=110111111111110111111000

 

then

 

c = b & (0 - b)

 

will give you the lowest bit that is set

 

once you process this bit

 

you can then do

 

b = b^c

 

and start the process over again until b = 0

Share this post


Link to post
Share on other sites
&nbsp;

You don't have loop over all the bits.&nbsp; There is a trick to loop over just the bits that are set.
if
b=110111111111110111111000
&nbsp;
then
&nbsp;
c = b &amp; (0 - b)
&nbsp;
will give you the lowest bit that is set
&nbsp;
once you process this bit
&nbsp;
you can then do
&nbsp;
b = b^c
&nbsp;
and start the process over again until b = 0

&nbsp;

Thanks for the tip. That will save lots of iterations!

Share this post


Link to post
Share on other sites

I'm nearly finished with implementing bitboards (still didn't start testing though). I have bitboards for the player, opponent, free spaces, mill positions, player mill and opponent mill positions. Each bitboard is 24bits long and representats the spaces on the board with board position 0 being the first bit (from the right).

 

I have 2 small problems which i can't figure out:

 

1. How to find out if a player mill is blocked by an opponent (2 player pieces and 1 opponent piece)

2. How to find out if a player mill is open (2 player pieces and 1 free space)

 

Do you have any tips on how I can calculate this?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this