Othello program

I'm writing an othello engine. What I need now is to create an endgame repository. my program is able to play a perfect game when there are 24 plies left and I want my program to store the position and its payoff so it can be fetched for future reference. I think this will make my program stronger and will prevent it to be defeated twice the same way.

What I need is a very basic implementation of an indexed record file that allows to quickly retrieve and store positions. No deletions required. Can anybody please refer to a source for this or share your thoughts on this approach. (that includes how to store positions)

Actually no, what you need is a good minimax implementation, ideally with alpha and beta pruning.

Then you'll have a good AI for it.

Othello isn't hard to program, to be honest, and it can be quite easy to beat most humans at it because its complexity is quite low compared to, say, Chess or Go. The complexity is about 10^28 last time I looked, compared to 10^50-something for chess and 10^100-something for Go.

If you did want to cache every possible end-game then I'd advise you to look into data storage requirements first. If you have 24 plays left, that suggests 24 gaps on the board, which suggests 24 * 23 * 22 * 21 *.... * 2 * 1 possible moves (at most) which is about: 51,090,942,171,709,440,000 possibilities. Of course, most of those will be illegal but even if you assumed 1% of them were legal, you'd still have an awfully large number of positions on the board left after you apply the games rules. Multiply that by the storage size of each move and you can come up with quite a hefty lookup in order to find the "perfect" ending for any one particular board position and huge memory requirements. This is where algorithms beat the caching of their results. Also, it would have to pre-calculate, or have experienced, most of those endings to actually make itself useful.

If you *did* insist on going that way, you'd need what you'd need for any similar task - a way of recording the board position uniquely as a string of some data, and a way to store and retrieve huge numbers of those data strings efficiently. Hash trees, etc. might be worth a read up on.

But my advice? Look at what you could potentially be storing on your average PC and just how much that information is going to be worth to you at runtime.

The smarter way is to develop a hidden board that contains square values... corners being the most important, ouside rows being second, etc. You then evaluate and adjust these values as you play and make the highest valued move that is available.

Owning all 4 corners pretty much guarantees ownership of the outside rows... if you have the entire outside row of the board, the best your opponent can manage is a tie.

It's pretty hard to beat...

Originally Posted by CommonTater

The smarter way is to develop a hidden board that contains square values... corners being the most important, ouside rows being second, etc. You then evaluate and adjust these values as you play and make the highest valued move that is available.

Owning all 4 corners pretty much guarantees ownership of the outside rows... if you have the entire outside row of the board, the best your opponent can manage is a tie.

It's pretty hard to beat...

I did almost exactly that in Visual Basic nearly 15 years ago now for a school project. I still have the program around somewhere (http://www.ledow.org.uk/Files/Othello.zip! Still requires VBRUN300.DLL!). I can tell you that it's far too simple to beat for anyone who's played Reversi more than casually. Heuristics based on position / number of captures / etc. like that don't work well for non-amateur Reversi play.

(Now that I recall, I re-wrote that same program in TI-85 Basic too!)

Reversi has a complexity too high for such simple heuristics.

Alpha -beta version of minimax is good for the play over the board, but as you near the end game, you can strengthen your programs play by using an end game tablebase.

These EGTB's are built up via retrograde analysis, and once your program has reached, or can analyze ahead to reach, their horizon, they offer perfect play.

The experts to talk to, are here:

www.talkchess.com

Sign up - it's free. This is the forum for arguing about chess clone software - no, actually it's the chess programmers forum, and several of the regulars there have programmed End Game Table Bases, for their program's use.

Oddly enough, it was a former Reversi programmer who stood chess programming on it's head for the last 5 years, by posting up code for his strong chess program "Fruit". Whatever you do, don't comment on anything about clone programs -- it's a very touchy subject!

They can show you how the EGTB's can be designed, use compression and de-compression on the fly, if you want to, etc. Go into the "programming and technical" sub-forum.

Have fun! You will learn a bunch!

If you did want to cache every possible end-game then I'd advise you to look into data storage requirements first. If you have 24 plays left, that suggests 24 gaps on the board, which suggests 24 * 23 * 22 * 21 *.... * 2 * 1 possible moves (at most) which is about: 51,090,942,171,709,440,000 possibilities. Of course, most of those will be illegal but even if you assumed 1% of them were legal, you'd still have an awfully large number of positions on the board left after you apply the games rules. Multiply that by the storage size of each move and you can come up with quite a hefty lookup in order to find the "perfect" ending for any one particular board position and huge memory requirements. This is where algorithms beat the caching of their results. Also, it would have to pre-calculate, or have experienced, most of those endings to actually make itself useful.

If you *did* insist on going that way, you'd need what you'd need for any similar task - a way of recording the board position uniquely as a string of some data, and a way to store and retrieve huge numbers of those data strings efficiently. Hash trees, etc. might be worth a read up on.

But my advice? Look at what you could potentially be storing on your average PC and just how much that information is going to be worth to you at runtime.

Let me get some spin control at this point. My program does use minimax with alpha-beta pruning. It implements heuristics as any other othello engine would.

Let's suppose I challenge my program against some other X Program. on move 36, my program is able to know the exact outcome of the position it is playing. It'll store it and the game will continue till it finishes.

assume X wins for a moment.

Now my program will go for a revenge against X. X will make the same moves as long as my program replies the same moves it did before, but there will be a point, let's say, on move 28, during its search it will figure out that the heuristical payoff given to that position on move 36 can be corrected with an objective final value, thus altering program's evaluation and making it choose some other move instead.

This approach I think could be useful for match tournaments.
Theoretically my program having this feature should win most of the times against my same program without this capability.

Hyatt's well known open source program Crafty, has a feature you may want to talk with Bob about. He implemented it because he got tired of seeing some players on the chess servers, beat his program over and over, with the same sequence of moves, to lift their rating, as well as at tournaments.

Hyatt is one of the team of programmers responsible for "Cray Blitz", which was the chess computer world champion, back in the days. He's now a prof at U.Alabama. He really knows his stuff!

Congrats on your program, it sounds like a good one!

The smarter way is to develop a hidden board that contains square values... corners being the most important, ouside rows being second, etc. You then evaluate and adjust these values as you play and make the highest valued move that is available.

Owning all 4 corners pretty much guarantees ownership of the outside rows... if you have the entire outside row of the board, the best your opponent can manage is a tie.

It's pretty hard to beat...

This works if an only if the stones you get at the edges of the board are stable, i.e.: cannot be flipped by the opponent. If you implement an heuristic like this, you coul do something like:

for a corner, get 100 points
for the edgesquare next to a corner you control, 10 plus points,
for the next edgesquare next to the above, 100 points.
for the fourth.. 10^4 and so forth

if you control a full edge, double the above. (evaluation from corner A to B, and evaluation from corner B to A)

this prevents the heuristic from considering edgestones good by default. thus making way the edgestones are arranged matter.

Hyatt's well known open source program Crafty, has a feature you may want to talk with Bob about. He implemented it because he got tired of seeing some players on the chess servers, beat his program over and over, with the same sequence of moves, to lift their rating, as well as at tournaments.

Hyatt is one of the team of programmers responsible for "Cray Blitz", which was the chess computer world champion, back in the days. He's now a prof at U.Alabama. He really knows his stuff!

Congrats on your program, it sounds like a good one!

What a try to implement by doing this is to resemble something that expert chessplayers use quite oftenly, their memory, their learnings coming from their own experience, the knowledge they gathered after years of play. No chessplayer relies on their sole talent and strngth to beat an opponent

You're preaching to the choir! Go!, He's glad to explain how his "learning" works in Crafty.

There should be a retrieval data structure that allows quick retrieval of a given position. Depending upon the time it takes to lookup, I would adjust my program on when to use it so that performance does not get compromised significantly. I'm thinking of storing positions using bitmaps. this allows to compare boards faster than using strings.

something like

Code:

struct board {
       unsigned long white[2];
       unsigned long black[2];
};

Is there any file with indexing/hash whatsoever that could be useful, if not, any tips to implement ?

Definitely I'll do it. thank you very much!

There are a few different ways that EGTB's are handled in chess. These programs all have their own way of doing it:

The King (Chessmaster's engine)
Crafty and most others - use Nalimov's EGTB
Gaviota
Robbolito // this is a clone, so I wouldn't mention it

AFAIK, they all use bit boards. Crafty makes extensive use of bitboards. Robert Hyatt definitely grok's bitboards!

Originally Posted by Adak

There are a few different ways that EGTB's are handled in chess. These programs all have their own way of doing it:

The King (Chessmaster's engine)
Crafty and most others - use Nalimov's EGTB
Gaviota
Robbolito // this is a clone, so I wouldn't mention it

AFAIK, they all use bit boards. Crafty makes extensive use of bitboards. Robert Hyatt definitely grok's bitboards!

I could see how quick Nalimov's EGTB's work. I'm thinking of kinda B* tree implementation to search positions. What do you think?