Bitboards... Again... (reversi)

Zacariaz · Post by **Zacariaz** » Mon Feb 21, 2011 4:52 pm

Yes I know, I just won't shut up

As I may have hinted in another thread, I've kinda given up on the chess project as it's too difficult for me at this moment, so I thought that I'd take step back to something seemingly simpler that is still an interesting challenge.

Reversi or Othello, I'm not really sure which is the proper name, seemed like the obvious choice, so I've been doing some thinking with that as a starting point.

The first consideration was how many boards I'd need. Obviously I'd need at least two, one for each colour, or it wouldn't make much sense at all to take the bitboard approach, however it seemed like a good idea to have boards describing the possible "moves" for each side, so that's more or less where I'm at with these considerations. Rotated boards will probably be introduced at a later time, but for now I don't' think it is necessary to take them in to consideration.

Then I've been thinking long and hard about how to derive those possible "moves" and it's here that I'm struggling and I've been unable to determine what the "normal" approach to the problem is. There are material worth reading on the net, but I've yet to find anything which helps me much in this area.

My first approach went something like this.

In order for a legal move to be legal, at least one adjacent position must hold a piece of the opposite colour, so it seemed a reasonable approach to mask out all the adjacent positions of the opposite coloured pieces to isolate them. Then of course I need to mask out those position which are already occupied.

So far only one issue, which I'll get back to later, had come to mind. The thing is though, if we take the initial state of the game as an example, we now have ten possible moves out of which only four are legal and I see no smart way to mask out the last two. Every solution I come up with can of course work, but the obvious lag of efficiency leads me to the conclusion that, if this is indeed the solution, I might as well not use bitboards at all as just about any alternative will most certainly work better. I won't be getting in to more details about the "solutions" I've come up with as even I can see that they're not worth discussion further.

So, after crying my self to sleep, I woke up and thought about a possible alternative approach, but I find it kinda hard to wrap my head around it.

Suppose that instead of generating these legal moves from the state of the game, then we initialize them from the start, like we'd initialise the two main boards with the initial game state. Then every time a move is made, you "simply" maintain these boards. That is, when black places a piece in position x, not only do we check which consequences it will have and which pieces to be flippedand thus altering the game state, but also check which alterations will have to be made to the "legal moves" boards. Obviously the newly occupied position will have to be masked out, possible new legal positions will have to be added adjacent to the newly occupied position, newly flipped pieces that may have an impact on the legal moves will have to be checked up against the "legal moves" boards and the legal moves that are affected will then have to be rechecked up against the state of the game to determine if they are in fact still legal. It seems a lot more complicated and yet it seems like a more proper way of doing things.

I do hope that I've been able to explain my self here. It haven't been easy and if nothing seems to make sense, I won't be too surprised.

A more simple, though almost as annoying, matter, is all about isolation one or more positions in a bitboard. as always I have trouble explaining so an example may be in order and for the sake of simplicity lets use a 16 bit board.

Code: Select all

UINT16 board = 0001001010000010b;

for(int n = 0; n < 16; n++)
    if(board & (1<<n))
        print n;

The above "pseudo" code should I think, print out 1, 7, 9, 12, which is useful information, however considering not only that we are working with 64 bit boards but also that this routine may very likely be used quite a lot, though of course not with the purpose of printing out the positions It seems rather processor intensive and I can't help but to wonder if there is something very important I've missed here. From a mathematically point of view it's rather easy to get an upper limit, as to say that the number 16 in the for loop in the example would instead be 13. I'm a bit rusty in this area, but I should this that the answer is something like log(board)/log(2), ceiled or floored depending on the implementation. I'm not sure about how the log() actually work in programming terms, so this particular solution may not be wise, though the principle should work. If then I could just figure out a way to determine a lower limit, a lot could probably be saved by it, but I haven't been able too.

Anyway, I got a bit sidetracked there.

In the end I'm just curious as to your opinions, suggestions, advice and so on and so forth.

As always I don't mean to be a bother, but this is really the only place that I know of where I can find people worth questioning about these sorts of things.

So thanks in advance and best regards.