Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Othello Is Solved?

arxiv.org

Post reply on HN
Print view View original

141–150 of 285 posts

Re: Othello Is Solved?

#141

Post by foota »

charcircuit wrote: post #46
cvoss wrote: post #16

Earlier quoted context omitted.

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.

The author isnt claiming it's possible to win against a perfect opponent, but rather, all perfect play scenarios end in a draw. If both players either can't play perfectly, or choose to play imperfectly, then it moves into unknown territory and either side can force a win.

This does have to be mutual though, if only one side plays imperfectly, then the other can always force at least a draw.

So if you know the other side is incapable of playing perfectly, it could be rational to deviate.

Re: Othello Is Solved?

#142

Post by light_hue_1 »

BlackFingolfin wrote: post #60
dfan wrote: post #27

Earlier quoted context omitted.

"Weakly solving" a game is a technical term. If you have weakly solved a game, you can play perfectly (achieve the optimal result) when the game starts from its initial position. If you have strongly solved it, you can play perfectly starting from any position.

Sorry, I was unclear: I know what weakly solved means. What I find curious is that the title and abstract refer to "solved", and don't mention what they actually mean. To me "solved" would suggest "strongly solved". But perhaps equating "solved" with "weakly solved" is default in this area? Still, I would like expect an abstract to say something like that explicitly. But given the overall state of that paper I think…

> But perhaps equating "solved" with "weakly solved" is default in this area?

It is the default and all that matters.

This is one of the dangers of reading papers as a non-expert. You can dismiss or be wowed by something that is totally irrelevant.

They wrote the paper very much like the Checkers paper from Science 2007.

Re: Othello Is Solved?

#143

Post by Magi604 »

neontomo wrote: post #108
bentcorner wrote: post #96

Earlier quoted context omitted.

> an African game with about 10 pits on each side of the board that hold stones https://en.wikipedia.org/wiki/Mancala if you want more info

Also, another version I'm more familiar with from childhood is https://en.wikipedia.org/wiki/Kalah

Here is the game I played with my grandma when I was younger:

https://en.wikipedia.org/wiki/Southeast_Asian_mancala

Re: Othello Is Solved?

#144

Post by Y_Y »

gtbcb wrote: post #129

I would love a Wikipedia list article of games that have been solved computationally and but also games where humans can still beat computers / AI, discussing the challenges and context behinds wins / losses.

Are there any board games left where humans beat the best computers?

On a related note, are there any Wikipedia list articles which are empty lists?

Re: Othello Is Solved?

#145

Post by Asraelite »

SonOfLilit wrote: post #57
charcircuit wrote: post #46

Earlier quoted context omitted.

>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.

No, the paper only "weakly solves", so it doesn't give a perfect strategy of the type you talk about. Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess. Armed with it, you will still lose easily to Magnus Carlsen. He will deviate fro| the sequence and you won't know the perfect responses to his moves.

"Weakly solved" does actually imply that perfect strategy. I think you're referring to "ultra-weakly solved", which seems to be what the paper did.

Re: Othello Is Solved?

#146

Post by mafuy »

tromp wrote: post #100
bradwood wrote: post #7

How about the ancient Chinese game of "go", next? Not convinced that can easily be solved at all.

Go is considered close to being solved on a 7x7 board [1]. The grand challenge would be solving 9x9 Go, the standard beginner board size. Note that professional players are far from mastering 9x9, and regularly play 9x9 tournaments. Solving the full 19x19 game is utterly out of the question. [1] https://forums.online-go.com/t/katago-attempts-to-solve-7x7/...

There was a recent push for 9x9. It's not solved but it is believed to be near perfect play.

https://katagobooks.org/9x9highlights.html

Re: Othello Is Solved?

#147

Post by bluGill »

leoff wrote: post #65
SonOfLilit wrote: post #57

Earlier quoted context omitted.

No, the paper only "weakly solves", so it doesn't give a perfect strategy of the type you talk about. Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess. Armed with it, you will still lose easily to Magnus Carlsen. He will deviate fro| the sequence and you won't know the perfect responses to his moves.

> Imagine finding a pamphlet written by God that contains a listing of a perfect game of chess How would you go to prove that this is the perfect game of chess, if you didn't explore all of it's possible sequences? If they did solve the game, there's no way around knowing all possible outcomes - starting from a fixed given position.

You don't, you trust that God has proved.

Re: Othello Is Solved?

#148

Post by sundarurfriend »

bentcorner wrote: post #96
mark_l_watson wrote: post #89

This is cool. I solved a simpler game about 15 years ago that my brother and I used to play: an African game with about 10 pits on each side of the board that hold stones. I coded up an alpha-beta engine for it, and discovered crazy always win strategies to match how my brother and I played. Suddenly I would win all the games, and then he never wanted to play again. This was a classic match up of a computer scientist…

> an African game with about 10 pits on each side of the board that hold stones https://en.wikipedia.org/wiki/Mancala if you want more info

Reminded me of https://en.wikipedia.org/wiki/Pallanguzhi

And it is indeed mentioned under the Names and Variants section. Seems likely that there's a historical connection somewhere.

Re: Othello Is Solved?

#149

Post by sdwr »

notdonspaulding wrote: post #137
sdwr wrote: post #47

Earlier quoted context omitted.

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.

> From start of game to 50 squares left is enumerable. A nitpick, but I don't think you meant to say "enumerable" here "enumerable" means "able to be enumerated, or counted" https://webstersdictionary1828.com/Dictionary/Enumerate "innumerable" means "unable to be numbered, or counted" https://webstersdictionary1828.com/Dictionary/innumerable

Enumerable as in "computationally enumerable", or "able to be enumerated in a reasonable amount of time x cpu x memory"

The beginning and end of the game have less possibilities to consider. The midgame has the most possible moves = hardest to calculate.

If you read carefully, the midgame is the bit the author avoids explaining how to solve ;)

Re: Othello Is Solved?

#150

Post by bluGill »

mtlmtlmtlmtl wrote: post #49
axlee wrote: post #5

Earlier quoted context omitted.

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 bac…

Great chess players often pull out a draw from what looks like an obviously lost position. Mostly great players start playing for a win, but somewhere in the middle they realize winning is hopeless and switch to looking for a draw.
Post reply on HN