Negamax AI and staying on the same turn

If a turn consists of several moves, I would redefine "move" to mean the whole set of actions you take in one turn. Can you describe a bit the game you are working on?

It's a nine men morris game.

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.

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.

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.

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.

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?

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.

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.

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.

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

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.

Thanks for the snippet. What do the set bits of the magic table represent and why did you use 0x4444444444444444ull ??

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.

 

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.

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.

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

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.

 

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.