# Generating moves in Reversi

This topic is 2155 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

Edited by patishi

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

Edited by patishi

##### Share on other sites

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.

##### Share on other sites

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

Edited by patishi

##### Share on other sites
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.

##### Share on other sites

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

##### Share on other sites

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

Edited by patishi

• 18
• 29
• 11
• 21
• 16