New Rust Chess Library

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
jordanbray
Posts: 51
Joined: Mon Aug 11, 2014 1:01 am

New Rust Chess Library

Post by jordanbray » Wed Nov 30, 2016 3:46 am

Hey all,

I've developed a new open source chess move generation library in rust! This aims to be a fast move generator, where many people can share the move generation code. It is under the very permissive MIT license.

It uses magic bitboards for move generation, has all the usual suspects when it comes to move generation optimizations (pinned pieces, whether or not you're in check during generation, etc). It can enumerate pseudo_legal or legal moves, and a board.legal_quick(...) function to check pseudo_legal moves generated by the structure, without the full cost of the board.legal(...) function.

There are two move generators, actually. One gives you a rust Iterator<> which will use incremental move generation (but is slightly slower for perft testing), the other will give you an array (of size 256) for all legal chess moves, and is a bit faster.

It uses copy-on-make, which is easier to implement (and consistent with the rust style), and I've made the board structure as small as possible to prevent overhead during copying. (Additionally, rust will *not* copy the board if it doesn't have to). No mailboxing :).

It has nice structures for ranks, files, squares, etc, all of which are designed to be optimized down efficiently by the rust compiler.

It has an incrementally updated pawn_hash() and a full board hash() for trasposition tables. It also has a CacheTable<T> which acts as a general purpose transposition table, designed for chess engine use (AKA: much faster than a HashMap<>). These features are tested with perft().

It has unit tests for perft testing.

You can download it using the rust 'cargo' package manager here: https://crates.io/crates/chess.

Documentation is available here: https://jordanbray.github.io/chess/chess/index.html

Source code is available here: https://github.com/jordanbray/chess

Some perft results are available here: https://github.com/jordanbray/chess_perft

Example of running a perft test:

Code: Select all

&#91;jordan@localhost ~&#93;$ cargo install chess_perft
    Updating registry `https&#58;//github.com/rust-lang/crates.io-index`
   Compiling getopts v0.2.14
   Compiling lazy_static v0.2.2
   Compiling libc v0.2.17
   Compiling bitflags v0.7.0
   Compiling rand v0.3.15
   Compiling chess v0.3.4
   Compiling chess_perft v0.0.7
    Finished release &#91;optimized&#93; target&#40;s&#41; in 14.45 secs
  Installing /home/jordan/.cargo/bin/chess_perft
warning&#58; be sure to add `/home/jordan/.cargo/bin` to your PATH to be able to run the installed binaries
&#91;jordan@localhost ~&#93;$ chess_perft -f "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" -d 5 -m # Test the KiwiPete Position
Perft 5 of r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
Result&#58; 193690690, Time&#58; 1s 561ms
&#91;jordan@localhost ~&#93;$
Thanks,
Jordan

mkchan
Posts: 83
Joined: Thu Oct 06, 2016 7:17 pm
Location: India
Contact:

Re: New Rust Chess Library

Post by mkchan » Wed Nov 30, 2016 6:52 am

Looks great! Now I finally have an incentive to study rust :D

abulmo
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: New Rust Chess Library

Post by abulmo » Wed Nov 30, 2016 10:39 am

jordanbray wrote:I've developed a new open source chess move generation library in rust! This aims to be a fast move generator.

Code: Select all

$ chess_perft -f "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" -d 5 -m # Test the KiwiPete Position
Perft 5 of r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
Result&#58; 193690690, Time&#58; 1s 561ms
This is slow. On my computer, the best result I get his:
Result: 193690690, Time: 1s 35ms

My own program, although not particularly fast, is 20% faster:

Code: Select all

$ amoeba perft -f "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" -d 5
perft 5&#58; 193690690 leaves in 0.849s &#40;228040418 leaves/s&#41;
And If I measure the whole execution time, the difference is larger, about 3.6s for your chess_perft against 0.87s for amoeba; probably due to the initialization of the magic tables (My program do not use them).

I am not a fan of the rust language either. Its syntax is hard to read, and it is not always easy to find the algorithm behind the code. I will stick to the D language, which allows me to write readable and fast code.
Richard

mar
Posts: 2001
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: New Rust Chess Library

Post by mar » Wed Nov 30, 2016 2:33 pm

abulmo wrote:I will stick to the D language, which allows me to write readable and fast code.
Until GC triggers.

Readability depends on a lot of factors and mostly on personal preference.

Funny btw that you use a bucket size of 4 but you don't cache-align TT.

jordanbray
Posts: 51
Joined: Mon Aug 11, 2014 1:01 am

Re: New Rust Chess Library

Post by jordanbray » Wed Nov 30, 2016 11:31 pm

These two give very similar performances for me. I'm using ldc2 as the D compiler. Should i have done something different during compilation?

Keep in mind the -m parameter to chess_perft uses an incremental move generator. You can remove the -m parameter for a very minor speed improvement (On the order of .1 seconds on my machine).

Code: Select all

&#91;jordan@localhost src&#93;$ time !!
time ./amoeba perft -f "r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" -d 5 
  a b c d e f g h
8 r . . . k . . r 8
7 p . p p q p b . 7
6 b n . . p n p . 6
5 . . . P N . . . 5
4 . p . . P . . . 4
3 . . N . . Q . p 3
2 P P P B B P P P 2
1 R . . . K . . R 1
  a b c d e f g h
w KQkq move 1, fifty 0 &#91;K&#58;e1, k&#58;e8&#93;

perft  5 &#58;       193690690 leaves in      1.427 s    135778708 leaves/s

real    0m1.481s
user    0m1.477s
sys    0m0.000s

jordanbray
Posts: 51
Joined: Mon Aug 11, 2014 1:01 am

Re: New Rust Chess Library

Post by jordanbray » Wed Nov 30, 2016 11:38 pm

I wonder if your machine is just much faster than mine! It probably is. If you have time, try chess_perft without the -m parameter and see how fast it is.

Additionally, one of the goals of this project is to create one place for optimization, so there aren't 50 chess move generators for rust. Just one really, really good one (eventually). :)

Thanks for the feedback

abulmo
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: New Rust Chess Library

Post by abulmo » Thu Dec 01, 2016 12:12 am

mar wrote:
abulmo wrote:I will stick to the D language, which allows me to write readable and fast code.
Until GC triggers.
GC impact is negligible on my program, according to a profiler:

Code: Select all

   0,00%  libc-2.23.so      &#91;.&#93; __memcpy_sse2_unaligned
   0,00%  libc-2.23.so      &#91;.&#93; malloc
   0,00%  amoeba            &#91;.&#93; nothrow ulong gc.gc.Gcx.sweep&#40;)
   0,00%  amoeba            &#91;.&#93; nothrow uint gc.gc.GC.getAttr&#40;void*)
   0,00%  amoeba            &#91;.&#93; nothrow ulong gc.gc.GC.sizeOf&#40;void*)
Readability depends on a lot of factors and mostly on personal preference
Right, it was just my opinion.
Funny btw that you use a bucket size of 4 but you don't cache-align TT.
I don't because I could not measure any speedup by aligning the TT on my machine.
Richard

abulmo
Posts: 151
Joined: Thu Nov 12, 2009 5:31 pm
Contact:

Re: New Rust Chess Library

Post by abulmo » Thu Dec 01, 2016 12:49 am

jordanbray wrote:I wonder if your machine is just much faster than mine! It probably is. If you have time, try chess_perft without the -m parameter and see how fast it is.

Code: Select all

without -m&#58; Result&#58; 193690690, Time&#58; 1s 37ms
with -m&#58;    Result&#58; 193690690, Time&#58; 1s 53ms
My computer is powered by a 6 year old 2600k @ 4Ghz. Fast, but there is faster cpu todays.
Additionally, one of the goals of this project is to create one place for optimization, so there aren't 50 chess move generators for rust. Just one really, really good one (eventually). :)
I hope I have not been unpleasant. Sharing your code is great and I hope it will helps other people developing chess engine in Rust.
Richard

jordanbray
Posts: 51
Joined: Mon Aug 11, 2014 1:01 am

Re: New Rust Chess Library

Post by jordanbray » Thu Dec 01, 2016 2:04 am

abulmo wrote:My computer is powered by a 6 year old 2600k @ 4Ghz. Fast, but there is faster cpu todays.
Yup. Definitely faster than my FX8120. I wonder if you are getting performance improvements from SSE or maybe the inline popcnt (which, I'm not 100% sure I'm using yet).
I hope I have not been unpleasant. Sharing your code is great and I hope it will helps other people developing chess engine in Rust.
Not at all. I'm happy to have any feedback. I only tested mine against stockfish, and noted mine was faster (again, on my machine). That said, I'm sure there are more optimizations to be done.

It's clear that CPU tuning will be a part of this project, now, which was not at all on my radar before.

Post Reply