Generating moves in Reversi

Started by
19 comments, last by carlos2 4 years, 4 months ago

This code you shared really inspired me. your code is very compact and does what it is supposed to do very quickly. The problem I see is what comes afterwards and I wondered how I could take advantage of the board inspection done here to avoid inspecting the board again to play one of these moves this algorithm found..

The victims are there.. if I masked them with a star bitmap of all possible flips in all directions? No, this won't work. you'll get enemy discs not belonging to those affected by the move. then I divided the problem into smaller pieces. For example:

The unfolded loop of the north inspection:

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;


What do I have after the execution of the second line?. enemies that areright next to my discs northwards... mmmm what is I now move northwards and AND them with empty squares? I'll get only the captures of length 1. and I can start drawing the capture bitmap of that move. If I now nove north again and AND with empties I'll obtain the captures of length 2... and so on. like:

u64 moveattacks[64];
u64 flippattern[64 /* Squares */][ 8 /*Directions */][6 /* Length */];
int payoff[64]; 
 /* new code */ 
u64 generate_moves(u64 own, u64 enemy) {
  u64 result = 0ull;
  u64 victims, partialresult, accum;
  int i;
 
  u64 empty = ~(own | enemy);  
  victims  =  NORTH(own)  & enemy; /* At this point I have my immediate enemies */
  accum    = NORTH(victims);
  partialresult   =  accum & empty;   /* Runs of length 1  */
  
  if (partialresult) {
	 payoff[i] = 0; 
     for( i= 0; i < 64; i++)
         if (partialresult & (1ULL << i)) {
            moveattacks[i] = flippattern[i][SOUTHWARDS][0];
			payoff[i]++;
	     }
     result |= partialresult;		 
  }
  
  victims  =  accum  & enemy;
  accum    =  NORTH(victims);
  partialresult   =  accum & empty; /* Runs of length 2 */
  
  
  if (partialresult) {
     for( i= 0; i < 64; i++)
         if (partialresult & (1ULL << i)) {
            moveattacks[i] |= flippattern[i][SOUTHWARDS][1];
			payoff[i]  +=2;
	     }
     result |= partialresult;		 
  }


  
  victims  =  accum  & enemy;
  accum    =  NORTH(victims);
  partialresult   =  accum & empty; /* Runs of length 3 */
  
  if (partialresult) {
  for( i= 0; i < 64; i++)
     if (partialresult & (1ULL << i)) {
        moveattacks[i] |= flippattern[i][SOUTHWARDS][2];
		payoff[i]  +=3;
	 }
  result |= partialresult;
  }


  
  victims  =  accum  & enemy;
  accum    =  NORTH(victims);
  partialresult   =  accum & empty; /* Runs of length 4 */
  
  if (partialresult) {
  for( i= 0; i < 64; i++)
     if (partialresult & (1ULL << i)) {
        moveattacks[i] |= flippattern[i][SOUTHWARDS][3];
		payoff[i]  +=4;
     }
  result |= partialresult;
  }


  
  victims  =  accum  & enemy;
  accum    =  NORTH(victims);
  partialresult   =  accum & empty; /* Runs of length 5 */
  
  if (partialresult) {
  for( i= 0; i < 64; i++)
     if (partialresult & (1ULL << i)) {
        moveattacks[i] |= flippattern[i][SOUTHWARDS][4];
		payoff[i]  +=5;
	 }
  result |= partialresult;
  }


  
  victims  =  accum  & enemy;
  accum    =  NORTH(victims);
  partialresult   =  accum & empty; /* Runs of length 6 */
  
  if (partialresult) {
  for( i= 0; i < 64; i++)
     if (partialresult & (1ULL << i)) {
        moveattacks[i] |= flippattern[i][SOUTHWARDS][5];
		payoff[i]  +=6;
     }
  result |= partialresult;
/* The code must continue here for the remaining 7 directions... */
 
  }
 return result;
}

ppattern array is a pre-computed 64 x 8 x 6 matrix (64 squares, 8 possible directions, 6 possible lengths ). Now I can even count the discs that are being flipped by the move. At the end of the routine I'll get:

1) A bitmap of all move candidates. (The original outcome) plus:

2) An array of masks corresponding to each of these moves. ( the impact on the board of each one)

3) the payoff of each move in terms of number of opponent discs being flipped.

Thank you very much for your code again. in return, I'm sharing this excerpt of mine. The complete code is too long and I think this excerpt depicts well enough the idea.

This topic is closed to new replies.

Advertisement