Progress on Rustic

[mvanthoor]

On sept 19 I posted that I implemented message passing between threads.

Now I have an active communication module (in its own thread) that reads incoming stuff from stdin. There are three modules:

- console (this is the only one implemented now)
- uci
- xboard

The incoming stuff is transformed into something the engine understands. It means that the consoel, uci and xboard modules all translate incoming data to the same format. The engine sends data into the modules, and each translates it for its own use, in either the console, uci, and xboard protocol, and outputs it to STDOUT

It's more work than just interweaving uci throughout the entire engine and be done with it, but this way, the engine can support any current and future protocol by just writing a new module for it.

So far so good.

I also wanted to have a Search that acts as a main controller in its own thread. For now, the search will run directly in that thread, but later, this concept can be extended by having worker threads attached to the controller. (So the engine can send "Start" and "Stop" to the controller, and it starts and stops the search accordingly. Or it quits all workers and itself completely when it receives "Quit".)

Again, so far so good. Working fine...

But now I end up with two message receivers in my engine:

comm_rx receives messages from the communication module.
search_rx receives (intermediate) results from the search controller.

So now I have the problem that I have TWO blocking receivers in the engine's main thread, and the thread won't continue until BOTH are unblocked. I don't want non-blocking reception, because that entails polling, and thus the main engine thread will be active all the time.

Enter "select!"

Rust has a construct that is able to unblock a thread, as soon as one of the waiting receivers gets a message. The thread continues, so the message in the receiver can be handled, and then the thread blocks again. Great. That's what I need.

And then they go and deprecate this functionality because it's written in unsafe code a few years ago, and they don't have a replacement yet.

QUE?!

So since Rust 1.32, the language has no "official" way of handling more than one receiver in a thread, and there are multiple competing implementations by several people and project groups. It was actually suggested to just rip all the channels out of the standard library, in the ongoing effort to keep it as small as possible. (Then why not dispense with it entirely?! Sjeess...)

The solution, apparently, is to use "crossbeam-channel", part of the "crossbeam" crate.

Now some people want to throw out Rust's entire threading API out of the standard library, and replace it with crossbeam. Then there's also mio, Tokio, std-async, Futures (both a version in the standard library, and a crate called Futures), chan, and new-channel and probably others.

Why doesn't Rust learn from Javascript and C++, in heaven's sake?

C++ had a fairly small standard library, but since some time, Boost is basically required as an addition. Therefore at some point, C++ acquired the same functionality as Boost in the standard library, and if I remember correctly, it even just takes parts of Boost INTO the standard library.

Same with Javascript. jQuery became so omnipresent, that Javascript ES6 is basically a re-implementation of jQuery's functionality directly into the language itself. jQuery, by all intents and purposes, is now subsumed and outdated.

Why doesn't Rust do the same thing? Implement a small, working feature in the standard library that people can use. If an implementation comes along that is used by MILLIONS, to the extent that it actually becomes the de facto default, it SHOULD replace the functionality in the standard library, officially. But no, Rust still wants to have a tiny standard library, and on crates.io, people and entire project groups keep fighting to make their implementation the dominant one. So in time, we'll have 75 ways of doing one thing in Rust.

And yes, I'm now basically forced to pull another huge dependency into my engine to get one tiny threading feature, that was available but isn't anymore (or isn't going to be, in the near future).

Maybe Rust needs to become a lot older (It's 10 years old, but only at version 1.0 for about 5), and much more heavily used in companies. At that point, you can't get away with stuff like that; somehow they WILL have to give their mandate on what crates are "officially maintained" by the Rust foundation (and thus can be considered 'standard'), because multi-billion dollar companies are not going to build their programs on top of a crate created by John Doe down the street.

[fabianVDW]

I also wanted to have a Search that acts as a main controller in its own thread. For now, the search will run directly in that thread, but later, this concept can be extended by having worker threads attached to the controller. (So the engine can send "Start" and "Stop" to the controller, and it starts and stops the search accordingly. Or it quits all workers and itself completely when it receives "Quit".)

Again, so far so good. Working fine...

But now I end up with two message receivers in my engine:

comm_rx receives messages from the communication module.
search_rx receives (intermediate) results from the search controller.

So now I have the problem that I have TWO blocking receivers in the engine's main thread, and the thread won't continue until BOTH are unblocked. I don't want non-blocking reception, because that entails polling, and thus the main engine thread will be active all the time.

Enter "select!"

Rust has a construct that is able to unblock a thread, as soon as one of the waiting receivers gets a message. The thread continues, so the message in the receiver can be handled, and then the thread blocks again. Great. That's what I need.

And then they go and deprecate this functionality because it's written in unsafe code a few years ago, and they don't have a replacement yet.

QUE?!

So since Rust 1.32, the language has no "official" way of handling more than one receiver in a thread, and there are multiple competing implementations by several people and project groups. It was actually suggested to just rip all the channels out of the standard library, in the ongoing effort to keep it as small as possible. (Then why not dispense with it entirely?! Sjeess...)

The solution, apparently, is to use "crossbeam-channel", part of the "crossbeam" crate.

This is fine, because you don't actually need more than one receiver in this case. Remember that you can have more than one sender. Just make the information you send a wrapper like this

Code: Select all

pub enum Information{
Comm(CommInformation),
Search(SearchInformation)
}

and then you can have one

Code: Select all

receiver_rx : Receiver<Information>

Not sure if this is a workaround or how it's usually done, but I think it is quite elegant, more so than having two receivers for this special case.

Now some people want to throw out Rust's entire threading API out of the standard library, and replace it with crossbeam. Then there's also mio, Tokio, std-async, Futures (both a version in the standard library, and a crate called Futures), chan, and new-channel and probably others.

Why doesn't Rust learn from Javascript and C++, in heaven's sake?

C++ had a fairly small standard library, but since some time, Boost is basically required as an addition. Therefore at some point, C++ acquired the same functionality as Boost in the standard library, and if I remember correctly, it even just takes parts of Boost INTO the standard library.

Same with Javascript. jQuery became so omnipresent, that Javascript ES6 is basically a re-implementation of jQuery's functionality directly into the language itself. jQuery, by all intents and purposes, is now subsumed and outdated.

Why doesn't Rust do the same thing? Implement a small, working feature in the standard library that people can use. If an implementation comes along that is used by MILLIONS, to the extent that it actually becomes the de facto default, it SHOULD replace the functionality in the standard library, officially. But no, Rust still wants to have a tiny standard library, and on crates.io, people and entire project groups keep fighting to make their implementation the dominant one. So in time, we'll have 75 ways of doing one thing in Rust.

This has been discussed countless of times already, so If you want some good arguments for why it stays how it stays, you can google for it.
Here are a few links to get you started


https://users.rust-lang.org/t/rust-shou ... hy/37449/3

[mvanthoor]

Thanks for the tips, Fabian I've resolved everything already, after some tinkering, jacking around, and breaking stuff a few times. The trick is to pass senders into functions/threads you want to be able to send things (and keep the receiver), or to create a channel in the function/thread, and return the sender (and again, keep the receiver).

It seems it is best to work with tiny parts in Rust, or you'll get into problems. Fortunately cross-beam supports select!, so I can have the main loop wait for incoming stuff from both Search and Comm.

My comm module now actually has TWO threads:

- One control thread that listens for incoming commands (up to now, only Quit and Update. Obviously Quit makes the module quit, and Update can be used to request information from the engine. My console UI needs this to print the board, or its printing will run though the output of Search.)
- One reader thread that reads from Stdin, transforms the incoming data (from console, uci or xboard) into a CommReport, and sends it off to the engine. This thread will send CommReport::Quit as soon as "quit" or "exit" are detected, and then close.

Search works the same way: one control thread, and one search thread (I'm thinking about making it a worker already, and just use one for now; and figure out multi-threaded search / Lazy SMP MUCH later.) search receives "SearchControl" commands from the engine, and sends "SearchReports", which the engine can then output through the comm module. (And each comm module will obviously convert a SearchReport for use on the console, uci, or xboard.)

it's quite a lot of work to do it in a completely modular fashion, but I feel that, after the infrastructure is in place, extending the engine with SMP search and (if ever needed, new protocols/server connection stuff, etc) will be a lot easier.

And I just don't like to interweave stuff. I don't see a reason why "Search" needs to know anything about "UCI" or "Xboard" or the other way around... and I also don't see a reason why the main engine loop should be concerned with the fact if its SearchReports are created by 1 thread or 64 threads.

With regard to the standard library... I know. As you might have guessed, I'm against using lots of dependencies (especially if they need to be downloaded during compilation), and against a tiny STD which will make the community create 500 ways of doing one thing; and if you choose the wrong way, you might end up with an abandoned crate on which your program heavily depends.

I take about as much time to research crates and modules, than actually using them. I'm very conservative with the crates I pull into the engine (but sometimes, crates themselves are not conservative with THEIR dependencies... CLAP, for example, is HUGE.)

[mvanthoor]

This is fine, because you don't actually need more than one receiver in this case. Remember that you can have more than one sender. Just make the information you send a wrapper like this

Code: Select all

pub enum Information{
Comm(CommInformation),
Search(SearchInformation)
}

and then you can have one

Code: Select all

receiver_rx : Receiver<Information>

Not sure if this is a workaround or how it's usually done, but I think it is quite elegant, more so than having two receivers for this special case.

I've thought about this, but in this solution, it is necessary to lump Comm and Search information together. I wanted to keep all the parts of the chess engine completely separate, where the active main_loop() part sits at the center, controlling the active Comm and Search objects, issuing commands and sharing information and data where necessary.

Therefore, it feels more logical to just have two receivers: one for Comm, one for Search, with the main loop waiting until one of them is activated. The main loop then does whatever it has to do depending on the received command or information, and then goes back to waiting.

(This is the same way a PLC would connect several parts of a big machine to one another.)

[mvanthoor]

Ah, drat... about select! :

Selects from a set of channel operations.

This macro allows you to define a set of channel operations, wait until any one of them becomes ready, and finally execute it. If multiple operations are ready at the same time, a random one among them is selected.

Nice... so if it happens that TWO messages are sent at exactly the same time and both the receiver for Comm _and_ Search become ready at the same time, then select! is going to execute one at random... and what about the other? Is it executed on the next pass, or dropped forever? Can't find any information.

It seems that I'll HAVE to create "Information" wrapper so I can work with only one receiver... though I still think it's not the greatest solution.

[mvanthoor]

Rustic's communication infrastructure has been implemented.

It is now able to receive information from, and write information to, its comm modules. It can also start and stop its search module, and it is already prepared for a future where the search module will have more than one worker (and thus will implement SMP.) The engine can now receive moves from outside (in this case, console; but obviously also UCI and Xboard after I implement those modules.)

The console comm module is very useful for building and testing new functions, because nothing else is in the way. If a new function is not fully working, it's because there's something wrong with the function; and I don't have to worry that either the UCI or Xboard protocol implementations are the problem.

(Obviously, the engine checks incoming moves for legality; even though a GUI probably will never send an illegal move through UCI or Xboard, I don't want the engine to just crash when I put something weird into the console.)

Next week I'll be implementing a brute force min-max search, to get that finished quickly; then I'll be able to play a game through the console. It'll probably play horrible, but that doesn't matter. When it works, I can implement enough of the UCI-protocol to get the engine connected to the GUI, and when that works, replace the search with a real a/b search, qsearch, and move ordering.

It's coming along nicely

Code: Select all

Program: Rustic Alpha 1
Author: Marcel Vanthoor <mail@marcelvanthoor.nl>
Description: Chess Engine written in Rust
Threads: 1 (not used yet, always 1)
Protocol: console
Starting Comm Reader thread.
Starting Search Control thread.
Setting up 1 workers...
Creating worker 1
Test calling worker 1
Starting Comm Control thread.
================================================

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I I I I I I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Rustic > e2e4
================================================

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . I . . .
3   . . . . . . . .
2   I I I I . I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        8bd874f3a73d976c
Active Color:       Black
Castling:           KQkq
En Passant:         e3
Half-move clock:    0
Full-move number:   1

Rustic >

[maksimKorzh]

Rustic's communication infrastructure has been implemented.

It is now able to receive information from, and write information to, its comm modules. It can also start and stop its search module, and it is already prepared for a future where the search module will have more than one worker (and thus will implement SMP.) The engine can now receive moves from outside (in this case, console; but obviously also UCI and Xboard after I implement those modules.)

The console comm module is very useful for building and testing new functions, because nothing else is in the way. If a new function is not fully working, it's because there's something wrong with the function; and I don't have to worry that either the UCI or Xboard protocol implementations are the problem.

(Obviously, the engine checks incoming moves for legality; even though a GUI probably will never send an illegal move through UCI or Xboard, I don't want the engine to just crash when I put something weird into the console.)

Next week I'll be implementing a brute force min-max search, to get that finished quickly; then I'll be able to play a game through the console. It'll probably play horrible, but that doesn't matter. When it works, I can implement enough of the UCI-protocol to get the engine connected to the GUI, and when that works, replace the search with a real a/b search, qsearch, and move ordering.

It's coming along nicely

Code: Select all

Program: Rustic Alpha 1
Author: Marcel Vanthoor <mail@marcelvanthoor.nl>
Description: Chess Engine written in Rust
Threads: 1 (not used yet, always 1)
Protocol: console
Starting Comm Reader thread.
Starting Search Control thread.
Setting up 1 workers...
Creating worker 1
Test calling worker 1
Starting Comm Control thread.
================================================

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . . . . .
3   . . . . . . . .
2   I I I I I I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        819aa694337673fb
Active Color:       White
Castling:           KQkq
En Passant:         -
Half-move clock:    0
Full-move number:   1

Rustic > e2e4
================================================

8   r n b q k b n r
7   i i i i i i i i
6   . . . . . . . .
5   . . . . . . . .
4   . . . . I . . .
3   . . . . . . . .
2   I I I I . I I I
1   R N B Q K B N R

    A B C D E F G H

Zobrist key:        8bd874f3a73d976c
Active Color:       Black
Castling:           KQkq
En Passant:         e3
Half-move clock:    0
Full-move number:   1

Rustic >

Yup, this is one of the core examples that makes me respect your approach in programming.
When you can't do something on your own the only thing left is to enjoy how others do it.
Keep good work, Marcel, maybe one day I will learn this stuff from your book. I hope for that.
If I had teachers like you when I was a kid probaly my life would gone completely different way)
It's a fortune to meet and know you!

[mvanthoor]

Yup, this is one of the core examples that makes me respect your approach in programming.
When you can't do something on your own the only thing left is to enjoy how others do it.
Keep good work, Marcel, maybe one day I will learn this stuff from your book. I hope for that.
If I had teachers like you when I was a kid probaly my life would gone completely different way)
It's a fortune to meet and know you!

I don't know what to say. YOU're the one with the huge amounts of youtube tutorials, where you explain some things more than well enough for anyone to understand. Those video's are second to none, except maybe BlueFever's (but that's no shame, because that series is legendary).

The things you'd learn from the book / massive tutorial I'm going to write on Rustic are mostly related to chess programming; things you can learn in other places, or even know already. You obviously know the Bruce Moreland site, from 2001. It's offline (but I managed to get a copy through old forum posts and the way-back machine), but the book will be similar to that. It'd basically be a written version of your own video's.

However, there will be a part to the book that is more Rust / software engineering related, instead of chess related. See below, if interested...

======

The one thing that is very different in Rustic as compared to many other engines is the internal structure. It has multiple active modules, with one or more threads per active module.

Many engines are written like VICE: with an entry point that runs from top to bottom, until it hits uci_loop(), where it 'hangs' waiting for input. Then it searches, and it either uses one extra thread, or it "peeks" into the keyboard buffer to keep receiving input. After the searched move is submitted, the engine hangs in uci_loop() again. Multiple threads for searching are spawned when needed (if the engine supports SMP).

(Please don't comment with "Not true, because MY engine..."; I obviously didn't scroll through the code of ALL engines in the universe.)

I didn't want to do it like that, so I designed Rustic the same way as I would design a program for an industrial machine. (Originally, I'm not an application or website developer; I write embedded software, firmware, and I program industrial machines.) The "Engine" thread is the main thread, like the PLC computer in a machine. It receives inputs, and sends outputs, and those go to other components of the engine. The other components react to those inputs, and send information back, if applicable. In a machine, these inputs/outputs and other components are physical, but in Rustic, they are in software (Threads inside the modules, and channels between threads.).

For people who are not used to writing software in this fashion this might be confusing, but to people who work as software engineers in the industrial world and write software to control machinery (or multiple machines, especially over a network), this approach will be instantly recognizable.

This is Rustic's Engine struct:

Code: Select all

// This struct holds the chess engine and its functions. The reason for this
// struct is that it can contain member functions and other structs, so
// these don't have to be in the global space.

pub struct Engine {
    running: bool,            	// Flag to keep main thread active.
    settings: Settings,       	// Struct holding all the settings.
    cmdline: CmdLine,         	// Module: Command line interpreter.
    comm: Box<dyn IComm>,     	// Module: Communications (active).
    board: Arc<Mutex<Board>>, 	// Module: Board.
    mg: Arc<MoveGenerator>,   	// Module: Move Generator.
    search: Search,           	// Module: Search (active).
}

- Running is self-explanatory. As soon as this is set to false, the engine will go into shutdown.
- Settings is just a struct that holds settings, such as the number of threads.
- CMDLine is a passive module: it runs once, on engine startup, to get all the provided command line parameters.
- Comm is an active module. It starts, and then keeps running, providing Rustic's Engine thread communication with the outside world.
- Board is the engine's board representation. It is passive; it executes moves if asked to.
- Mg is the move generator. It is passive. When you give it a board, it'll generate pseudo-legal moves.
- Search is an active module. It's active, as it controls 1 or more search workers (it can start/stop/quit workers, etc).

In this regard, Rustic is not a 'standard' engine. It has a large internal communication infrastructure, with interchangeable comm modules it is actually capable of running mutliple comm modules at the same time: it could be connected to a GUI for playing, but at the same time, have a second comm module that sends moves or commands over a network to a live viewer, or something like that.

This is massively NOT chess related, and it certainly wasn't necessary to build it like this, but I wanted it. This allows me to keep the UCI and Xboard protocols completely separated from one another and the rest of the engine (in most engines I've seen the UCI-protocol is interwoven throughout the engine, including search), so I can work in one part without worrying that I break a different part of the engine. I can even replace a complete part with none, or minimal changes to other parts. And yes... for a chess engine this might be over-engineered.

[mvanthoor]

Almost forgot... search is alive It is already capable of multi-threading, but in practice, it will only be using one worker thread for now, even if you specify 4 or 16. (The engine just overrules --threads 4 to --threads 1).

Next step: put in a brute force search mini-max search (in the spot where it now says "Worker reporting"), so it can play horrible chess, and I can then implement the UCI interface. And after that, the final step to version 1: alpha/beta search with mvv-lva move ordering. (Killer and history will be implemented for version 2; tapered eval for version 3; hash table for version 4. Rough roadmap. I don't know exactly yet.)

Code: Select all

$ ./target/release/rustic.exe -t4
Program: Rustic Alpha 1
Author: Marcel Vanthoor <mail@marcelvanthoor.nl>
Description: Chess Engine written in Rust
Threads: 4
Protocol: console
Initializing engine...
Starting Comm Reader thread.
Starting Search Control thread.
Starting Comm Control thread.
Setting up 4 workers.
Creating worker 1.
Activating worker 1.
Creating worker 2.
Activating worker 2.
Creating worker 3.
Activating worker 3.
Creating worker 4.
Activating worker 4.

start		<-- I type this in the console

Worker 1 reporting.
Worker 4 reporting.
Worker 3 reporting.
Worker 2 reporting.

// -- keeps outputting --

stop 		<-- I type this in the console

// -- output stops --

quit
Quitting Comm Reader thread.
Waiting for Comm shutdown...
Quitting Comm Control thread.
Shutting down worker: 1
Comm shutdown completed.
Waiting for Search to shut down...
Shutdown for worker 1 completed.
Shutting down worker: 2
Shutdown for worker 2 completed.
Shutting down worker: 3
Shutdown for worker 3 completed.
Shutting down worker: 4
Shutdown for worker 4 completed.
Quitting Search Control thread.
Search shutdown completed.
Engine shutdown completed.

[mvanthoor]

Rustic now has the beginnings of an evaluation function. (Because I need this for the search anyway, I decided to do this first.) In the position below (which I have played by hand for both sides), the following happed:

- White swapped a bishop (value: 320) for a knight (310): evaluation: -10
- White castled kingside (PSQT +20, for white): evaluation -10 + 20 = +10
- Black castled queenside (PSQT +15, for black): evaluation +10 - 15 = -5
- Adjustment due to king PSQT is +20 for white, +15 for black, so net adjustment is +5.

Seems to work Now I just need to implement the PSQT's for the other pieces, and then the search and uci.

PS: For now, I'm rolling my own PSQT's and piece values. Later I'll add tapered evaluation, and even later I'll optimize/tune this somehow. I dislike PSQT's with A1 on the top left. I make mistakes when changing them. I have the impression that PSQT's with A1 = 0 and a flip table for black are more common, but mine are from white's point of view (E1 is element 60 in the table, so A1 is element 56), so I have a FLIP table for white, instead of black.

Code: Select all

8   . . k r . b n r
7   . i i b q i i i
6   i . i . . . . .
5   . . . . i . . .
4   . . . . I . . .
3   . . N I . N . .
2   I I I . . I I I
1   R . B Q . R K .

    A B C D E F G H

Zobrist key:        be2f35a194888a0e
Active Color:       White
Castling:
En Passant:         -
Half-move clock:    1
Full-move number:   8

===
Adjustment for wK: 20
Adjustment for bK: 15
King adjustment: 5
Evaluation: -5
===

Rustic >