I'm thinking about a fast Othello moves generator since several years, and it seems that the Pentium could help.

Every cell could be stored into 2 bits, as we have 64 cells on the board, we get 128 bits, and this could be stored into registers.

One routine per cell seems the faster way to do this.

Let's take the following case (monodimensional Othello):

.xxxxo

. is empty square
x is 'x' player
o is 'o' player

'o' to play, how can we implement the move generator efficiently in this case using MMX ?

JC
Posted on 2002-09-21 15:23:40 by MCoder
I think you'd be better off not dealing with the whole board at a time, but rather with lines, be they rows, columns or diagonal.

Use your storage method, each full 8 cell line would take 16bits. At that rate you could implement a lookup table of the best move for that paticular line.

Then a method of summing those best moves or otherwise to see overall which move is the best for a given board layout, not to hard in theory at least :grin: .
Posted on 2002-09-21 18:28:44 by Eóin
As MMX is for math and byte packing, it is not going to perform miracles for you when calculating moves, because there is no mathematical equation that specifies the best move.

What you have to do is:
- iterate through each cell that the player can "move" to
- generate a new "board" with that cell filled in with the player's color, and all the affected tiles flipped to that player's color
- based on how successful that move is for the player, allocate a number of points to that move
- once all moves have been allocated, execute the move with the highest points value
- if you have several moves worth the same number of points, then randomly select one of those moves

When you have your move rating logic sorted out satisfactorily, then you could start introducing negative points for negativity in a move, i.e. you might allocate a move 5 points because it causes 5 of the oponents tiles to be flipped, but you might then minus 3 points from that because the oponent may be able to get most of those tiles back in their next move.

And when you get really keen, you might want to introduce some "look-ahead", which is where for each move, you take the temporarily generated board and calculate the next couple of moves, with all the points being awarded back to that original move. As you increase the size of your look-ahead, you get closer and closer to calculating the absolute best possible move each time.
Posted on 2002-09-23 00:07:02 by sluggy
Hi everybody.

I work on the fastest Othello move generator, I think .

The pb with Othello evaluation : change a line, it changes many other entities. A single square difference may give you a +/-30 score. So the pb cannot be solved with a +/- n points per change. The very best is pattern evaluation, this revolution brought by Michael BURO's Logistello.

In spite of many (theoretical) tries I gave up working on 38 lines (8 lines/8 cols/11+11 diagonals) because of the overhead when transforming a single entity : you have to update many others.

Still, from the beginning I work on MMX. Here is a version I currently use, it can be improved and I will do it as soon as possible with my brand-new ideas. You have so many tricks with MMX. This endgame solver version is for PIII or more, because of PMOVMSKB for instance.

I also have a countmobility function from Richard D., <200 opcodes, I am currently improving it.

I *really* enjoy talking about this matter :)

Regards
Posted on 2002-09-23 05:51:43 by valy
valy,
did you intend for there to be an attachment with your post??
Posted on 2002-09-23 06:53:59 by sluggy
Sorry I attached the file, I made a preview... I made a back in IE6... I posted. What was wrong ?!

Anyway I was, and here it is (?!)
Posted on 2002-09-23 08:11:06 by valy
I have never found a computerized version of Othello/Reversi that played intelligently. Ranking moves based upon the number of chips/tiles reversed is a big mistake.

The key to a competitive strategy is to play for the corners of the board. Control the corners and you will win every time.

Generating a hueristic that plays for the corners is an interesting challenge. Wish I was young enough to have time for it...
Posted on 2002-09-30 20:13:48 by Berninhell
The key to a competitive strategy is to play for the corners of the board. Control the corners and you will win every time.
Which is why you allocate more points to a move the closer it gets in position to the corners. How many of the opponents chips are flipped is only a part of the evaluation.
Posted on 2002-10-01 02:49:08 by sluggy
A real hueristic would be a bit more complicated than that.

Edge play is critical for forcing your opponent into yielding the corners and it is not based upon proximity to the corners.
Posted on 2002-10-01 08:26:22 by Berninhell
Hi,

I do have seen a good Othello game on pocket pc. It does try to gain the corners, however i still managed to beat it.(It's on my friend's pockeet pc)
Posted on 2002-10-01 09:28:30 by roticv
A real hueristic would be a bit more complicated than that.

Edge play is critical for forcing your opponent into yielding the corners and it is not based upon proximity to the corners.
I agree, in my explanation i do make it sound like a simple operation when it isn't really.

I can almost sense a western-style shoot-out here :) Your moves generator can meet my moves generator at high noon, may the best generator win :)

I think we could each code a plugin move generator for MCoder (the guy who started his thread). It could be in the form a a dll, he calls a function with some data representing the state of play, and the generator would return the coordinate of the recommended move. And obviously this would have to be done as time permits :)
Posted on 2002-10-01 20:59:41 by sluggy
I'm smelling a competition...
...oh, damn! It is me - I need to take a shower. :grin:
Posted on 2002-10-01 21:15:48 by bitRAKE
A really OLD (Atari 8-bit!) implementation made a table that IIRC was like the following:




15 -1 08 06 06 08 -1 15
-1 -1 00 02 02 00 -1 -1
08 00 06 04 04 06 00 08
06 02 04 00 00 04 02 06
06 02 04 00 00 04 02 06
08 00 06 04 04 06 00 08
-1 -1 00 02 02 00 -1 -1
15 -1 08 06 06 08 -1 15



(This is kinda off the top of my head BTW...)

Each is a position on the board. A higher number means a better location, so the computer would look for the 'best' location to get by summing the locations that would be gotten by a move. I used this table for years (as a human being...) and played a hard game of Othello.

Examining the table... to get a side position is good, to get a corner is better, but to get a piece near a good place is very very bad because you could potentially give that position to your opponent.

Also... trying to get most pieces per move is really weak strategy.

The guy who made the above table also made the program modify it during the game depending on various game conditions... don't remember how the program modified it though...


Corrected error in table alignment...
Posted on 2002-10-02 02:07:45 by AmkG
Wow ! I'm impressed by Abyss32.
I'm quite busy with other things right now, but I'll surely take a close look soon.

BTW, forget about mobility and lame values of the cells !
One of the best french programs used an interesting auto-evaluation routine.
It simply used a database of games (you can download Thor, which contains all official games since 20 years !), and computed the perfect finals of all games upto move 50, meaning that it had to do an alpha-beta of depth 10.
This gave him an absolute note, like -8 or +10.
Then he correlated all his heuristics with this note.
With 6000 random games, his program had an impressive auto-evaluated notation of positions !

I'd be glad to see how fast you can go with 64Mb+ RAM and huge lookup tables.

JC
Posted on 2002-10-02 16:59:27 by MCoder