Bit board in the Othello

Bit board > Bit board in the Othello

With the bit board in the Othello, I explain the numeration using the bit board in the Othello.

Table of contents

Summary

Data structure to express in 1 bit whether a stone exists about 8x8 = 64 trout.

Because 64 bits, Othello have the stone of two kinds of black and white about one stone class, I can express a board side in 64 bits variable x 2.

Can perform the handling of of a judgment and the stone whether sandwiched the stone of the partner inversion about plural stones only by a shift and a Boolean operation at the same time without using recurrence and the loop (bit parallel characteristics); collect it, and processing becomes higher-speed than normal data structure.

Detailed

Because 8x8 = 64 trout, the stone are two kinds of black and white, the board side of the Othello can express a board aspect if two prepare for a 64 bits integer.

  typedef uint64 BitBoard;  class CBanmen  {     BitBoard black;     BitBoard white,  }, 

Monochrome inversion

When I call the next level in the pro-inversion such as negative max, the negative alpha game tree search algorithm, it is necessary to reverse after point of the board side, but has only to replace order when I express a board side of the Othello in two bit board black, white and hand it as an argument of the search function when I hand it with an argument as follows.

  int negaAlpha(BitBoard black, BitBoard white, int alpha, int beta, int depth)  {      ....      for (about all legal start) {          I carry out start,          I replace a αΒ level with // black and white and call the next level          int score = -negaAlpha (white, black, -beta, -alpha, depth-1),            I return start,          ....      }      ....  } 

Correspondence of each trout eye and bit of the board side

As for the trout of the Othello, a headgear with a projection at the left is A, B, C, horizontally in the origin ...To the H, vertical direction 1, 2, 3, ...I am indexed with 8 and am appointed like A1, D3.

It should be assumed that I assume col (0..7), a vertical direction row (0..7) in a horizontal direction with the bit number of the bit board corresponding to the trout with col + row * 8.

  BitBoard cr2bitboard(int col, int row)  // col (0..7), bit board generation corresponding to row (0..7)  {     return (BitBoard)1 <<(col + row * 8),  } 

Stone inversion processing

It is BitBoard mv; at a black start position It is BitBoard rev; at the position that thereby turns over If that is the case, I can describe the update handling of board side as follows.

  black ^= mv | rev;  White ^= rev; 

When I express a board side with sequence, it costs the inversion processing in proportion to the number of stones turning over, but can process it with uniformity cost without depending on loadage in koku to turn over as above because it can process a plural number trout at the same time if I use a bit board.

The processing to cancel start, and to return to an original state becomes same as the inversion processing mentioned above.

It does not have to return the state of the board side if I do it as follows if I hand a monochrome bit board with an argument when I call a function of the next depth by a game tree search.

 int negaAlpha(BitBoard black, BitBoard white, int alpha, int beta, int depth) {      ....      for (about all legal start) {          I carry out // start and I replace a αΒ level with black and white and call the next level          int score = -negaAlpha (white ^ rev, black ^ (mv | rev),                                 -beta, -alpha, depth-1),            ....      }      .... } 

Inversion pattern calculation

The conditions that are legal start are as follows.

• A start position is a blank
• After the stones of the partner continued about more than one of 8 directions from the start point, there is one's stone

The stone of consecutive partners becomes the inversion pattern.

Method using the loop

I show a cord when I use below a loop.
You check it with this cord only about 1 direction, but, actually, must check it about all 8 directions.

 BitBoard getRevPat(BitBoard black, BitBoard white, // board side state                    BitBoard m)  In // m, all the others are 0 with 1 only start point, 1 bit {     BitBoard rev = 0,     if (((black | White) & m)!= 0)  When there is not // start point in a blank         return rev;     BitBoard mask = transfer(m);     While while (mask!= 0 && (mask & white)!= 0) {// Shiraishi continues         rev |= mask;         mask = transfer(mask);     }     if ((mask & black) = = 0)  Without // Kuroishi, I cannot start it         return 0,     else         return rev; // inversion pattern} 

BitBoard transfer(BitBoard m) puts back the pattern that moved to the specific direction. If it is movement to the right direction,

 BitBoard transfer(BitBoard m) {     return (m>>1) & 0x7f7f7f7f7f7f7f7f; } 

I can define と.

Method not to use a loop for

Because the upper limit of the loadage in koku of the partner turning over about one direction is 6, in the case of each, there is it without using a loop and can develop it as follows.

     BitBoard wh = white & 0x7e7e7e7e7e7e7e7e;    Guard for // traverses     BitBoard m2, m3, m4, m5, m6;     BitBoard m1 = pos >> 1, // pos: Start point     if ((m1 & wh)!= 0) {         if (((m2 = m1 >> 1) & wh) = = 0) {             if ((m2 & black)!= 0)  When I return only // one                 rev |= m1;         } else if (((m3 = m2 >> 1) & wh) = = 0) {             if ((m3 & black)!= 0)  When I return // two                 rev |= m1 | m2;         } else if (((m4 = m3 >> 1) & wh) = = 0) {             if ((m4 & black)!= 0)  When I return // three                 rev |= m1 | m2 | m3;         } else if (((m5 = m4 >> 1) & wh) = = 0) {             if ((m5 & black)!= 0)  When I return // four                 rev |= m1 | m2 | m3 | m4;         } else if (((m6 = m5 >> 1) & wh) = = 0) {             if ((m6 & black)!= 0)  When I return // five                 rev |= m1 | m2 | m3 | m4 | m5;         } else {             if (((m6 >> 1) & black)!= 0)  When I return // six                 rev |= m1 | m2 | m3 | m4 | m5 | m6;         }     } 

Method not to use condition divergence for

The correction of this knob is expected.

Allied item

• Bit operation
• Bit board
• Bit board in the chess
• Bit board in the shogi

This item is an unfinished item in conjunction with the games. I demand the cooperator who corrects it, and corrects this item (portal game).

It is acquired by "bit board &oldid=48206803 in the https://ja.wikipedia.org/w/index.php?title= Othello"

This article is taken from the Japanese Wikipedia Bit board in the Othello

This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.

Wikipedia and Tranpedia does not guarantee the accuracy of this document. See our disclaimer for more information.

In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.