othello data structures etc.

dans l'article 1127397837.482509.268890 DeleteThis @g47g2000cwa.googlegroups.com,
bob DeleteThis @coolgroups.com à bob DeleteThis @coolgroups.com a écrit le 22/09/05 16:03 :

> I was just wondering if you guys know what data structures and
> functions are best for an Othello game. Right now, I'm just using an
> array of 64 chars.
>
> Also, my functions for enumerating moves and what not probably are
> quite suboptimal. If anyone has any insights regarding this sort of
> thing, I'd love to hear about them.
>
> Thanks.
>

The best entry point :

http://perso.club-internet.fr/abulmo/resources/solver/doc/index.html

And after a list of interesting points

http://perso.wanadoo.fr/othello/english/Concepts/Resources.html

Good coding
--
Bruno Causse
http://perso.wanadoo.fr/othello
 >> Stay informed about: othello data structures etc. 

I think I set things up as a 10x10 array of bytes or ints (I'm thinking I
used ints since my program is in Java and for some reason java copies ints
faster...I think.)

As far as legal moves are concerned, you want to try to update that from
turn to turn. What I do is keep a list of positions that are adjacent to
black (white) pieces and update the list after each turn. Not all the moves
in the list are legal but they dramatically reduce the possible moves you
need to check. The lists are also useful since their size gives a mobility
measure which can be incorporated into the board evaluation. The updating of
the list is done inside the "doMove(Position p)" which also updates various
other things including piece counts of each color and such.

Here's an Othello Java applet I wrote a few years ago:
http://www.stat.ucla.edu/~jasonl/reversi/Reversi.html. The level of play is
limited by the small number of board features that I am using (~16) but
weights assigned to these features were obtained using self-play and
logistic regression so it still manages to play a pretty decent game.


<bob RemoveThis @coolgroups.com> wrote in message
news:1127397837.482509.268890@g47g2000cwa.googlegroups.com...
>I was just wondering if you guys know what data structures and
> functions are best for an Othello game. Right now, I'm just using an
> array of 64 chars.
>
> Also, my functions for enumerating moves and what not probably are
> quite suboptimal. If anyone has any insights regarding this sort of
> thing, I'd love to hear about them.
>
> Thanks.
>
 >> Stay informed about: othello data structures etc. 

It tried your game, and it's not bad. What's that stuff about 10
Perfect?

Jason Lenderman wrote:
> I think I set things up as a 10x10 array of bytes or ints (I'm thinking I
> used ints since my program is in Java and for some reason java copies ints
> faster...I think.)
>
> As far as legal moves are concerned, you want to try to update that from
> turn to turn. What I do is keep a list of positions that are adjacent to
> black (white) pieces and update the list after each turn. Not all the moves
> in the list are legal but they dramatically reduce the possible moves you
> need to check. The lists are also useful since their size gives a mobility
> measure which can be incorporated into the board evaluation. The updating of
> the list is done inside the "doMove(Position p)" which also updates various
> other things including piece counts of each color and such.
>
> Here's an Othello Java applet I wrote a few years ago:
> http://www.stat.ucla.edu/~jasonl/reversi/Reversi.html. The level of play is
> limited by the small number of board features that I am using (~16) but
> weights assigned to these features were obtained using self-play and
> logistic regression so it still manages to play a pretty decent game.
>
>
> <bob.DeleteThis@coolgroups.com> wrote in message
> news:1127397837.482509.268890@g47g2000cwa.googlegroups.com...
> >I was just wondering if you guys know what data structures and
> > functions are best for an Othello game. Right now, I'm just using an
> > array of 64 chars.
> >
> > Also, my functions for enumerating moves and what not probably are
> > quite suboptimal. If anyone has any insights regarding this sort of
> > thing, I'd love to hear about them.
> >
> > Thanks.
> >
 >> Stay informed about: othello data structures etc. 

That means that the last 10 moves of the game are played perfectly. Most
"professional" would games would probably do this automatically but I
wanted to make it explicit to see its impact. Also, unlike most
"professional" games, I don't try to optimize the final piece count, i.e. it
makes no difference to the program whether it wins by 2 pieces or 30
pieces - it just tries to win. I actually wrote the game mostly to get more
familiar with Java so a lot of the classes/methods that I use are probably
not the most efficient for this particular application.


<bob.RemoveThis@coolgroups.com> wrote in message
news:1127438404.998771.56790@f14g2000cwb.googlegroups.com...
> It tried your game, and it's not bad. What's that stuff about 10
> Perfect?
>
> Jason Lenderman wrote:
>> I think I set things up as a 10x10 array of bytes or ints (I'm thinking I
>> used ints since my program is in Java and for some reason java copies
>> ints
>> faster...I think.)
>>
>> As far as legal moves are concerned, you want to try to update that from
>> turn to turn. What I do is keep a list of positions that are adjacent to
>> black (white) pieces and update the list after each turn. Not all the
>> moves
>> in the list are legal but they dramatically reduce the possible moves you
>> need to check. The lists are also useful since their size gives a
>> mobility
>> measure which can be incorporated into the board evaluation. The updating
>> of
>> the list is done inside the "doMove(Position p)" which also updates
>> various
>> other things including piece counts of each color and such.
>>
>> Here's an Othello Java applet I wrote a few years ago:
>> http://www.stat.ucla.edu/~jasonl/reversi/Reversi.html. The level of play
>> is
>> limited by the small number of board features that I am using (~16) but
>> weights assigned to these features were obtained using self-play and
>> logistic regression so it still manages to play a pretty decent game.
>>
>>
>> <bob.RemoveThis@coolgroups.com> wrote in message
>> news:1127397837.482509.268890@g47g2000cwa.googlegroups.com...
>> >I was just wondering if you guys know what data structures and
>> > functions are best for an Othello game. Right now, I'm just using an
>> > array of 64 chars.
>> >
>> > Also, my functions for enumerating moves and what not probably are
>> > quite suboptimal. If anyone has any insights regarding this sort of
>> > thing, I'd love to hear about them.
>> >
>> > Thanks.
>> >
>
 >> Stay informed about: othello data structures etc. 

bob DeleteThis @coolgroups.com a écrit :
> I was just wondering if you guys know what data structures and
> functions are best for an Othello game. Right now, I'm just using an
> array of 64 chars.

The other alternative is to use bitboards. Personnally, I do not think
there is a huge difference in performance, particularly on 32-bit systems.

> Also, my functions for enumerating moves and what not probably are
> quite suboptimal. If anyone has any insights regarding this sort of
> thing, I'd love to hear about them.

The main trick is to avoid useless code to be executed. For example, if
you want to move in A1 (the upper-left square), it is a waste of time to
check if you can flip the inexistant upper discs, or the inexistant left
discs, etc.

--
Richard
 >> Stay informed about: othello data structures etc. 

Matthew Hills a écrit :

> You can get info on othello programs at:
> http://satirist.org/learn-game/systems/othello/

This site is outdated and most of the links are dead.

The top programs now are:

Saio: http://www.romanobenedetto.it/Saio.htm
ntest: http://www.btinternet.com/~chris.welty/Ntest/index.htm
Logistello: http://www.cs.ualberta.ca/~mburo/log.html
Zebra: http://www.radagast.se/othello/
Herakles: http://www.herakles.tournavitis.de/
Edax: http://abulmo.club.fr/edax/index.htm
etc.

The Internet Othello Server does not exist anymore, and has been
replaced by GGS (Generic Game Server):
telnet://opal.cs.ualberta.ca:5000

Of course, Michael Buro's papers are still worth reading:
http://www.cs.ualberta.ca/~mburo/publications.html

> There are also some interesting papers on othello in the literature.
> I'd recommend reading the dissertation on Keyano for a survey of the
> field.

Only the part about parallel programming is interesting.

--
Richard
 >> Stay informed about: othello data structures etc. 

Hi Richard,

May I ask how what sort of search depth you are using in Ajax at the
"expert" and "master" levels? Very nice program by the way.


"Richard Delorme" <abulmo.DeleteThis@nospam.fr> wrote in message
news:4333cf23$0$301$7a628cd7@news.club-internet.fr...
> Matthew Hills a écrit :
>
>> You can get info on othello programs at:
>> http://satirist.org/learn-game/systems/othello/
>
> This site is outdated and most of the links are dead.
>
> The top programs now are:
>
> Saio: http://www.romanobenedetto.it/Saio.htm
> ntest: http://www.btinternet.com/~chris.welty/Ntest/index.htm
> Logistello: http://www.cs.ualberta.ca/~mburo/log.html
> Zebra: http://www.radagast.se/othello/
> Herakles: http://www.herakles.tournavitis.de/
> Edax: http://abulmo.club.fr/edax/index.htm
> etc.
>
> The Internet Othello Server does not exist anymore, and has been replaced
> by GGS (Generic Game Server):
> telnet://opal.cs.ualberta.ca:5000
>
> Of course, Michael Buro's papers are still worth reading:
> http://www.cs.ualberta.ca/~mburo/publications.html
>
>> There are also some interesting papers on othello in the literature.
>> I'd recommend reading the dissertation on Keyano for a survey of the
>> field.
>
> Only the part about parallel programming is interesting.
>
> --
> Richard
 >> Stay informed about: othello data structures etc. 

Jason Lenderman a écrit :
> Hi Richard,
>
> May I ask how what sort of search depth you are using in Ajax at the
> "expert" and "master" levels?

dummy: 0 ply (random player).
beginner: 2 plies in midgame, 4 in endgame.
amateur: 4 plies in midgame, 8 in endgame.
expert: 6 plies in midgame, 12 in endgame.
master: 8 plies in midgame, 16 in endgame.

> Very nice program by the way.

Thank you

--
Richard
 >> Stay informed about: othello data structures etc. 

By a ply, am I correct in assuming you mean two moves (i.e. one move for
each player)? If so, it seems you are getting some very deep searches
considering the how qukcly the program responds (with the pause turned off.)
I played the othello program I wrote a few years back against Ajax and was
able to beat it 33-31 at the "expert level" with my program set to a 6 move
look ahead (I guess that would correspond to 3 plies) and last 10 moves
(i.e. last 5 plies) perfect. But it lost badly to your program at the
"master" level. You know, I always thought the weakness of my program was
the static board evaluation since it only uses 16 board features (the usual
basic position features, mobility measure and piece count) but am now
thinking that my searches are just far too shallow.

How do you get such fast searches? And how do you make the damn pointer
change to an hourglass in Java when the computer is thinking?


"Richard Delorme" <abulmo DeleteThis @nospam.fr> wrote in message
news:43342975$0$304$7a628cd7@news.club-internet.fr...
> Jason Lenderman a écrit :
>> Hi Richard,
>>
>> May I ask how what sort of search depth you are using in Ajax at the
>> "expert" and "master" levels?
>
> dummy: 0 ply (random player).
> beginner: 2 plies in midgame, 4 in endgame.
> amateur: 4 plies in midgame, 8 in endgame.
> expert: 6 plies in midgame, 12 in endgame.
> master: 8 plies in midgame, 16 in endgame.
>
> > Very nice program by the way.
>
> Thank you
>
> --
> Richard
 >> Stay informed about: othello data structures etc. 

So, what is the point of calling a half-move a ply? I can't imagine
what a half-move even is.
 >> Stay informed about: othello data structures etc. 

Jason Lenderman a écrit :
> By a ply, am I correct in assuming you mean two moves (i.e. one move for
> each player)?

No. In Chess jargon, 1 move = 2 plies = 2 half-moves. This is why I used
the word "ply" instead of "move", as I supposed it less ambiguous.

> If so, it seems you are getting some very deep searches
> considering the how qukcly the program responds (with the pause turned off.)
> I played the othello program I wrote a few years back against Ajax and was
> able to beat it 33-31 at the "expert level" with my program set to a 6 move
> look ahead (I guess that would correspond to 3 plies) and last 10 moves
> (i.e. last 5 plies) perfect. But it lost badly to your program at the
> "master" level. You know, I always thought the weakness of my program was
> the static board evaluation since it only uses 16 board features (the usual
> basic position features, mobility measure and piece count) but am now
> thinking that my searches are just far too shallow.
>
> How do you get such fast searches?

Now, that I have explained what I meant by "ply", Ajax may not look that
fast -- Bruno Causse's Cyrano applet is much faster. There is nothing
extra-ordinary in Ajax. Just a descent but perfectible implementation of
well known algorithms (PVS, iterative-deepening, aspiration window,
hashtable, move sorting, etc). Ajax's static board evaluation (Mobility,
Stability, etc.) is also quite slow to compute.
BTW, Ajax thought details (score, principal variation, search depth,
search speed, etc.) are visible in the Java console window.

> And how do you make the damn pointer
> change to an hourglass in Java when the computer is thinking?

Canvas canvas;
// ...
canvas.setCursor(Cursor.getPredefinedCursor(Cursor.WAIT_CURSOR));


--
Richard
 >> Stay informed about: othello data structures etc. 

Thanks for the explantion Richard. Now that I understand what "ply" means
(somewhat unintuitive) I am going back to my earlier view that my static
board evaluation needs more work.

Thanks for the Java cursor tip!

"Richard Delorme" <abulmo.TakeThisOut@nospam.fr> wrote in message
news:43348c87$0$303$7a628cd7@news.club-internet.fr...
> Jason Lenderman a écrit :
>> By a ply, am I correct in assuming you mean two moves (i.e. one move for
>> each player)?
>
> No. In Chess jargon, 1 move = 2 plies = 2 half-moves. This is why I used
> the word "ply" instead of "move", as I supposed it less ambiguous.
>
>> If so, it seems you are getting some very deep searches considering the
>> how qukcly the program responds (with the pause turned off.) I played the
>> othello program I wrote a few years back against Ajax and was able to
>> beat it 33-31 at the "expert level" with my program set to a 6 move look
>> ahead (I guess that would correspond to 3 plies) and last 10 moves (i.e.
>> last 5 plies) perfect. But it lost badly to your program at the "master"
>> level. You know, I always thought the weakness of my program was the
>> static board evaluation since it only uses 16 board features (the usual
>> basic position features, mobility measure and piece count) but am now
>> thinking that my searches are just far too shallow.
>>
>> How do you get such fast searches?
>
> Now, that I have explained what I meant by "ply", Ajax may not look that
> fast -- Bruno Causse's Cyrano applet is much faster. There is nothing
> extra-ordinary in Ajax. Just a descent but perfectible implementation of
> well known algorithms (PVS, iterative-deepening, aspiration window,
> hashtable, move sorting, etc). Ajax's static board evaluation (Mobility,
> Stability, etc.) is also quite slow to compute.
> BTW, Ajax thought details (score, principal variation, search depth,
> search speed, etc.) are visible in the Java console window.
>
>> And how do you make the damn pointer change to an hourglass in Java when
>> the computer is thinking?
>
> Canvas canvas;
> // ...
> canvas.setCursor(Cursor.getPredefinedCursor(Cursor.WAIT_CURSOR));
>
>
> --
> Richard
 >> Stay informed about: othello data structures etc. 

bob RemoveThis @coolgroups.com a écrit :
> So, what is the point of calling a half-move a ply? I can't imagine
> what a half-move even is.

It is chess jargon. In chess a game is written like this :

1.e4 d6
2.d4 g6
3.Nc3 Bg7
4.Bc4 c6
5.Qf3 d5
6.exd5 Nf6
7.Bg5 O-O
8.Bxf6 exf6
9.Nge2 b5
10.Bb3 b4
11.Na4 Ba6
12.O-O-O Bb5
13.h4 Qa5
....

A white movement and the black reply shares the same move number. So, a
"move" (1.e4 d6) , in chess, includes a white (1.e4) "ply" and a black
(1... d6) "ply". "half-move" is a synonymous of ply.

--
Richard
 >> Stay informed about: othello data structures etc.