63 62 61 60 59 58 57 56
55 54 53 52 51 50 49 48
47 46 45 44 43 42 41 40
39 38 37 36 35 34 33 32
31 30 29 28 27 26 25 24
23 22 21 20 19 18 17 16
15 14 13 12 11 10  9  8
 7  6  5  4  3  2  1  0

Thank you very much for all the help

The mave move function can be implemented based on your move generator. you must first define a set of 64 masks which represent the row, column and diagonals of each square. AND it with enemy and own, run thw same code but this time you'll collect the victims in result instead. now you can make a move by switching off enemy's bits using this result mask and switch on own's bits plus the new move bit. done.

Thanks for your code, What I do not understand much is why do you iterate only 4 times? what happens to longer than 4 opponent's runs? to explain myself , please consider a board on which a1 is white, all other squares are black except a8 which is empty and it's white to move. How will this algorithm identify a8 as valid if it only runs 4 times northwards?

The loop runs 5 times. Here's what happens in your example:

u64 victims = N(own) & enemy; // = a2

victims |= N(victims) & enemy; // = a2 | a3

victims |= N(victims) & enemy; // = a2 | a3 | a4

victims |= N(victims) & enemy; // = a2 | a3 | a4 | a5

victims |= N(victims) & enemy; // = a2 | a3 | a4 | a5 | a6

victims |= N(victims) & enemy; // = a2 | a3 | a4 | a5 | a6 | a7

result |= N(victims) & empty; // = a8

The loop runs 5 times. Here's what it does in your example:

u64 victims = N(own) & enemy; // = a2

victims |= N(victims) & enemy; // = a2 | a3

victims |= N(victims) & enemy; // = a2 | a3 | a4

victims |= N(victims) & enemy; // = a2 | a3 | a4 | a5

victims |= N(victims) & enemy; // = a2 | a3 | a4 | a5 | a6

victims |= N(victims) & enemy; // = a2 | a3 | a4 | a5 | a6 | a7

result |= N(victims) & empty; // = a8

Yes, you are right, I unfolded the loop wrongly

I reworked a bit this code to speed it up. loop unfolding and use of macros to avoid the huge count of procedure calls

typedef unsigned long long u64;


#define NORTH(x) ((x) << 8)
#define SOUTH(x) ((x) >> 8)
#define EAST(x) (((x) & 0xfefefefefefefefeull) >> 1)
#define WEST(x) (((x) & 0x7f7f7f7f7f7f7f7full) << 1)
#define NW(x)    NORTH(WEST(x))
#define NE(x)    NORTH(EAST(x))
#define SE(x)    SOUTH(EAST(x))
#define SW(x)    SOUTH(WEST(x))




u64 generate_moves(u64 own, u64 enemy) {
  u64 result = 0ull;
  u64 victims;
 
  u64 empty = ~(own | enemy);
  
 /* North */
 
 victims  =  NORTH(own)  & enemy; 
 victims |=  NORTH(victims) & enemy;
 victims |=  NORTH(victims) & enemy;
 victims |=  NORTH(victims) & enemy;
 victims |=  NORTH(victims) & enemy;
 victims |=  NORTH(victims) & enemy;
 result  |=  NORTH(victims) & empty;


/* South */


 victims  =  SOUTH(own)  & enemy;
 victims |=  SOUTH(victims) & enemy;
 victims |=  SOUTH(victims) & enemy;
 victims |=  SOUTH(victims) & enemy;
 victims |=  SOUTH(victims) & enemy;
 victims |=  SOUTH(victims) & enemy;
 result  |=  SOUTH(victims) & empty;
 
 /* West */
 
 victims  =  WEST(own)  & enemy;
 victims |=  WEST(victims) & enemy;
 victims |=  WEST(victims) & enemy;
 victims |=  WEST(victims) & enemy;
 victims |=  WEST(victims) & enemy;
 victims |=  WEST(victims) & enemy;
 result  |=  WEST(victims) & empty;
 
 /* East */


 victims  =  EAST(own)  & enemy;
 victims |=  EAST(victims) & enemy;
 victims |=  EAST(victims) & enemy;
 victims |=  EAST(victims) & enemy;
 victims |=  EAST(victims) & enemy;
 victims |=  EAST(victims) & enemy;
 result  |=  EAST(victims) & empty;
 
/* North East */


 victims  =  NE(own)  & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 result  |=  NE(victims) & empty;


/* South West */
 
 victims  =  SW(own)  & enemy;
 victims |=  SW(victims) & enemy;
 victims |=  SW(victims) & enemy;
 victims |=  SW(victims) & enemy;
 victims |=  SW(victims) & enemy;
 victims |=  SW(victims) & enemy;
 result  |=  SW(victims) & empty;
 
/* North West */


 victims  =  NE(own)  & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 victims |=  NE(victims) & enemy;
 result  |=  NE(victims) & empty;


/* South East */
 
 victims  =  SE(own)  & enemy;
 victims |=  SE(victims) & enemy;
 victims |=  SE(victims) & enemy;
 victims |=  SE(victims) & enemy;
 victims |=  SE(victims) & enemy;
 victims |=  SE(victims) & enemy;
 result  |=  SE(victims) & empty;
 
 return result;
}

sunandshadow said:
From a human perspective, here is some general reversi strategy: it's not just about capturing the most pieces per move. You want to get the corners, because they are the only positions which cannot be retaken by the opponent. Corners can be used to control the walls, and walls can be used to control the middle.

Adding to this, for me the usual strategy is trying to have the least peaces. This way you can control the opponent by limiting his options. If you have your peaces surrounded by his pieces, he likely have to make a move he does not want to, giving you a corner. The end game is then to invert the entire board from there.

Most Reversi algorithms are easy to beat, but the one came with Windows was very good. Really missing this...

carlos2, are you sure those changes to the code are speed improvements at all? Unrolling loops and inlining function calls are both basic optimizations that compilers will perform for you.