Scheme-based TreE EvaLuating Engine for Chess.
The goal of this project is to produce an elegant and readable chess engine in R7RS scheme. Performance is secondary.
This project is part of my Analog Sprint. I am trying to remove this dependence on LLMs via analog sprints like this. This project will not have any LLM generated code.
The overall design I have in mind is a simple minimax alpha-beta pruning chess engine a la Sebastian Lague.
I wrote a chess engine based on the above video in ASP.NET Blazor WebAssembly back in 2022 called Chessnovert. This could be the spiritual scheme successor to that.
Initially I wanted to call this “check/cc” – check with current continuation, but github (and any system really) does not play well with slashes in names, so I went with “steele” which is a backronym that stands for Scheme-based TreE EvaLuating Engine and of course, also the name of one of the creators of scheme who I hear is fond of chess.
- Chibi Scheme
- For its robust R7RS support.
- Cyclone Scheme
- For compilation to native binary.
- Minimax Algorithm
- Just like Chessnovert.
- UCI
- For interfacing with boards such as xboard.
.
├── LICENSE
├── README.org
├── Makefile
├── src
│ ├── main.scm # main entrypoint
│ └── steele # libraries (steele foo)
│ ├── board.scm
│ ├── board.sld
│ ├── engine.scm
│ ├── engine.sld
│ ├── rules.scm
│ ├── rules.sld
│ ├── utils.scm
│ └── utils.sld
└── tests # tests for each lib
├── board.scm
├── engine.scm
└── rules.scm
From the project root, run the following:
chibi-scheme -I src src/main.scmIf you have cyclone, you can compile this into a native binary and then run it. It is about 10x faster than chibi-scheme.
# compile the main executable
make
# run
./steeleRun an individual test file with either chibi or cyclone. For example:
# chibi
chibi-scheme -Isrc tests/engine.scm
# cyclone
cyclone -I src/ tests/rules.scm
./tests/rulesOr else, compile and run all tests with cyclone. This is much faster.
make testYou can install and uninstall using make. PREFIX and DESTDIR configurable.
# Install
sudo make install
# Uninstall
sudo make uninstallThis project is a learning exercise, currently in the initial stages of development.
The predicates valid-*-move? check whether a move obeys the normal
rules of movement of a piece. The pseudo-legal-move? predicate is
the dispatch for valid-*-move?.
The legal-move? predicate provides the full legality check for a move.
The minimax engine is found in engine.scm. It uses a negamax algorithm based on the one from the Sebastian Lague video but written with scheme idioms like the immutable board and tail-recursive calls.
Not implemented yet.
Not implemented yet.
Not implemented yet.
Work in progress.
Tests are located in the tests/ directory. Each lib (utils, rules
etc) gets an isolated test file. These should be run separately as
some of them (like tests/engine.scm) can take a long time to run.
Not implemented yet.
The performance is horrendous as expected. This is because the board is immutable and has to be copied for every branch of the minimax tree. I hoped I could use posix threads if the board was immutable but that is a later concern.
On cyclone scheme (native binary) on my 2018 Ideapad 330s:
perft depth 1 20 0.000863seconds perft depth 2 400 0.020688seconds perft depth 3 8902 0.380149seconds perft depth 4 197281 8.781418seconds perft depth 5 4865351 184.580871seconds
Of course, the depth 5 number is wrong because en passant is not implemented yet.
This code is licensed under AGPL-3.0, the text for the license may be found in LICENSE.