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

$ chessboard --help
Usage: chessboard [OPTIONS]

  Python CLI to explore chessboard positions.

Options:
  --version             Show the version and exit.
  -l, --length INTEGER  Length of the board.  [required]
  -h, --height INTEGER  Height of the board.  [required]
  -s, --silent          Do not display result board, only final count.
  -v, --verbose         Print much more debug statements.
  -p, --profile         Produce a profiling graph.
  --rook INTEGER        Number of rooks to add to the board.
  --knight INTEGER      Number of knights to add to the board.
  --queen INTEGER       Number of queens to add to the board.
  --bishop INTEGER      Number of bishops to add to the board.
  --king INTEGER        Number of kings to add to the board.
  --help                Show this message and exit.

Examples

Simple 3x3 board with 2 kings and a rook:

$ chessboard --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 --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 --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 --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 /homr/kevin/chessboard/solver-profile.png

Performances

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

Results from the table above came from running the benchmark.sh script in a detached background process:

$ nohup ./benchmark.sh > benchmark.out 2> benchmark.err < /dev/null &
$ tail -F benchmark.out

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