I was wondering, how good are the current best reversi playing programs compared to the best human players? We know that chess playing programs are at least as good or better than the best human players (deep blue) and we know that Go playing programs are not yet as good as the best Go players - so what about reversi?

I play a program called WinThello on my computer (http://www.spee.nl/othello/). It claims to be one of the strongest on the internet. I can beat it on standard mode about 50% of the time, occasionally I beat it on Expert and I once beat it on Master. I'm wondering how the best human players would do against it.

Peter

Try Zebra. It's a good program. I'm sure there are others out there with more knowledge about this than me, but I think that the best computer programs are as good as or better than the best humans. In fact, I think computer programs will be able to play perfect within not many years. Today, they play perfect after around 10 moves, I think.

Yes, Peter, try zebra (http://www.radagast.se/othello/). It might not be as much fun to play against as wintello, though :-)

Humans don't stand a chance against a computer program. There are even java applets that know how to play othello well! (http://perso.wanadoo.fr/othello/english/index.html).

Marius is right. There are lots of programs out there with “Master” and “Champion” levels that are actually quite bad. WZebra is the strongest freeware program, and on the higher levels it is far superior to humans. In fact, you can feed it a transcript between two strong human players, and in a few minutes it will tell you exactly where they made their mistakes. It can find perfect play from around midways in the game (depending on your patience), and it has compared scores and evaluations from a huge database of top quality games (imported and self-generated) to give a very reliable evaluation of any opening. Othello is far from solved in the strict sense, but at the same time it seems very unlikely that any major “holes” in its book will be found.

I don't recommend playing too much against it for practice, as you will probably get demotivated from losing all the time! But it's an excellent tool for analyzing your games, or learning openings. You can also get a good feel for the game by watching it play against itself (and possibly compare with the strategy tips at The Othello Guide).

Thanks. I'll try Zebra - not that I need a stronger opponent.

I find the concept of a 'perfect play' hard to understand. How can there be a perfect move? I guess it has to do with the fact that the computer can work out every possible sequence of moves to a finished game after a certain number of moves and it can choose the best one, but surely the method by which it chooses what sequence to take cannot be proved to be perfect (maybe it can and I don't know what I'm talking about). What would happen if a program was made that could play a perfect game from the start and it played against itself? Would it always be a draw or would it be random who won sometimes?

Peter

Good questions, Peter.

I find the concept of a 'perfect play' hard to understand.

Take a 4x4 board and try all the possible options. You will find out that one squence of moves work better than the other. The best seuences (resulting in the biggest win) is the perfect play.

but surely the method by which it chooses what sequence to take cannot be proved to be perfect

But if you tried all the other sequences and found out that they were all worse than your best, you have proof, don't you? Take the 4x4 as example again.

What would happen if a program was made that could play a perfect game from the start and it played against itself? Would it always be a draw or would it be random who won sometimes?

the result will always be the same, otherwise one of the players would not have played perfect. They (some wise men who are working on solving (=finding perfect play) othello) think othello is a draw. That means, besides that it's a perfectly equal game, that when both players play perfect, the result is a draw.

6x6 othello has already been solved, btw (a win for white).

It does play perfectly from around midways, as I said (if told to do so). It doesn't have to check all combinations; some branches of the game-tree can be pruned off: If you know that your opponent has one strong reply to your move that makes it weak, you don't need to check the other replies - well, that's a whole science in itself.

If a computer plays any pure abstract game perfectly against itself, the outcome will always be the same. Not necessarily a draw, but in the case of standard Othello, WZebra's book indeed suggests that it will be a draw. Perfect play on a board of size 6x6 gives a 19-17 win for the second player, as proved by Joel Feinstein.

If you are interested in perfect play for simple abstract games, may I suggest you look at the analysis programs for three mutually related games on my Neutreeko page. :-)

Thanks but I still don't quite get it. A single move results in many different sequences since the opponent may be anywhere in the future. So it cannot choose the move based on the best sequence since there are a number of possible sequences in the future depending on the opponents moves. It can only take the move that results in the maximum number of winning sequences - but this is not necassarily perfect. I know you're right, I'm just trying to understand.

Good to know the 6x6 has been solved. I guess black loses because they have a disadvantage in going first (parity). I can see how the processing time to work out the perfect game increases exponentially with the board size. I wonder how long it will be until we have computers powerful enough to work out the 8x8.

Peter

Perfect play is somehow based on the opponent ALSO playing perfect. A “perfect strategy” means that for every possible move your opponent can make, you will make the move which results in the biggest win (or smallest loss) for yourself. Start from the very last move of the game: Assuming a normal reversi game, you'll only have one place to play, so that trivially also has to be the “best”. At the second last move, however, you could have two possible places to play. Your opponent has to play the other place. Thus, you can calculate what move will give you the highes score. That is your “perfect” move. With three moves left, you could have three possible places to play. Each of these could give your opponent two possibilities, which in turn could give you one. I already told you how to calculate perfect play with two moves left. Now, you assume that your opponent will make the perfect move when there are two moves left. Knowing that, you can calculate your score for each of your three possibilities with three moves left. This should be done backwards until the very first move. The problem, ofcourse, is that the number of possible games becomes so high that it is almost impossible to calculate. Well, today it IS impossible, maybe, but in a few years, it WILL be possible.

I'm not sure I helped you with this post. Maybe someone else can explain it better. Or I can try again sometime when I have more time.

Thanks, I get it now I think.

Apparently it would take 3.8 million million years to calculate the 8x8 perfect game! Maybe when we have quantum computers.

Peter

Chances that Othello is A draw is 99,99%, based on WZerba's book. But because not ALL lines are calculate there is a slightly chance (>00,01%) that there is maybe a 33-31 line for one of the colors.

I heard that there are a few japanese people that work together and have a book around 600mb by fusing books.

Because men think othello is a draw some people try “draw avoidence”. Jan de Graaf of the the Dutch Othello Fedaration let his Zebra learn 24 hours a day, based on this principal.

If you want to understand this way of working read the next article about draw avoidence.

http://othellogateway.com/othello/nbda.php

But if you want to know more just ask Gunnar Anderson, the maker of Othello: gunnar@radagast.se

Or ask Jan de Graaf, he also know a lot of Zebra:

jan.de.graaf@othello.nl

I hope you will understand it now :)

erwin.

I doubt Gunnar has time to answer these kind of emails:) And I also hope I won't get too many emails because I will probably take the time to answer them!

In my opinion the best programs are clearly better than the best humans:

- indeed the best programs can plat the last 50% of the game perfect or at least without any losing mistakes.

- books of the best programs are very big. the book-lines end where the endgame begins. the reason that Othello has not been solved is that the biggest books are still not wide enough. (They are so wide that Othello is >99% surely a draw)

- midgame heuristics for the best programs are also very good, but occaisionally humans can read (or rather “feel”) a position better than a program. With deep midgame searches even this becomes very rare. This is probably the only area where it is still possible to improve Othello programs, although it'll be very difficult.

Othello programs (zebra as best example) are great tools for the top human players to analyse their games, study opening en preparing opening surprises for thier human opponents. For training your endgame ICare or HappyEnd are very nice programs. Emmanuel Lazard, one of the many programmers in the Othello community, has written his own opening trainer program that helps him a lot. These days one has to use computerized tools to become part of the best Othello players in the World.

I have been working on defining the presumed 'drawtree' for Othello using Zebra for the past 6 years. It is running 24/7 on 5 computers now. I expect that proving that Othello is a draw will take several decades, I might even live to experience it:)

Will Othello become boring when it is (nearly) proven? NO! The best players will always be able to play their opponents out-of-book in a subtle way and beat them in a good midgame battle. On top of that many endgames that computers can play perfectly are IMPOSSIBLE to play correctly for humans…

I (with a WZebra+ExtraLargeBook) first expanded a draw picker (pick your own line) book to 24 moves (had to fix some errors on the way)

Strengthen book lines that were rated above -2 by adding to WZebra book and if okey were also added to draw picker book (sometimes also deleted)

Transitions were given code names to prevent duplicate expansion

But then I decided to make slim books, i.e. choose moves that produce a small book against a player wanting to play a big draw book

Black slim draw book has 475 positions to remember and about 60 branches (only showing up to 8)

C4c3D3c5D6e3B5e6F6a6F5b6B4b3D2e2A4c6A5a3F3d1F2g1C2c1B2d7B1a1A2f7C8d8E1f1    B=E7

C4c3D3c5D6e3B5e6F6a6F5b6B4b3D2e2A4c6A5a3F3d1F2g1C2c1B2d7B1a1A2f7C8e7F4d8    B=E1

C4c3D3c5D6e3B5e6F6a6F5b6B4b3D2e2A4c6A5a3F3d1F2g1C2c1B2g3D7c7B8e8C8f7E7f8    B=D8

C4c3D3c5D6e3B5e6F6a6F5b6B4b3D2e2A4c6A5a3F3d1F2g1C2c1B2g3D7c7B8f4B1e7F7g6    B=E1

C4c3D3c5D6e3B5e6F6a6F5b6B4b3D2e2A4c6A5a3F3d1F2g1C2g3C7f4G4h4E1f1G5c8B2h5    B=D7

C4c3D3c5D6f4F5d2F3d7C6c7B4b5A5a3A4a6B6e6E7f8B3f6E3g4G5h4H6a2B7a8D8h5A7b2    B=G6

C4c3D3c5D6f4F5e3G4e6F6d7C7f7C8g5F3g6F8h3E2d2G3e1H4f2H6e7C2d8E8h5H2g8H8h7    B=G7

C4c3D3c5D6f4F5e3G4e6F6d7C7f7C8g5F3g6F8h3E2d2G3e1H4f2H6e7C2h5H2d8E8g8H8h7    B=G7

White slim draw book has 56 positions to remember and only 2 branches

C4e3F6e6F5c5F4g6F7g5D6d3F3c3H4h5G4h3E2f2D2d1G3e1B6c2B4e8F8g8B3e7H7c7B1a5A4g2H1c1G1f1G7b5H6h8H2a1B2a2A3–A6a7D7d8C6    w=b7

C4e3F6e6F5c5C3c6D3d2E2b3C1c2B4b5A6a4E7e1D6d7A5a7B6f1A2b7B1f2D1c7G1f3F4g5G6f8E8f7H6d8C8g3G4h5H3h2G8h4H1g2G7a3B2a1B8a8–    w=h8

Black slim book needed is 1717 positions (200 branches approx) [more to learn with e3 unless they also go slim]

C4c3D3c5B4d2D6b3E6f4E3f3C2f5D1b6F6c7E2f2    B=G3

C4c3D3c5B4d2D6b3E6f4E3f3C2f5D1e7F6a4B5c6    B=B6

C4c3D3c5B4d2D6c6F4f5B6f3E3e2F6f7G4e6G5d7    B=C7

C4e3F6e6F5c5F4g6F7d3F3g5G4e7D6h3F8b5H4c6    B=F2

C4e3F6e6F5c5F4g6F7d3F3g5G4e7D6h3F8g3C6c3    B=C2

C4e3F6e6F5c5F4g6F7d6E7f3G5h5G4g3E2d2H6d7    B=F2

C4e3F6e6F5c5F4g6F7d6E7f3G5h6B6b5C6f8G4c7    B=D7

C4e3F6e6F5c5F4g6F7d6E7f3G5h6B6b5C6f8G4e8    B=D7

C4e3F6e6F5c5F4g6F7d6E7f3G5h6B6b5C6f8G4h5    B=H3

C4e3F6e6F5c5F4g6F7d6E7f3G5h6B6c6D3b5D7c7    B=D8

C4e3F6e6F5c5F4g6F7g5D6d3F3b5C3g3B3b4C6e2    B=C2

C4e3F6e6F5c5F4g6F7g5D6d3F3c3H4h5G4h3E2e1    B=C2

C4e3F6e6F5c5F4g6F7g5D6d3F3c3H4h5G4h3E2f2    B=D2

C4e3F6e6F5c5F4g6F7g5D6d7E7c6G4h3E2d3C3f3    B=G3

Thanks for reviving this interesting old topic.

Can you explain what a slim draw book is, how it works and what the move at the end of your line is?

What is the status of solving Othello 8x8 ?

Start with a draw book, in my case 24 moves, all failing moves should be lose or -2.00, if not make program self play and adjust book until changed

Next each (black & white) slim draw book wants to be the smallest number of positions+move that you need to remember (56 in white's is maybe unbeatable)

Pick moves that give limited choice to the other draw player (in white's slim book give them only one choice except for C4e3F6e6F5c5 b=C3 or b=F4)

Trim book to a manageable size (recommend less than 20k) then expand to more moves and deal with transpositions

You might get a slimmer black book if you don't play for a draw!  (C4e3F4 which maybe -6.00)

e.g. C4c3D3c5B4d2D6b3E6f4E3f3C2f5D1b6F6c7E2f2    B=G3

in this position play G3, if you play D7 or E7 it's still a draw but a bigger book, other moves are/were rated -2.02 or worse so maybe safe to trust

(at the end of midgame only trust -6.00)

It seems to be a draw, to be more certain would have to create a “2 book” (play to win by 2, draw, or lose by 2), and then a “4 book” etc