Hi all. after looking for a rather "easy" board game to implement I came across Reversi. it is the perfect challange for me after coming from connect 4. its gonna be implemented in C which i just started learning (coming from java) so needed something not that hard (like chess)

Well, it seems that generate the moves is not so easy as at appears.. sure i can do it in a rather naive approach and use a normal array for the board and go through each row,column and diagonal (or maybe each square)

but it will be a lot of itterations over the array and very slow. I am trying to think of a way to implement this with bit boards, but i can't seem to find an algorithm that does this. Any suggestions? I don't mind using a regualr array, but i need something faster than what i've came up with so far.

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