Hi !
Featured games (84)
games approved by the League of Dukes
Games in Showcase (601)
Games in Android Showcase (171)
games submitted by our members
Games in WIP (649)
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 4154 times)
0 Members and 1 Guest are viewing this topic.
Offline recosfero

Junior Newbie

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

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?

Offline Jono
« Reply #1 - Posted 2010-12-11 10: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 Devvie

Medals: 2


« Reply #2 - Posted 2010-12-11 11: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 Spiffy Duke »

Medals: 554
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

« Reply #3 - Posted 2010-12-11 12: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 12: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
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

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

« Reply #5 - Posted 2010-12-11 12: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 Spiffy Duke »

Medals: 554
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

« Reply #6 - Posted 2010-12-11 13: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

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

« Reply #7 - Posted 2010-12-11 13: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-06 23: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.

"We all secretly believe we are right about everything and, by extension, we are all wrong." W. Storr, The Unpersuadables
Pages: [1]
  ignore  |  Print  
You cannot reply to this message, because it is very, very old.

Riven (23 views)
2015-07-27 16:38:00

Riven (13 views)
2015-07-27 15:35:20

Riven (18 views)
2015-07-27 12:26:13

Riven (8 views)
2015-07-27 12:23:39

BurntPizza (24 views)
2015-07-25 00:14:37

BurntPizza (36 views)
2015-07-24 22:06:39

BurntPizza (20 views)
2015-07-24 06:06:53

NoxInc (23 views)
2015-07-22 22:16:53

NoxInc (14 views)
2015-07-22 22:13:39

Jesse (35 views)
2015-07-22 03:10:36
List of Learning Resources
by gouessej
2015-07-09 11:29:36

How Do I Expand My Game?
by bashfrog
2015-06-14 11:34:43

List of Learning Resources
by PocketCrafter7
2015-05-31 05:37:30

Intersection Methods
by Roquen
2015-05-29 08:19:33

List of Learning Resources
by SilverTiger
2015-05-05 10:20:32

How to: JGO Wiki
by Mac70
2015-02-17 20:56:16

2D Dynamic Lighting
by ThePixelPony
2015-01-01 20:25:42

How do I start Java Game Development?
by gouessej
2014-12-27 19:41:21 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‑
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!