Sign in to follow this  
patishi

Generating moves in Reversi

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 this post


Link to post
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 this post


Link to post
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.

Edited by sunandshadow

Share this post


Link to post
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 this post


Link to post
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.

Edited by Paradigm Shifter

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this