3 ms·

This is awesome! Any idea where Chess would stack up? I'm assuming it'd be greater than Checkers in that list, but how much greater? And would Nim be simpler

This is awesome! Any idea where Chess would stack up? I'm assuming it'd be greater than Checkers in that list, but how much greater? And would Nim be simpler than Gomoku (Connect-N)?

jefftk 7y ago
If you or someone else would like to have a go at writing one I'd be happy to review and add it! https://github.com/jeffkaufman/game-complexity https://github.com/jeffkaufman/game-complexity
- CydeWeys 7y ago
  Nice. I wonder, would it make sense to encode the idea of a square and hex grid with pieces of two different colors as a library of sorts, such that this basic grid implementation doesn't count against each game individually? The boards are very widely reused, generic, mathematical concepts. This would give something like Go or Connect-N a fairer shot of competing against something like a Nim, which only needs a single integer accumulator to represent its game state.
  - jefftk 7y ago
    The compressed Go program gets only 2.3% smaller post-gzip (13 bytes) if you remove the definition of the board: b=[[' ']*19 for x in range(19)] Most of the complexity is in what changes players are allowed to make to the board.
    - DavidSJ 7y ago
      Note that there are some rule sets in which suicide is legal, so long as it doesn’t violate a generalized ko rule (no repeated board positions, considering whose turn it is as part of the position).
      - jefftk 7y ago
        I implemented the Tromp-Taylor rules (https://en.wikibooks.org/wiki/Computer_Go/Tromp-Taylor_Rules https://en.wikibooks.org/wiki/Computer_Go/Tromp-Taylor_Rules) which have "A turn is either a pass; or a move that doesn't repeat an earlier grid coloring." Since it doesn't consider whose turn it is to move in whether a grid coloring is repeated, it won't allow suicide.
        thaumasiotes 7y ago
        The prohibition on matching any earlier state of the board makes playing the game significantly more complex in reality, but not in terms of how many bits it takes to describe the rules. Have you considered defining the complexity in terms of the number of bits required to implement the game, and not just the ruleset? Go requires a potentially very large list of past board states.
        CydeWeys 7y ago
        The amount of memory used in the execution of the program doesn't seem as important, and biases against games played on larger boards for no real reason. At the extreme end, you'd say that Conway's Game of Life takes infinite memory and is thus of infinite complexity because it occurs on an unbounded board, yet, the actual rules are very small and simple to implement.
jdkee 7y ago
Checkout Oscar Toledo’s nanochess for tiny chess implementations. https://nanochess.org/chess.html https://nanochess.org/chess.html

This is awesome! Any idea where Chess would stack up? I'm assuming it'd be greater than Checkers in that list, but how much greater? And would Nim be simpler than Gomoku (Connect-N)?

jefftk 7y ago

If you or someone else would like to have a go at writing one I'd be happy to review and add it! https://github.com/jeffkaufman/game-complexity https://github.com/jeffkaufman/game-complexity

CydeWeys 7y ago
Nice. I wonder, would it make sense to encode the idea of a square and hex grid with pieces of two different colors as a library of sorts, such that this basic grid implementation doesn't count against each game individually? The boards are very widely reused, generic, mathematical concepts. This would give something like Go or Connect-N a fairer shot of competing against something like a Nim, which only needs a single integer accumulator to represent its game state.
- jefftk 7y ago
  The compressed Go program gets only 2.3% smaller post-gzip (13 bytes) if you remove the definition of the board: b=[[' ']*19 for x in range(19)] Most of the complexity is in what changes players are allowed to make to the board.
  - DavidSJ 7y ago
    Note that there are some rule sets in which suicide is legal, so long as it doesn’t violate a generalized ko rule (no repeated board positions, considering whose turn it is as part of the position).
    - jefftk 7y ago
      I implemented the Tromp-Taylor rules (https://en.wikibooks.org/wiki/Computer_Go/Tromp-Taylor_Rules https://en.wikibooks.org/wiki/Computer_Go/Tromp-Taylor_Rules) which have "A turn is either a pass; or a move that doesn't repeat an earlier grid coloring." Since it doesn't consider whose turn it is to move in whether a grid coloring is repeated, it won't allow suicide.
      - thaumasiotes 7y ago
        The prohibition on matching any earlier state of the board makes playing the game significantly more complex in reality, but not in terms of how many bits it takes to describe the rules. Have you considered defining the complexity in terms of the number of bits required to implement the game, and not just the ruleset? Go requires a potentially very large list of past board states.
        CydeWeys 7y ago
        The amount of memory used in the execution of the program doesn't seem as important, and biases against games played on larger boards for no real reason. At the extreme end, you'd say that Conway's Game of Life takes infinite memory and is thus of infinite complexity because it occurs on an unbounded board, yet, the actual rules are very small and simple to implement.

jdkee 7y ago

Checkout Oscar Toledo’s nanochess for tiny chess implementations. https://nanochess.org/chess.html https://nanochess.org/chess.html