Generating moves in Reversi

Here's some very straight-forward code to generate moves in reversi:

typedef unsigned long long u64;

u64 N(u64 x) {
  return x << 8;
}

u64 S(u64 x) {
  return x >> 8;
}

u64 E(u64 x) {
  return (x & 0xfefefefefefefefeull) >> 1;
}

u64 W(u64 x) {
  return (x & 0x7f7f7f7f7f7f7f7full) << 1;
}

u64 NW(u64 x) {
  return N(W(x));
}

u64 NE(u64 x) {
  return N(E(x));
}

u64 SW(u64 x) {
  return S(W(x));
}

u64 SE(u64 x) {
  return S(E(x));
}

u64 generate_moves(u64 own, u64 enemy) {
  u64 result = 0ull;
 
  u64 empty = ~(own | enemy);
  u64 victims = N(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= N(victims) & enemy;
  result |= N(victims) & empty;
 
  victims = S(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= S(victims) & enemy;
  result |= S(victims) & empty;
 
  victims = W(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= W(victims) & enemy;
  result |= W(victims) & empty;
 
  victims = E(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= E(victims) & enemy;
  result |= E(victims) & empty;
 
  victims = NW(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= NW(victims) & enemy;
  result |= NW(victims) & empty;
 
  victims = NE(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= NE(victims) & enemy;
  result |= NE(victims) & empty;
 
  victims = SW(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= SW(victims) & enemy;
  result |= SW(victims) & empty;
 
  victims = SE(own) & enemy;
  for (int i=0; i<5; ++i)
    victims |= SE(victims) & enemy;
  result |= SE(victims) & empty;
 
  return result;
}

It can think of a couple of ways to improve it, but let's see if you can understand the basic idea from that code.

Thanks a lot for the code, very elegant! it will take me some time to understand what's going on.. i will get into it :)

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.

thx for the tip! yes,I read a little about positions evaluation in Reversi. My first instinct was ofcourse to count the number of players for each side, but it appeared to be wrong way, at least in the beginning and middle stages of the game. I read somewhere that the numbers of possible move (i.e mobility) is also an important factor

Alvaro: I am looking at your code above, (still investigating it..but i am starting to see what's going on) I have a technical question though,
when you are doing: u64 empty = ~ (own | enemy) , isn't it like saying: empty = 0L ? (or something like that..) is there a special reason you chose to use a bit operation to do that?

EDIT: sorry, my mistake..i just relized that i was wrong :)

Twiddles ~ is the bitwise NOT operator, not logical NOT (bang !) so it inverts all the bits.

EDIT: It sets all bit positions not occupied by you or your opponent to 1, i.e. all the empty squares.

yeah.thanks! I just noticed my mistake. the empty bits are set to 1

EDIT: ok,forget about it..I will simplify the question. I pretty much got the move generating algorithm, and i know that i need to do a XOR operation on both the white and black boards with the victims board in order to actually play the move. but if i have a bit pattern (the result) containing all possible moves on the board,and the user chooses to play only one of them, than i can't do XOR on the whole board .. i need to do it specifically on the players that related to the square chosen. I hope you understand what i am asking

You need to write a function to perform a move on a board. I envision the code for that would look a bit like the code to compute queen attacks in chess. My first thought would be to start with a technique called magic bitboards. But there are some details I have to think through. I'll post some code if I find the time.

Ok thanks a lot. I will start writing the move generating function and see if i can handle the makeMove function as well.

Alvaro,I have another question regarding your code: I assume that here also i need to use (visualize) a board representation with one spare bit at each column?

(8) (17)

7 16 .......

6 15 .......
5 14 .......
4 13 .......
3 12 .......
2 11 .......
1 10 .......
0 9 .......

as i understand from your code, you did it by rows and not columns like the above example

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

There is no spare bit anywhere.

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.