chessboard 1.5.0

Motivation

This project is a playground to test some optimization strategies in Python, but is essentially an example of a real-life Python package, and serve me as a boilerplate project for future CLI.

Install

This package is available on PyPi, so you can install the latest stable release and its dependencies with a simple pip call:

$ pip install chessboard

Usage

List global options and commands:

$ chessboard --help
Usage: chessboard [OPTIONS] COMMAND [ARGS]...

  CLI to solve combinatoric chess puzzles.

Options:
  --version      Show the version and exit.
  -v, --verbose  Print much more debug statements.
  --help         Show this message and exit.

Commands:
  benchmark  Benchmark the solver.
  graph      Plot solver performances.
  solve      Solve a chess puzzle.

Solver specific options:

$ chessboard solve --help
Usage: chessboard solve [OPTIONS]

  Solve a puzzle constrained by board dimensions and pieces.

Options:
  -l, --length INTEGER  Length of the board.  [required]
  -h, --height INTEGER  Height of the board.  [required]
  -s, --silent          Do not render result boards in ASCII-art.
  -p, --profile         Produce a profiling graph.
  --queen INTEGER       Number of queens.
  --king INTEGER        Number of kings.
  --rook INTEGER        Number of rooks.
  --bishop INTEGER      Number of bishops.
  --knight INTEGER      Number of knights.
  --help                Show this message and exit.

Benchmark specific options:

$ chessboard benchmark --help
Usage: chessboard benchmark [OPTIONS]

  Run a benchmarking suite and measure time taken by the solver.

  Each scenario is run in an isolated process, and results are appended to
  CSV file.

Options:
  --help  Show this message and exit.

Plotting specific options:

$ chessboard plot --help
Usage: chessboard graph [OPTIONS]

  Update all kind of performance graphs from the benchmark data.

  All data come from CSV database.

Options:
  --help  Show this message and exit.

Examples

Simple 3x3 board with 2 kings and a rook:

$ chessboard solve --length=3 --height=3 --king=2 --rook=1
<SolverContext: length=3, height=3, pieces={'rook': 1, 'king': 2, 'queen': 0, 'bishop': 0, 'knight': 0}>
Searching positions...
┌───┬───┬───┐
│ ♚ │   │   │
├───┼───┼───┤
│   │   │ ♜ │
├───┼───┼───┤
│ ♚ │   │   │
└───┴───┴───┘
┌───┬───┬───┐
│   │   │ ♚ │
├───┼───┼───┤
│ ♜ │   │   │
├───┼───┼───┤
│   │   │ ♚ │
└───┴───┴───┘
┌───┬───┬───┐
│ ♚ │   │ ♚ │
├───┼───┼───┤
│   │   │   │
├───┼───┼───┤
│   │ ♜ │   │
└───┴───┴───┘
┌───┬───┬───┐
│   │ ♜ │   │
├───┼───┼───┤
│   │   │   │
├───┼───┼───┤
│ ♚ │   │ ♚ │
└───┴───┴───┘
4 results found in 0.03 seconds.

Famous eight queens puzzle, without printing the solutions to speed things up:

$ chessboard solve --length=8 --height=8 --queen=8 --silent
<SolverContext: length=8, height=8, pieces={'rook': 0, 'king': 0, 'queen': 8, 'bishop': 0, 'knight': 0}>
Searching positions...
92 results found in 119.87 seconds.

Huge combinatoric problem can take some time to solve:

$ chessboard solve --length=7 --height=7 --king=2 --queen=2 --bishop=2 --knight=1 --silent
<SolverContext: length=7, height=7, pieces={'rook': 0, 'king': 2, 'queen': 2, 'bishop': 2, 'knight': 1}>
Searching positions...
3063828 results found in 9328.33 seconds.

The CLI allow the production of a profiling graph, to identify code hot spots and bottleneck:.

$ chessboard solve --length=6 --height=6 --king=2 --queen=2 --bishop=2 --knight=1 --silent --profile
<SolverContext: length=6, height=6, pieces={'rook': 0, 'king': 2, 'queen': 2, 'bishop': 2, 'knight': 1}>
Searching positions...
23752 results found in 207.25 seconds.
Execution profile saved at /home/kevin/chessboard/solver-profile.png

Performances

Results below are given in seconds, and were run with the --silent option.

To run the standard benchmark suite and add results to the database, run the benchmark in a detached background process:

$ nohup chessboard benchmark > /dev/null 2>&1 &

N-queens problem solving time:

Stability policy

Here is a bunch of rules we’re trying to follow regarding stability:

• Patch releases (0.x.n → 0.x.(n+1) upgrades) are bug-fix only. These releases must not break anything and keeps backward-compatibility with 0.x.* and 0.(x-1).* series.

• Minor releases (0.n.* → 0.(n+1).0 upgrades) includes any non-bugfix changes. These releases must be backward-compatible with any 0.n.* version but are allowed to drop compatibility with the 0.(n-1).* series and below.

• Major releases (n.*.* → (n+1).0.0 upgrades) are not planned yet, unless we introduce huge changes to the project.

Third-party

This project package’s boilerplate is sourced from the code I wrote for Scaleway’s postal-address module, which is published under a GPLv2+ License.

The CLI code is based on the one I wrote for the kdenlive-tools module, published under a BSD license.

Other resources

• Combinatorial Generation

• Applied Combinatorics

• Extremal Problems

License

This software is licensed under the GNU General Public License v2 or later (GPLv2+).

1.5.0 (2016-07-01)

• Add default isort configuration.

• Add more trove classifiers.

• Add proper support of logging. Closes #2.

• Use Miniconda to install numpy, scipy, matplotlib and pandas in Travis builds.

• Activate unittests in Python 3.3, 3.4 and 3.5. Closes #9.

• Activate unittests on OSX.

• Get detailed CPU info for each benckmark.

• Add sphinx-based documentation.

• Use pip to install package and other extra dependencies.

• Add a git mailmap template.

1.4.0 (2015-11-23)

• Make the solver into a CLI sub-command.

• Pythonize benchmarking and include it as a CLI sub-command.

• Plot n-queens graph from benchmark data.

• Switch from coveralls.io to codecov.io.

1.3.0 (2015-09-06)

• Only compute 2D coordinates of each piece instance when needed, so we can reach immediately the cache if we’re only interested by the territory. Adds a 1.21x speedup.

• Add custom PEP8 configuration.

• Add custom Pylint configuration.

1.2.0 (2015-09-03)

• Pre-compute some Board properties. Adds a 1.12x speedup.

• Reuse Board object. Adds a 1.06x speedup.

• Use list of boolean instead of bytearray for states in Board. Adds a 1.11x speedup.

• Add a little benchmark suite.

1.1.0 (2015-08-28)

• Use bytearray to represent board states. Closes #4.

• Cache piece territories to speed solver up to 3x on board with big population of pieces.

1.0.0 (2015-08-27)

• Do not spend time converting back and forth linear position to 2D position. Provides a 1.16x speedup.

• Proceed permutation exploration with pieces of biggest territory coverage first. Adds 16x speed-up. Closes #5.

• Add support for bumpversion.

• Add new --profile option to produce an execution profile of the solver.

0.9.1 (2015-08-25)

• Fix rendering of unicode string in terminal.

• Document stability policy and release process.

• Add PyPi-based badges.

0.9.0 (2015-08-25)

• Validate CLI user inputs and provides hints.

• Abandon branches of the search space as soon as possible. Closes #3.

• Deduplicate per-kind piece group permutations early. Closes #7.

• Add --silent option to skip displaying of all board results in ASCII art.

0.8.0 (2015-08-15)

• Refactor solver to deduplicate positions by kind (combination) before iterating the search space by brute force (cartesian product).

0.7.0 (2015-08-14)

• Display results in unicode-art.

0.6.0 (2015-08-14)

• Add Knight model.

0.5.0 (2015-08-13)

• Add Rook and Bishop models.

• Allow overlapping but non-threatening territory of pieces to co-exists.

0.4.0 (2015-08-13)

• Add project status badges.

• Enable continuous integration metrics: build status, coverage and code quality.

• Fix index to position computation in non-square boards.

• Remove restriction on board dimensions.

• Unit-tests result sets produced by the solver.

0.3.0 (2015-08-12)

• Add Queen piece.

• Fix displaying of piece representation.

• Fix persistence of square occupancy between each piece addition.

0.2.1 (2015-08-11)

• Fix King displacement map.

0.2.0 (2015-08-11)

• Allow initialization of board pieces.

• Implement brute-force solver.

0.1.1 (2015-08-08)

• Package re-release to fix bad version number.

0.1.0 (2015-08-08)

• First public release.

• Implements a CLI to inititalize the chessboard.

0.0.0 (2015-08-08)

• First commit.