3 ms·

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 co

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.

axlee 3y ago
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.
- jfengel 3y ago
  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.
- forty 3y ago
  In case you wondering like me, checkers here means American checkers, played on a smaller 8x8 board. International checkers played on 10x10 board is a much bigger space to explore of course.
  - Detrytus 3y ago
    Does the board size matter here? Wouldn't the strategy from 8x8 board somehow generalize to bigger boards? The one issue that I can possibly see is even vs odd board sizes, e.g. play on 9x9 board can be a bit different than 8x8 or 10x10.
    - forty 3y ago
      Solve a 2x2 Rubik's cube and see if that helps solving a 4x4 ^^ From the computer point of view, it's more possible states to explore, so I think it makes things much harder
      - Detrytus 3y ago
        I meant: after you've analyzed the whole solution space for a smaller board, can't you come up with some heuristics, which will be applicable regardless of the board size? Checkers is a very simple game, all pieces are identical, unlike chess.
- RetroTechie 3y ago
  That would be a fun way to define computer opponent: introduce an arbitrary amount of allowed compute power. Say, allowing a purpose designed device, but limited to 1W of power consumption. Or some fixed energy budget (J) per move. Too strong? Take it down to 0.1W, 10mW or whatever. That would degrade brute forcing as a viable approach, and bring it back to smart algorithms, clever ways to reduce the search space, etc.

axlee 3y ago

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.

jfengel 3y ago
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.
forty 3y ago
In case you wondering like me, checkers here means American checkers, played on a smaller 8x8 board. International checkers played on 10x10 board is a much bigger space to explore of course.
- Detrytus 3y ago
  Does the board size matter here? Wouldn't the strategy from 8x8 board somehow generalize to bigger boards? The one issue that I can possibly see is even vs odd board sizes, e.g. play on 9x9 board can be a bit different than 8x8 or 10x10.
  - forty 3y ago
    Solve a 2x2 Rubik's cube and see if that helps solving a 4x4 ^^ From the computer point of view, it's more possible states to explore, so I think it makes things much harder
    - Detrytus 3y ago
      I meant: after you've analyzed the whole solution space for a smaller board, can't you come up with some heuristics, which will be applicable regardless of the board size? Checkers is a very simple game, all pieces are identical, unlike chess.
RetroTechie 3y ago
That would be a fun way to define computer opponent: introduce an arbitrary amount of allowed compute power. Say, allowing a purpose designed device, but limited to 1W of power consumption. Or some fixed energy budget (J) per move. Too strong? Take it down to 0.1W, 10mW or whatever. That would degrade brute forcing as a viable approach, and bring it back to smart algorithms, clever ways to reduce the search space, etc.