Thread: Othello program

  1. #1
    Registered User
    Join Date
    Dec 2011
    Posts
    7

    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)

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User ledow's Avatar
    Join Date
    Dec 2011
    Posts
    435
    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.

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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...

  5. #5
    Registered User ledow's Avatar
    Join Date
    Dec 2011
    Posts
    435
    Quote Originally Posted by CommonTater View Post
    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.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

  7. #7
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    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.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!
    Last edited by Adak; 12-14-2011 at 07:03 PM.

  9. #9
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    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.

  10. #10
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    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

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You're preaching to the choir! Go!, He's glad to explain how his "learning" works in Crafty.

  12. #12
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    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 ?

  13. #13
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    Definitely I'll do it. thank you very much!

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

  15. #15
    Registered User
    Join Date
    Dec 2011
    Posts
    7
    Quote Originally Posted by Adak View Post
    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?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Cannot find Bug in my Othello program.
    By goat37 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2011, 10:05 PM
  2. Othello procedure
    By Morrow in forum Game Programming
    Replies: 7
    Last Post: 10-05-2004, 05:29 AM
  3. Help on writing a othello program
    By alice in forum C Programming
    Replies: 4
    Last Post: 03-16-2004, 09:18 AM
  4. othello AI
    By laasunde in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 11-02-2003, 02:37 PM
  5. Reversi / Othello
    By dericosp in forum C Programming
    Replies: 6
    Last Post: 06-11-2002, 05:35 PM

Tags for this Thread