Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (579)
games submitted by our members
Games in WIP (500)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Bitboard for othello  (Read 3372 times)
0 Members and 1 Guest are viewing this topic.
Offline recosfero

Junior Newbie





« Posted 2010-12-11 01:25:42 »

Hi,
im currently working on an ai for othello/reversi im using alpha/beta search without move ordering for searching the game tree.
Currently im using an 8x8 int array as board representation. But i want to use a Bitboard to make copying the boards easier. The board will contain 2 long variables 1 for the white stones, one for te black stones.
Somehow i cant come up with an efficient way of calculating the possible moves for a given state. Of course i can check the empy fields adjacent to discs and verify if the field is valid through extending a bitmask in every direction.
But i think this is slower than the int representation.
Anyone has some good ideads?

regards
Offline Jono
« Reply #1 - Posted 2010-12-11 11:14:09 »

I wouldn't worry about the speed of calculating valid moves. The array lookups you would need with the int representation will be much, much slower that the bit shifting and masking.

I would suggest just having two methods that are implementation-specific (doing the bit manipulation for longs, array access for the ints): an isWhite(x,y) and an isBlack(x,y) method. These should get in-lined by the compiler (make them private or final) so there shouldn't be a performance hit, and the logic of the valid move checking that uses them will be implementation independent.

Another option is to keep a set of valid moves for each colour along with open states. I can't remember all the rules for Othello, but I think a child state's valid moves share a lot of the parent state's. Then when generating the child states you would only need to check the few locations on the board that have changed with the last move.
Offline Captain Awesome

Junior Member


Medals: 2


Hi


« Reply #2 - Posted 2010-12-11 12:43:31 »

Why don't you just use one 2-dimensional int array (int[][]) for the board. You can fill it with zero (empty space), one (white pieces) and two (black pieces).
That way you get the entire board in one array and you eliminate some potential bugs (like if you put a black and a white piece in the same spot)
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #3 - Posted 2010-12-11 13:41:43 »

btw should be no need to make things private or final for them to be inlined.

Cas Smiley

Offline recosfero

Junior Newbie





« Reply #4 - Posted 2010-12-11 13:49:06 »

@ jono thanks ill try that


i think the increase in performance is mostly due to faster copying of the boards and faster move generation which allows greater search depth
currently i have to manually copy all the values in one board representation into a new 2d array cause the .clone() method does not clone the array in the board representation
@captain
sry if it wasnt clear by 8x8 i was referring to a 2d-int array with length 8
 thats what im currently using although black is -1 cause its easier to get the enemy color.

Offline pjt33
« Reply #5 - Posted 2010-12-11 13:57:53 »

That way you get the entire board in one array and you eliminate some potential bugs (like if you put a black and a white piece in the same spot)
Using bitmasks you can easily pick those bugs up with assert((black & white) == 0).
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2010-12-11 14:05:41 »

You should be modelling the bitboards using 2 longs:

long white;
long black;

Then all the operations you need to do on the whole board can be done with single instructions and no array lookups, that's the whole point of bitboards.

Cas Smiley

Offline pjt33
« Reply #7 - Posted 2010-12-11 14:26:28 »

An additional thought:

You can construct an array of 64 longs giving the adjacency for each square. Then you can maintain alongside white and black a long representing positions which are adjacent to at least one piece. When someone places a piece in square x you update adjacent |= adjacency[ x ]. Then the set of possible moves can be pre-filtered to adjacency & ~(white | black).
Offline philfrei
« Reply #8 - Posted 2011-01-07 00:23:08 »

Just a thought--maybe you can optimize how you access the array, or optimize by using something other than an array? For example, iterating and inspecting via a "for each" loop can be quicker than incrementing an index repeatedly into an array. And certain structures iterate faster than others.

Also, is it absolutely necessary to make and inspect a full copy of the board to derive the possible plays list? Perhaps a single structure would suffice for directing this function, with the occupied squares being flagged, and removed from a list of available squares, as they are consumed. For example, remove a play from a list of possible plays (and store it in a Stack that coordinates with the alpha/beta tree), and use this list rather than generating a new list of available plays from scratch on each iteration.

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (37 views)
2014-04-15 18:08:23

BurntPizza (33 views)
2014-04-15 03:46:01

UprightPath (49 views)
2014-04-14 17:39:50

UprightPath (31 views)
2014-04-14 17:35:47

Porlus (48 views)
2014-04-14 15:48:38

tom_mai78101 (69 views)
2014-04-10 04:04:31

BurntPizza (129 views)
2014-04-08 23:06:04

tom_mai78101 (229 views)
2014-04-05 13:34:39

trollwarrior1 (193 views)
2014-04-04 12:06:45

CJLetsGame (200 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!