If anyone fancies playing the game, I made this for/with my kids: https://jawj.github.io/fliptiles
(The ‘AI’ player is very weak)
Othello Is Solved?
41–50 of 285 posts
Re: Othello Is Solved?
#42> Next, we selected 2,587 positions out of the aforementioned 2,958,551 positions and formulated hypotheses regarding their outcomes. We chose them such that if all these hypotheses were proven correct, it would prove that the initial position results in a draw. But no elaboration? Sounds to me like the game is not solved, instead the author looked pretty hard for a winning line, and didn't find one.
I only skimmed it, but it looks like they described this to me.
The next sentence:
> Although there are numerous ways to select subsets that would prove the initial position results in a draw, we used algorithm 1 to obtain a small subset.
Algorithm 1:
> We developed an algorithm that requires predictive scores for all positions with 50 empty squares and returns a subset such that if the all positions belonging to that subset are solved, and the all solutions match the predictions, the initial position is consequently solved. It was described as Algorithm 1.
(The algorithm is also printed out)
Re: Othello Is Solved?
#43For those interested in the game (it's popular among computer science and AI scholars), the Othello world championship is currently underway in Rome, Italy with games live streamed on liveothello.com and Youtube @WorldOthello
Does this paper render the championship moot? Is any software based on the paper entered? Is Othello like checkers, where there were mostly draws in high level games?
Chess is weakly solved for all practical purposes (it's not proven but no one is able to show a winning sequence for white even with weeks to prepare vs a top engine playing with something like 30 minutes per move) and it doesn't affect the competition at all. It's impossible to remember it all anyway.
Once/if chess is formally weakly solved it will change exactly nothing for human chess players. If your plan is to remember the solution you may just as well start learning top engine lines today.
Re: Othello Is Solved?
#44Earlier quoted context omitted.
Now that Othello is solved, there exist a set of rules a player can follow to guarantee a win or draw every game. It's possible (if unlikely) that a computer could sufficiently compress those rules to be memorizable (and then applicable) by a human.
Checkers have been solved 16 years ago and still see competition. A game being solved is not exactly the same as "apply this memorizable algorithm and you'll win", especially if the solution implies scanning 10^n positions for each move.
I recall hearing that competition checkers has a randomization element at the start, to keep it more interesting. I believe checkers is strongly solved anyway, but it at least keeps people from memorizing all of the major lines.
Re: Othello Is Solved?
#45Ok, so we just have to keep adding rows and columns to the game in order to keep the game from being "solved"?
Re: Othello Is Solved?
#46Earlier quoted context omitted.
Does this paper render the championship moot? Is any software based on the paper entered? Is Othello like checkers, where there were mostly draws in high level games?
This paper "weakly solves" Othello. That means that we know for the initial board state both 1) the final win/lose/draw outcome (it's a draw), and 2) the sequence of moves that should be taken by perfect players to get there (Figure 1, right). In particular, the paper does not "strongly solve" Othello. If you have an arbitrary board state, 1) and 2) are are not necessarily known for it. That means it's still possible…
>That means it's still possible to win a game by intentionally deviating from the perfect sequence
Someone with perfect strategy would have an answer for any deviation. Playing imperfectly would likely get you into a losing position. There is no way to go from a game being drawn if played perfectly to being winning if the then loser were to be using perfect strategy.
Re: Othello Is Solved?
#47> Next, we selected 2,587 positions out of the aforementioned 2,958,551 positions and formulated hypotheses regarding their outcomes. We chose them such that if all these hypotheses were proven correct, it would prove that the initial position results in a draw. But no elaboration? Sounds to me like the game is not solved, instead the author looked pretty hard for a winning line, and didn't find one.
I only skimmed it, but it looks like they described this to me. The next sentence: > Although there are numerous ways to select subsets that would prove the initial position results in a draw, we used algorithm 1 to obtain a small subset. Algorithm 1: > We developed an algorithm that requires predictive scores for all positions with 50 empty squares and returns a subset such that if the all positions belonging to tha…
Algorithm 1 doesn't say shit! It says "pick the best move", or "pick all the moves".
From start of game to 50 squares left is enumerable.
From 36 moves left to end-of-game is apparently solvable.
The middle is the combinatorial explosion, and he avoids explaining how he navigates it.
Re: Othello Is Solved?
#48Earlier quoted context omitted.
This looks like a George W "Mission Accomplished" moment. - the game is obviously known to be a draw - but we don't have computational power to enumerate that - so test a bunch of game states - and confirm that none of them are wins - ??? - it's solved! Trust me!
The concept of "weakly solved" is not original to this effort. IIRC checkers was weakly solved for years but is now strongly solved.
And you can go further Heads Up (ie two player) Limit (ie you decide to raise or not, the size of the raise is fixed) Texas Hold 'Em (the style of Poker most played today) is essentially weakly solved.
The process used generates a statistical approximation and tells you how close it is to correct, in theory a perfect solution would beat this by that amount, in practice of course Poker is a game of chance, and so over any realistic game it wouldn't matter because the deviation from correctness they've computed is tiny. Could they make an even smaller deviation with more compute used? Sure, but why bother.
https://en.wikipedia.org/wiki/Cepheus_(poker_bot)
Cepheus is instructive also because some humans have played against this and believed they were outplaying it, which indicates there are real human poker players who misunderstand their own variance so much (and/or discount real variance from others so much) that they're completely unable to successfully rate their abilities.
If you lose 12Bb over 100 hands you are not, in fact, "winning except that it sometimes gets lucky". You're just losing, of course it sometimes gets lucky, that's how luck works, it's a game of chance.
Re: Othello Is Solved?
#49Earlier quoted context omitted.
Does this paper render the championship moot? Is any software based on the paper entered? Is Othello like checkers, where there were mostly draws in high level games?
Why would it render human games moot? Why would a software participate in a championship? The draw percentage in checkers/draught and in chess are roughly similar, (anywhere between 50% and 60% at high-level play), despite checkers being solved and chess not.
And honestly I think the draw percentage in chess is influenced just as much by sociological processes as it is by game theoretic concerns. The very top chess players are extremely risk averse. Chess is way too complex for humans to ever be able to play perfectly in sufficiently complex positions, honestly. The top players today obsessively avoid positions like that unless they can find a forced drawing line as a backup.
In other words, not losing is heavily prioritised over winning in top chess, currently.
There are many possible ways to change this. My favourite is to make a win worth 3 points, and a draw 1 point. Both in tournament scoring and rating calculation.
I think this would incentivise more aggressive play, and disincentivise the constant slog of the same 15 top players playing mostly draws against eachother, and barely playing in more open tournaments with a bigger rating interval.
Re: Othello Is Solved?
#50The thing I love about Othello is the contradiction between action and territory. While the game develops, playing your turn is in some sense against you, yet you must. Hence, you need to remain compact and inner while you occupy, until space becomes too small and its time to reclaim definite influence.