4 ms·

> 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

by sdwr 3y ago

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

dist-epoch 3y ago
More likely, those 2587 positions cover all possibilities. There are other proofs like this - the 4 color theorem one, which was also reduced to a finite number of configurations which were manually colored.
- BlackFingolfin 3y ago
  But none of this explicit. This is at best an announcement of a potential proof. But it isn't a proof yet. Also curious: in the end of the paper they talk about having "weakly solve" Othello... the paper overall reads really strangely.
  - dfan 3y ago
    "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.
    - BlackFingolfin 3y ago
      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 this is a side concern at best anyway.
      - anigbrowl 3y ago
        They wrote about this in the introduction and in the context of algorithm 2.
      - NooneAtAll3 3y ago
        > To me "solved" would suggest "strongly solved". But perhaps equating "solved" with "weakly solved" is default in this area? It's the default for all reasonable games - statespace is huge (i.e. tic-tac-toe is childsplay) and simple strategies don't exist (that'd make bad human game). You can't even iterate all positions - even less prove them all for one outcome.
      - light_hue_1 3y ago
        > 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.
  - jmmcd 3y ago
    "weakly solve" is not curious. Read from the start, they define this.
  - sdwr 3y ago
    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!
    - sebzim4500 3y ago
      The concept of "weakly solved" is not original to this effort. IIRC checkers was weakly solved for years but is now strongly solved.
      - tialaramex 3y ago
        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) 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.
        Raidion 3y ago
        Poker being one of my favorite hobbies (probably 300k hands played lifetime), it's wild how much variance matters. Like a 4BB/100 winrate (aka you win 4 big blinds every 100 hands) is very much an "I can be a professional" winrate. You have a ~10% chance over 100k hands to be <0 dollars earned. Likewise, 10% of time time you'll make twice that. Poker is fascinating in that there are a ton of people who never actually hit the true law of big numbers hands and walk around thinking "I'll never be good enough to play at X level" or "I'm a poker god with big winnings" not knowing how good they really are. Professional players do actually get in statistically significant sample sizes, but for amateur players, most don't get enough hands to really understand their skill level.
missblit 3y ago
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)
- sdwr 3y ago
  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.
  - notdonspaulding 3y ago
    > 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 https://webstersdictionary1828.com/Dictionary/Enumerate "innumerable" means "unable to be numbered, or counted" https://webstersdictionary1828.com/Dictionary/innumerable https://webstersdictionary1828.com/Dictionary/innumerable
    - sdwr 3y ago
      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 ;)
CSMastermind 3y ago
I also got confused at this part. I've now read the paper twice and I'm not sure I understand their method. Overall the way the paper is written is not straightforward. It's possible the author is correct, I'd need to really sit down and try to work out their reasoning but at first pass I'm skeptical.
devit 3y ago
They computed results for a bunch of 36-empty-squares positions on their clusters and uploaded them to https://figshare.com/articles/dataset/Analyses_of_the_Game_of_Othello_s_Positions/24420619 https://figshare.com/articles/dataset/Analyses_of_the_Game_o... The script at https://github.com/eukaryo/reversi-scripts/blob/main/reversi_player.py https://github.com/eukaryo/reversi-scripts/blob/main/reversi... plays perfectly (assuming the whole thing is correct) a bunch of data computed by other scripts in the repository using the 36-empty-squares solutions, for which a regular machine is presumably suitable. It seems that what it does is essentially look up a <=300GB table with all positions with 37-64 empty squares reachable from the weak solution, and runs edax with "-solve" for positions with <=36 empty squares.
- b33j0r 3y ago
  I’m not taking a stance on “Othello is solved”, but offer a digression about a lookup table being a valid solution to a tractable problem, or its subproblem. I don’t see a lot of people saying this (not parent either), but I know that many hope for closed-form solutions to things, even secretly. It just dang doesn’t look that way anymore. Weird when a finite set is sufficient to prove subproblems that cover a perplexingly different or larger domain. Whether a proof is accepted or not, we’ll still kinda wonder on the structure of special cases in computational complexity. They seem to work unreasonably well, and we rarely find them by hand/brainmeat.

by sdwr 3y ago

dist-epoch 3y ago

More likely, those 2587 positions cover all possibilities. There are other proofs like this - the 4 color theorem one, which was also reduced to a finite number of configurations which were manually colored.

BlackFingolfin 3y ago
But none of this explicit. This is at best an announcement of a potential proof. But it isn't a proof yet. Also curious: in the end of the paper they talk about having "weakly solve" Othello... the paper overall reads really strangely.
- dfan 3y ago
  "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.
  - BlackFingolfin 3y ago
    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 this is a side concern at best anyway.
    - anigbrowl 3y ago
      They wrote about this in the introduction and in the context of algorithm 2.
    - NooneAtAll3 3y ago
      > To me "solved" would suggest "strongly solved". But perhaps equating "solved" with "weakly solved" is default in this area? It's the default for all reasonable games - statespace is huge (i.e. tic-tac-toe is childsplay) and simple strategies don't exist (that'd make bad human game). You can't even iterate all positions - even less prove them all for one outcome.
    - light_hue_1 3y ago
      > 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.
- jmmcd 3y ago
  "weakly solve" is not curious. Read from the start, they define this.
- sdwr 3y ago
  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!
  - sebzim4500 3y ago
    The concept of "weakly solved" is not original to this effort. IIRC checkers was weakly solved for years but is now strongly solved.
    - tialaramex 3y ago
      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) 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.
      - Raidion 3y ago
        Poker being one of my favorite hobbies (probably 300k hands played lifetime), it's wild how much variance matters. Like a 4BB/100 winrate (aka you win 4 big blinds every 100 hands) is very much an "I can be a professional" winrate. You have a ~10% chance over 100k hands to be <0 dollars earned. Likewise, 10% of time time you'll make twice that. Poker is fascinating in that there are a ton of people who never actually hit the true law of big numbers hands and walk around thinking "I'll never be good enough to play at X level" or "I'm a poker god with big winnings" not knowing how good they really are. Professional players do actually get in statistically significant sample sizes, but for amateur players, most don't get enough hands to really understand their skill level.

missblit 3y ago

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)

sdwr 3y ago
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.
- notdonspaulding 3y ago
  > 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 https://webstersdictionary1828.com/Dictionary/Enumerate "innumerable" means "unable to be numbered, or counted" https://webstersdictionary1828.com/Dictionary/innumerable https://webstersdictionary1828.com/Dictionary/innumerable
  - sdwr 3y ago
    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 ;)

CSMastermind 3y ago

I also got confused at this part. I've now read the paper twice and I'm not sure I understand their method. Overall the way the paper is written is not straightforward. It's possible the author is correct, I'd need to really sit down and try to work out their reasoning but at first pass I'm skeptical.

devit 3y ago

They computed results for a bunch of 36-empty-squares positions on their clusters and uploaded them to https://figshare.com/articles/dataset/Analyses_of_the_Game_of_Othello_s_Positions/24420619 https://figshare.com/articles/dataset/Analyses_of_the_Game_o... The script at https://github.com/eukaryo/reversi-scripts/blob/main/reversi_player.py https://github.com/eukaryo/reversi-scripts/blob/main/reversi... plays perfectly (assuming the whole thing is correct) a bunch of data computed by other scripts in the repository using the 36-empty-squares solutions, for which a regular machine is presumably suitable. It seems that what it does is essentially look up a <=300GB table with all positions with 37-64 empty squares reachable from the weak solution, and runs edax with "-solve" for positions with <=36 empty squares.

b33j0r 3y ago
I’m not taking a stance on “Othello is solved”, but offer a digression about a lookup table being a valid solution to a tractable problem, or its subproblem. I don’t see a lot of people saying this (not parent either), but I know that many hope for closed-form solutions to things, even secretly. It just dang doesn’t look that way anymore. Weird when a finite set is sufficient to prove subproblems that cover a perplexingly different or larger domain. Whether a proof is accepted or not, we’ll still kinda wonder on the structure of special cases in computational complexity. They seem to work unreasonably well, and we rarely find them by hand/brainmeat.