#chess #move #generator

chess

This is a fast chess move generator. It has a very good set of documentation, so you should take advantage of that. It (now) generates all lookup tabels with a build.rs file, which means that very little pseudo-legal move generation requires branching. There are some convenience functions that are exposed to, for example, find all the squares between two squares. This uses a copy-on-make style structure, and the Board structure is as slimmed down as possible to reduce the cost of copying the board. There are places to improve perft-test performance further, but I instead opt to be more feature-complete to make it useful in real applications. For example, I generate both a hash of the board and a pawn-hash of the board for use in evaluation lookup tables (using Zobrist hashing). There are two ways to generate moves, one is faster, the other has more features that will be useful if making a chess engine. See the documentation for more details.

33 releases (14 stable)

✓ Uses Rust 2018 edition

new 3.0.2 May 15, 2019
3.0.1 Jan 16, 2019
2.0.2 Dec 22, 2018
2.0.1 Oct 29, 2018
0.2.0 May 29, 2016

#17 in Game development

Download history 4/week @ 2019-01-29 7/week @ 2019-02-05 8/week @ 2019-02-12 4/week @ 2019-02-19 70/week @ 2019-02-26 35/week @ 2019-03-05 6/week @ 2019-03-12 42/week @ 2019-03-19 98/week @ 2019-03-26 35/week @ 2019-04-02 5/week @ 2019-04-09 10/week @ 2019-04-16 37/week @ 2019-04-23 41/week @ 2019-04-30 44/week @ 2019-05-07

155 downloads per month
Used in 1 crate

MIT license

171KB
3.5K SLoC

A Fast Chess Library In Rust

Build Status crates.io

This library handles the process of move generation within a chess engine or chess UI.

This library is follows semver for version numbering in the format MAJOR.MINOR.PATCH. That means:

  • Any change to the API that breaks existing code will involve a MAJOR version number change.
  • Any added functionality or features that do not break existing applications will involve a MINOR version number change.
  • Any bug fixes or performance improvements that do not affect users will involve a PATCH version change.

Requires Rust 1.31 or Greater

This library requires rust version 1.27 or greater in order to check for the BMI2 instruction-set at compile-time. Additionally, this build is compatible with rust 2018 which, I believe, requires rust 1.31.

Note: bmi2 has been disabled due to horrible performance on AMD architectures. I have instead opted to expose the two relevant functions publicly if on a bmi2 CPU.

Examples

Simple Move Generation

This puts all moves into a static array. An array is used instead of a Vec to keep the moves on the stack, and to allow reuse of the array (which has a big impact on performance).

  use chess::{Board, ChessMove};

  let board = Board::default();
  let mut moves = [ChessMove::default(); 256];
  let count = board.enumerate_moves(&mut moves);
  assert_eq!(count, 20);

Incremental Move Generation With Capture/Non-Capture Sorting

Here we iterate over all moves with incremental move generation. The iterator below will generate moves as you are going through the list, which is ideal for situations where not all moves will be looked at (such as in an engine search function).

  use chess::MoveGen;
  use chess::Board;
  use chess::EMPTY;

  // create a board with the initial position
  let board = Board::default();

  // create an iterable
  let mut iterable = MoveGen::new(board, true);

  // make sure .len() works.
  assert_eq!(iterable.len(), 20); // the .len() function does *not* consume the iterator

  // lets iterate over targets.
  let targets = board.color_combined(!board.side_to_move());
  iterable.set_iterator_mask(targets);

  // count the number of targets
  let mut count = 0;
  for _ in &mut iterable {
      count += 1;
      // This move captures one of my opponents pieces (with the exception of en passant)
  }

  // now, iterate over the rest of the moves
  iterable.set_iterator_mask(!EMPTY);
  for _ in &mut iterable {
      count += 1;
      // This move does not capture anything
  }

  // make sure it works
  assert_eq!(count, 20);

Making a Move

Here we make a move on the chess board. The board is a copy-on-make structure, meaning every time you make a move, you create a new chess board. The board structure is optimized for size to reduce copy-time.

  use chess::{Board, ChessMove, Square, Rank, File, Color};

  let m = ChessMove::new(Square::make_square(Rank::Second, File::D),
                         Square::make_square(Rank::Fourth, File::D),
                         None);

  let board = Board::default();
  assert_eq!(board.make_move_new(m).side_to_move(), Color::Black);

Compile-time Options

When compiling, I definitely recommend using RUSTFLAGS="-C target-cpu=native", specifically to gain access to the popcnt and ctzl instruction available on almost all modern CPUs. This is used internally to figure out how many pieces are on a bitboard, and what square a piece is on respectively. Because of the type system used here, these tasks become literally a single instruction. Additionally, BMI2 is enabled on machines with the instructions by using this flag.

BMI2

As of version 1.0.3 of this library, the BMI2 instruction-set is used on machines that support it. This speeds up the logic in two ways:

  • It uses built-in instructions to do the same logic that magic bitboards do.
  • It reduces cache load by storing moves in a u16 rather than a u64, which can be decompressed to a u64 with a single instruction.

On targets without BMI2, the library falls back on magic bitboards. This is checked at compile-time.

Shakmaty

Another rust chess library is in the 'shakmaty' crate. This is a great library, with many more features than this one. It supports various chess variants, as well as the UCI protocol. However, those features come at a cost, and this library performs consistently faster in all test cases I can throw at it. To compare the two, I have added 'shakmaty' support to the 'chess_perft' application, and moved a bunch of benchmarks to that crate. You can view the results at https://github.com/jordanbray/chess_perft.

What It Does

This library allows you to create a chess board from a FEN-formatted string, list all legal moves for the chess board and make moves.

This library also allows you to view various pieces of board-state information such as castle rights.

This library has very fast move generation (the primary purposes of its existance), which will be optimized more. All the tricks to make chess move generation fast are used.

What It Does Not Do

This is not a chess engine, just the move generator. This is not a chess UI, just the move generator. This is not a chess PGN parser, database, UCI communicator, XBOARD/WinBoard protocol, website or grandmaster. Just a humble move generator.

API Documentation

... is available at http://jordanbray.github.io/chess/.

Anything Else

Nope. Have fun.

Dependencies

~144KB

  • build build.rs
  • build rand 0.4.2