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

Development philosophy

1. First create something that work (to provide business value).

2. Then something that’s beautiful (to lower maintenance costs).

3. Finally works on performance (to avoid wasting time on premature optimizations).

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:

Development

Check out latest development branch:

$ git clone git@github.com:kdeldycke/chessboard.git
$ cd ./chessboard
$ python ./setup.py develop

Run unit-tests:

$ python ./setup.py nosetests

Run PEP8 and Pylint code style checks:

$ pip install pep8 pylint
$ pep8 chessboard
$ pylint --rcfile=setup.cfg chessboard

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: we’re still in beta and the final feature set of the 1.0.0 release is not decided yet.

Release process

Start from the develop branch:

$ git clone git@github.com:kdeldycke/chessboard.git
$ git checkout develop

Revision should already be set to the next version, so we just need to set the released date in the changelog:

$ vi ./CHANGES.rst

Create a release commit, tag it and merge it back to master branch:

$ git add ./chessboard/__init__.py ./CHANGES.rst
$ git commit -m "Release vX.Y.Z"
$ git tag "vX.Y.Z"
$ git push
$ git push --tags
$ git checkout master
$ git pull
$ git merge "vX.Y.Z"
$ git push

Push packaging to the test cheeseshop:

$ pip install wheel
$ python ./setup.py register -r testpypi
$ python ./setup.py clean
$ rm -rf ./build ./dist
$ python ./setup.py sdist bdist_egg bdist_wheel upload -r testpypi

Publish packaging to PyPi:

$ python ./setup.py register -r pypi
$ python ./setup.py clean
$ rm -rf ./build ./dist
$ python ./setup.py sdist bdist_egg bdist_wheel upload -r pypi

Bump revision back to its development state:

$ pip install bumpversion
$ git checkout develop
$ bumpversion --verbose patch
$ git add ./chessboard/__init__.py ./CHANGES.rst
$ git commit -m "Post release version bump."
$ git push

Now if the next revision is no longer bug-fix only:

$ bumpversion --verbose minor
$ git add ./chessboard/__init__.py ./CHANGES.rst
$ git commit -m "Next release no longer bug-fix only. Bump revision."
$ git push

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.

License

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

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.