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.