Arnold Kling  

My Othello Career

The Dimensionality, Evolution,... Solving Othello: a Follow-Up...

Mostly off topic, but Tyler Cowen sent me a cryptic email asking about it. I can refer him to this essay.from 1998.

With apologies to Robert Fulgum, everything I ever learned about competition I learned by playing Othello(tm owned by Pressman toys). Othello is a board game somewhat like Chess or Go, and it has a small fraternity of competitive players, of which I am one.

When I was at my peak, I might have played at 65 percent of optimality. That is, 65 percent the time I played the correct move for the given position. The 65 percent figure is a guess, because it is impossible to prove that a move is correct (except for positions near the end of the game, when one can use a computer to determine the optimal move by brute force.)

At that time, the world champion of Othello might have played at 75 percent of optimality. If this is correct, and the world champion and I had played 100 games, how many would I have been expected to win?

If you think that 75 percent of optimality vs. 65 percent of optimality should lead to a fairly small difference in games won, you are assuming implicitly that the game only lasts one move. In fact, because each player makes 30 moves, the cumulative effect of a seemingly small difference in accuracy is such that I would be fortunate to win 5 games out of 100 against the world champion.

Suppose that a game lasts N moves. I win when I play correctly for more moves than the world champion. As N becomes large, the small per-move advantage of the world champion compounds until my chances of winning nearly vanish.

...Many people argue that Microsoft wins with inferior software and superior marketing tactics. However, Microsoft software usually is superior in some dimensions, even though it may be inferior in others. My mental model of Microsoft is that, like the world champion in Othello, it makes fewer mistakes than its competitors.

More below the fold, if you are interested. You can also read this interview.

Basically, all it took for computers to overtake humans (or at least this human) in Othello was one or two iterations of Moore's Law back in the late 1980's. I forget whether it was the 486 or the Pentium that did me in.

It was a real lesson in what happens when you're up against a rival whose ability is doubling every 18 months or so. I had a copy of a program by David Parsons that I could whip any time on my then out-of-date computer in the late 1980s. Once I got a newer model, I inserted the exact same disk, and with a faster machine I could not win a game. The computer was now looking ahead 7 to 9 moves within the time constraint, instead of 5, and that made all the difference. Parsons himself crushed me during the U.S. nationals in 1988, because he had run my usual openings through his computer program and found lines that refuted them. He was not a better overall player, as I think he would admit.

Parsons' program was an old-fashioned AI type of program. The next generation used statistics. The computer would have a database of games with positions and outcomes. So, when it looks at a position at move 33, it looks in the database for the most similar sorts of positions and the final scores of those games. Crudely speaking, if the average is a win for Black by 5 discs, then the position is scored as +5 for Black and -5 for White.

So, now, imagine that we are Black, about to make move 25. We create a tree of all possible sequences of moves between now and move 33, and if there is a move 25 (to, say, square c8) that with best play by both sides leads to the position described in the preceding paragraph, then we can score that particular move as +5. If it is the best scoring move, then we go to c8 at move 25.

Except that is looking ahead 8 moves. Zebra Othello used to have no problem looking ahead 15 moves, maybe 20. I have not tried it on any recent computer.

I think the only reason that Othello was not "solved" ten years ago (in the sense that Tic-tac-toe has a solution, which is that optimal play by both sides leads to a draw) is that it turns out that a lot of the openings seem to lead to really close games. I remember having Zebra play out for both sides the result of an opening known as the Rotating Flat, aka the Rose-Kling-Tamenori variation, and the final score was something like 33-31. That was true for a number of other openings as well. What this says is that the tree of optimal Othello games is very bushy, so that humans as currently constructed will never be able to master Othello purely through memorization. So human Othello will remain interesting, even though computer Othello might ultimately be dull, because by now it may be possible to solve the game on the computer.

My career began in 1981 and lasted about 10 years. I never won a U.S. national title. Two rival players, Brian Rose and David Shaman, were better than me. I wrote a lot of good articles for Othello Quarterly, but there is no online archive. If somebody wants a set of old issues to scan in and put on line, I am pretty sure I have a complete set through the early 1990s.

My best tournament was the Internationals in Milan in 1987 (the only international in which I participated). The U.S. sent three players as a "team," and I came in 6th--behind Brian and David but much better than expected relative to the top players European players. The Japanese sent only one of their top players (who finished first), or else they would almost surely have finished 1-2-3. During the 1980s and 1990s, only a handful of non-Japanese ever came in first. Brian and David won international titles, but they had to become really obsessive in order to do so*. Not that there's anything wrong with that.

(*by any rational standard, of course, I also was obsessive. But I did manage to hold on to a full-time job and spend time with my children)

Comments and Sharing

CATEGORIES: Growth: Consequences

COMMENTS (21 to date)
Tyler Cowen writes:

Excellent, thanks...

Eric writes:

I doubt that computers have solved Othello or that they ever will. If I remember the rules for Othello, it's played on an 8x8 board, pieces once played are never removed (although they can switch colors) and a game ends when all spaces are filled. So there are 64! possible games, which is about 10^89. I think the average computer does maybe 10^12 or 10^13 operations a second. So even if we had 10^20 computers that could do 10^20 operations a second, it would take them 10^42 years to finish. Our sun will probably explode in around 10^7 years.

Now computers do have very good tricks to estimate which moves are more likely to win and certainly towards the end of the game they can calculate the outcome of the game for all possible moves, but it will probably take more time than mankind will have to figure out the outcome for every possible move from the beginning of the game.

Eric writes:

I'm sorry, the sun won't explode for another 10^10 years. Quite a bit more time for people, but not enough for computers to solve the game.

Kevin Dick writes:

This is similar to my analysis of sparring against my mixed martial arts trainer, a formal professional.

I can perform any given technique, on average, 90% as well as he can. This is pretty much imperceptible to the casual observer.

However, it usually takes at least 3 techniques to overwhelm an opponent's defenses and score. Typically, 5 is the number. The less well you do a technique, the worse position you're in for the next technique. So errors compound.

Therefore, once we engage, by the time we're in scoring position, I'm at 60% of his capability. Perceptible at a glance.

DWAnderson writes:

Eric, if computer operations per second increase by an order of magnitude every 7 years or so, however (consistent with Moore's law). a single computer could solve by brute force in a year in about 500 years. Not soon, but before the sun explodes. Of course long before then sentient machines may well have solved Othello through non-bute force methods.

Dog of Justice writes:

Eric, your analysis overstates the complexity of Othello.

The center four squares are always occupied, and the other 60 squares can be either white, black, or blank. By symmetry, we can assume it's always white's turn to move in this database; then we have at most 2^4 * 3^60 board states, under 10^30. There are additional symmetries that can be exploited to cut this number down more.

I would not be surprised to see Othello solved in my lifetime.

Doc Merlin writes:

"My mental model of Microsoft is that, like the world champion in Othello, it makes fewer mistakes than its competitors."

This I disagree on.

Allie writes:

[Comment removed pending confirmation of email address. Nick edited. Email the to request restoring this comment. A valid email address is required to post comments on EconLog.--Econlib Ed.]

Finch writes:

In addition to the symmetries pointed out above, attempts to solve chess-like games often work backwards as well as forwards. I.e., they look at the possible end-states and work back to the possible predecessor states. Working the tree from both ends greatly reduces the combinatorial magnitude of the problem. This was important in using Chinook to solve checkers. I don't know Othello well, so I'm not sure how well this would apply.

In general, it isn't just Moore's Law; there's a great deal of cleverness going into the software for artificial game playing agents.

6x6 Othello is solved. 8x8 is not solved, but computer analysis is highly suggestive of it being a draw. I'd be surprised if it wasn't solved in the next few decades.

fundamentalist writes:
My mental model of Microsoft is that, like the world champion in Othello, it makes fewer mistakes than its competitors.

In business, all mistakes aren't created equal. Some are fatal. In the late 1980's the home computer market was divided almost in equal thirds between MS, Apple and Amiga. Amiga had the better graphics and bet the farm that gaming would be the future of the pc. It lost, partly because it was so expensive ($2,000 in the late 80's).

MS concentrated on business software and it licensed its OS to as many equipment manufacturers as possible. As a result, MS based hardware was much cheaper than Apple hardware because Apple wanted all the profit available in hardware as well as software. Cheaper hardware caused MS based pc's to capture most of the market.

For old farts out there, recall how the slightly inferior VHS system beat the superior Beta system from Sony. The same thing happened. Sony built all the beta vcr's while the makers of VHS (I forget) licensed the technology to many competing vcr makers.

All of those decisions were marketing decisions. Marketing mistakes can be deadly.

Jesper writes:

Eric, you vastly overestimate the size of the game tree. First, the first five pieces are always in the same configuration (symmetries considered). So we have 59!, not 64!. Then most squares are illegal, which cuts down the number further. Wikipedia has the number of possible games at about 10^54 and the number of positions at 10^28.

Then we have the alpha beta algorithm. In essence, at every node in the game tree, if one move is determined to be a win for the player that does the move, the siblings need not be searched - they can't be better than a win. This may seem trivial, but given a good move ordering, determined by heuristics, it may cut the tree size down to its square root.

Also, consider that if we could save all positions searched, then about 10^28 nodes searched would suffice, as the rest could be resolved instantly by hash table lookups. Now, 10^28 is too much space, but we can save the most important (topmost) positions in the tree.

In all, Othello is nearly solved. I agree with Finch that it will be solved within a few decades.

PrometheeFeu writes:

On Othello, I agree with those who say it will be solved relatively soon if we decide to throw enough computing power at it. If anything, the problem is pretty close to being embarrassingly parallel and has lots of opportunities for pruning. Not saying that it WILL be solved as it would still be fairly hefty to solve, but it will definitely be solvable soonish.

On Microsoft, I think what people fail to mention is the strong network externalities that favor them as the incumbent player. Most companies use Windows OS and Microsoft Office as their standard. Therefore, most people learn Windows OS and Microsoft Office so they can get hired. Therefore, most companies decide to use Windows and Microsoft Office so they can more easily find employees. Re-training yourself to be able to use some alternative may be fairly expensive (or at least is perceived as such) and changing the equipment your company uses would also be fairly expensive. (Just think re-training the IT staff and having them give up on everything they built around Microsoft products) So Microsoft does not have to be the best to win. It just has to be better than the alternative minus the cost of switching. That's why many alternatives have worked really hard on reducing the cost of switching by making their user interface easier and more familiar to windows users. Unfortunately, even the cost of learning the cost of switching is fairly high. So unless Windows REALLY goes bad, or some alternative offers some REALLY AMAZING improvement, we're stuck with Windows for a while. Mind you, if we were to switch, the same thing would probably happen again with the new incumbent having less incentive to improve and innovate than the alternatives.

Mr Mister writes:

Re: Microsoft:

For the consumer or average single user, Arnold's analogy may hold. But speaking as a business user of MS Office software in 2011, it's not a matter of mistakes - there isn't really even a viable competitor for the enterprise class software they sell. Open source alternatives (e.g. Google Docs, OpenOffice) are vastly inferior for automating repetitive tasks and creating complex documents, spreadsheets, and applications.
The implementation of VBA alone would keep most mid- to large companies on MS Office. I could believe that Mac or Linux based OS's might have a shot vs. Windows OS's for PC's and servers, but Office is in a class of it's own. In terms of integrated business apps, no one else is even playing ball in their league at the enterprise level.

Jesper writes:

PrometheeFeu, actually, parallelization is not that easy. You need to do alpha-beta, and you need to try not to search paths that will be cut-off anyway. Ok, it may parallelize fairly well, but not "embarassingly" so.

Finch writes:

What Jesper said.

Alpha-Beta is inherently serial. There are many related parallel algorithms, but they have trouble getting speedups of more than a factor of a couple of hundred and inherently do a lot more work.

In Chess, today, the best programs are serial or use a small number of threads. The trick is knowing where to prune and where to extend, and of course, good board evaluation. Though there's debate, smart chess programmers often put the yearly ELO growth at about half due to hardware advances and half due to software advances.

Major advances have been made in computer Go via Monte-Carlo Tree Search variants, which make pretty good use of parallel hardware. And are quite different from Alpha-Beta.

Duncan writes:

I'm reminded of the joke about the Astronomy lecturer where a student in the front row says:
"Excuse me, Professor, could you repeat that?"
"I said the sun will explode in 10 billion years."
"Thank God for that - I thought you said 10 million!"

Eric writes:

Arg, I mixed up the piece placement rules for Othello (must place next another piece so that a capture is made) with those of Go (can place in any open space). Yeah, that does drastically simplify the number of possible moves at any point in the game and makes the tree narrower. I stand corrected.

Andy writes:

I would expect Othello to be solved in the next few years. We're almost there. Of course not much research time is spent on this.

Cryptomys writes:

Arnold is being modest. It's true that Rose and Shaman were better than Arnold, but Rose and Shaman were both world champions. Arnold is at least an International Master of Othello, maybe a Grandmaster.

The British radical gerontologist Aubrey deGrey is also a strong Othello player. I saw Sylvia Bokor on a video about Ayn Rand the other day. She is a weak Othello player. BTW, I once beat the Parsons program in an over the board tournament by running it out of time. I think it was running on a 486 at about 40 Mhz.

What Arnold seems to be proposing is a practical, but not a rigorous, solution to 8x8 Othello, the standard game. I believe that 6x6 Othello was rigorously solved some time ago. If 8x8 Othello were solved, my guess is that tournament players would simply shift to a larger version of the game, such as 10x10 or 12x12.

Matthias Berg writes:

About the complexity of Othello:
IIRC, on average there are about 8.5 possibilities per move over the 60 moves.
Good Othello programs can solve the last 30 moves in decent time (on a fast computer it shouldnt take more than some minutes I think).
So is that 8.5^29*x where x is the time spent for the 30 empties?
Not sure we'll really see it mathematically solved soon, but the top programs won't be beatable real soon. Saio rarely loses at all.

David Toth writes:

I must mention that Jonathan Cerf did win the International Championship for the US.

Comments for this entry have been closed
Return to top