Sign in to follow this  
haykan648

Othello Game c++

Recommended Posts

A vector of pointers to pieces to represent the board? Seems like many operations would be very slow if you use that. I would use two 64-bit integers myself (these are called bitboards). If you don't want to do that, have an array of 64 elements telling you what's on each square.

Share this post


Link to post
Share on other sites

A vector of pointers to pieces to represent the board? Seems like many operations would be very slow if you use that. I would use two 64-bit integers myself (these are called bitboards). If you don't want to do that, have an array of 64 elements telling you what's on each square.


Thank you. But can you be more precise ? For example what operations would be slower?

Share this post


Link to post
Share on other sites
Bitboards are cool, and it's good to have used them. The idea is that a 64bit integer can hold, well 64 yes/no infos.
So using 2 of these you have all the bits to hold for every field on a 8x8 board the info if there is a piece,
and if it is white or black. 2 yes/nos for every field on the board.
Search for bitmasks,bitboards,bitset or so on to get more infos.
When it comes to efficiency, you just can't beat those.

fast example of bitboards, thoroughly untested:


// Where this is set, there is a piece
unsigned long hasPiece;
// Where this is set, the piece is white, if not it's black
unsigned long whatPiece;

// add a white piece @ 5x4 
hasPiece |= (1<<(4*8+5));
whatPiece |= (1<<(4*8+5));

// add a black piece @ 3x3
hasPiece |= (1<<(3*8+3));
whatPiece &= ~(1 << (3*8+3));

// remove a piece @ 1x2
hasPiece &= ~(1 << (2*8+1));

// change the color of 3x3 to white
whatPiece |= (1 << (3*8+3));

// is there a piece @ 7x2?
(hasPiece & (1 << (2*8+7))) > 0 ? true : false;

// what color is the piece @ 7x2?
(whatPiece & (1 << (2*8+7))) > 0 ? "white" : "black";


Share this post


Link to post
Share on other sites
just because, here's an example that compiles:
#include 
// g++ bitboard.cpp -o bitboard
int main()
{
	// Where this is set, there is a piece
	unsigned long hasPiece = 0;
	// Where this is set, the piece is white, if not it's black
	unsigned long whatPiece = 0;

	std::cout << "is there a piece @ 7x2? " << ((hasPiece & (1ul << ((2*8)+7))) > 0 ? "yes" : "no") << std::endl;
		
	// add a white piece @ 7x2 
	hasPiece |= (1ul << ((2*8)+7));
	whatPiece |= (1ul << ((2*8)+7));

	std::cout << "is there a piece @ 7x2? " << ((hasPiece & (1ul << ((2*8)+7))) > 0 ? "yes" : "no") << std::endl;
	std::cout << "what color is the piece @ 7x2? " << ((whatPiece & (1ul << ((2*8)+7))) > 0 ? "white" : "black") << std::endl;
	
	// change the color of 7x2 to black
	whatPiece &= ~(1ul << ((2*8)+7));
	
	std::cout << "what color is the piece @ 7x2? " << ((whatPiece & (1ul << ((2*8)+7))) > 0 ? "white" : "black") << std::endl;
	
	// remove 7x2
	hasPiece &= ~(1ul << ((2*8)+7));
	
	std::cout << "is there a piece @ 7x2? " << ((hasPiece & (1ul << ((2*8)+7))) > 0 ? "yes" : "no") << std::endl;
}

Share this post


Link to post
Share on other sites
Although ninnghazad's examples seem correct, they don't show the true power of bitboards. The magic of bitboards is apparent when you perform operations on the whole board. For example, you can generate all the moves at the same time, with a few operations for each of the 8 directions. I'll show you one as an example. The answer fits in a single bitboard too!

typedef unsigned long long u64;

/*                                                                                                                                                                                                                 
  Square numbering:                                                                                                                                                                                                
                                                                                                                                                                                                                   
  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                                                                                                                                                                                          
*/

u64 east(u64 x) {
  return (x & 0xfefefefefefefefeull) >> 1;
}

u64 east2(u64 x) {
  return (x & 0xfcfcfcfcfcfcfcfcull) >> 2;
}

u64 east4(u64 x) {
  return (x & 0xf0f0f0f0f0f0f0f0ull) >> 4;
}

u64 saturate_east(u64 x, u64 obstacles) { // http://chessprogramming.wikispaces.com/Kogge-Stone+Algorithm
  x |= east(x) & ~obstacles;
  obstacles |= east(obstacles);
  x |= east2(x) & ~obstacles;
  obstacles |= east2(obstacles);
  x |= east4(x) & ~obstacles;
  return x;
}

struct Board {
  u64 bb[2];
  int side_to_move;

  u64 generate_moves_east() const {
    u64 mine = bb[side_to_move];
    u64 enemy = bb[!side_to_move];
    u64 empty = ~(mine | enemy);
    return east(saturate_east(mine, empty) & enemy) & empty;
  }

  // ...                                                                                                                                                                                                           
};

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