Monchester

[unserializable]

Ok, this is done -- here is Monchester 1.0!

Now on GitHub, with source code licensed under GPLv3:

• Source release archives: https://github.com/unserializable/monchester/releases/
• Binaries folder: https://github.com/unserializable/monch ... r/binaries
• Issue reporting: https://github.com/unserializable/monchester/issues
• Full README: https://github.com/unserializable/monch ... /README.md

What do the users say?

• "I drew it twice, but with black it beat me twice."
• "Daddy, it is gonna take your horsie!"

It values bishop at 8 pawns, knight more than a bishop and knight is the only piece for which placement it gives any additional bonuses. Constant 4-ply search depth. Not a single extension. No quiescence search. Simple blunders galore, balanced by simple randomization for varied play. No hash tables, transposition tables, alpha-beta, etc. Completed after 18 years in attic, released for beta-testing on the eve of Halloween and now ready to challenge the patzers of this world. GPLv3, somewhat commented code. Rock solid (I truly hope!).

Details of changes in 1.0 as compared to 0.99

Public and easily accessible release on GitHub, with source code license (GPLv3) now chosen and applied. This 1.0 release is complete with all FIDE rules, including engines own underpromotions. Its playing level estimate is the same as for 0.99 -- should fall somewhere between ChessPuter (842) and GiuChess (993) in terms of CCRL 404.

Features:
* Added underpromotion support for engine-side.
* Mate scoring output to correspond to CECP conventions.
* Command-line parameters ``--version`` and ``--help`` and ``--bench`` now produce useful output and are documented.
* Game score saving feature disabled by default -- interfaces take care of that. Debuggers, testers and developers can enable it from ``features.h`` -- if they are using Mac or Linux (Windows will not work as it has now file locking call ``flock``).
* CECP 'hint' command is sneakily supported -- hint depth is set at 2-ply, beware of taking hints from Monchester.

Bugfixes:
* Fix missing promotion suffix on relevant engine moves.
* Fixed internal mishandling of black promotions that sometimes could cause illegal move to be tried on-board.
* Fixed crash if CECP ``go`` given immediately after protocol announcement without ``new`` or ``setboard`` inbetween.

Thanks to Guenther Simon and Roland Chastain for trying out and giving feedback to 0.99 preview release!

In the binaries folder for 1.0 there are currently Linux x64 binaries (static and dynamic) only. There were no testers of 0.99 Mac binaries -- I suppose I will put up Mac binaries later if I get my friend to compile it for me again --but if possible I would like to look at possible installation methods via brew. For Windows binaries, Guenther promised to update https://rwbc-chess.de/download.htm offering when 1.0 comes out, so they should be available there soon.

[Guenther]

Ok, this is done -- here is Monchester 1.0!

Now on GitHub, with source code licensed under GPLv3:

• Source release archives: https://github.com/unserializable/monchester/releases/
• Binaries folder: https://github.com/unserializable/monch ... r/binaries
• Issue reporting: https://github.com/unserializable/monchester/issues
• Full README: https://github.com/unserializable/monch ... /README.md

What do the users say?

• "I drew it twice, but with black it beat me twice."
• "Daddy, it is gonna take your horsie!"

...

For Windows binaries, Guenther promised to update https://rwbc-chess.de/download.htm offering when 1.0 comes out, so they should be available there soon.

I will look at it tomorrow!
Thanks for the update info, Taimo.

[unserializable]

I will look at it tomorrow!

Thank you Guenther, have a good evening !

[mvanthoor]

Third way is to just to have search that rans for short enough time that the command processing delay remains within bounds that interfaces accept as okay. For Monchester this means that analysis mode of XBoard is not supported, but otherwise things should be good and cross-platform, had no wish to do cross-platform threading or relatively low-level I/O code in C at this moment (even C11 threads are underspecified). Good to hear that Rust threading is nicely specified and supported in the standard library.

While it does work to make sure that your search is over before the GUI starts complaining, you will at some point need to build something that can keep the search running, but also interrupt it if a command comes in. You could look into the VICE video series. It has a video on how to do it, by peeking into the keyboard buffer.

Thanks for the help offer. This notion of 'basic' is rather advanced, starting with minimax should not anyhow hinder chances of 'decent search' -- though about MVV-LVA I have no knowledge, so will not challenge your assertion -- could you expand on that a little bit?

Alpha-Beta is an impromvement on MiniMax. The MiniMax algorithm always searches the entire three. Alpha-Beta tries to cut off branches that are not good. Basically it means: "If my opponent can make this move, it is very bad for me, so I won't go into that position." At that point, Alpha-Beta disregards that position, and all the branches below it in the tree, which saves a lot of search time.

MVV-LVA extends on that. It stands for Most Valuable Victim, Least Valuable Attacker. It is a way of making Alpha-Beta pick certain moves first. As you can imagine, Pawn takes Queen is (probably) very good for you if you can do it, but very bad if the opponent can do it. Queen takes Pawn is only useful if the pawn is not protected. Thus, you should search Pawn takes Queen first.

You do it as follows:
- create a table that holds all the possible captures, and rank them from good to bad.
- Now sort your moves by score
- Then Search as normal

Because you have the good captures first, the chance of cutting off more of the tree becomes bigger, and you have to search less to find the same moves.

Note that this only works with alpha-beta, not with minimax.

PS: In Rustic, I don't sort moves. I use the "pick_move" variant. Lets say I have 40 moves to search, from 0 to 39. When searching move 0, I run through the entire list, and make sure the highest scoring move is swapped onto position 0. If that does create a cutoff, the search just do the next move, at position 1; but before searching that move, I have "pick_move" put the highest scoring move there (out of the remaining part of the list.)

[hgm]

In Fairy-Max I use the following piece of code for providing functions to read the time and peek for input that work under Windows, Linux and OSX:

Code: Select all

#ifdef WIN32 
#    include <windows.h>
#    define CPUtime 1000.*clock
     int Input()
     {  // checks for waiting input in pipe
	static int init; static HANDLE inp; DWORD cnt;
	if(!init) inp = GetStdHandle(STD_INPUT_HANDLE);
	if(!PeekNamedPipe(inp, NULL, 0, NULL, &cnt, NULL)) return 1;
	return cnt;
    }
#else
#    include <sys/time.h>
#    include <sys/times.h>
#    include <sys/ioctl.h>
#    include <unistd.h>
     int GetTickCount() // with thanks to Tord
     {	struct timeval t;
	gettimeofday(&t, NULL);
	return t.tv_sec*1000 + t.tv_usec/1000;
     }
     int Input()
     {
	int cnt;
	if(ioctl(0, FIONREAD, &cnt)) return 1;
	return cnt;
     }
#endif

GetTickCount() returns a wall-clock-time measure in msec (it ticks only every 16 ms on Windows, though). Input() returns nonzero if there is input waiting to be read. These functions can be called from the search every so many nodes (better not in every node, as they are pretty time consuming), to test whether the search should be aborted.

[mvanthoor]

In Fairy-Max I use the following piece of code for providing functions to read the time and peek for input that work under Windows, Linux and OSX:

Code: Select all

#ifdef WIN32 
#    include <windows.h>
#    define CPUtime 1000.*clock
     int Input()
     {  // checks for waiting input in pipe
	static int init; static HANDLE inp; DWORD cnt;
	if(!init) inp = GetStdHandle(STD_INPUT_HANDLE);
	if(!PeekNamedPipe(inp, NULL, 0, NULL, &cnt, NULL)) return 1;
	return cnt;
    }
#else
#    include <sys/time.h>
#    include <sys/times.h>
#    include <sys/ioctl.h>
#    include <unistd.h>
     int GetTickCount() // with thanks to Tord
     {	struct timeval t;
	gettimeofday(&t, NULL);
	return t.tv_sec*1000 + t.tv_usec/1000;
     }
     int Input()
     {
	int cnt;
	if(ioctl(0, FIONREAD, &cnt)) return 1;
	return cnt;
     }
#endif

GetTickCount() returns a wall-clock-time measure in msec (it ticks only every 16 ms on Windows, though). Input() returns nonzero if there is input waiting to be read. These functions can be called from the search every so many nodes (better not in every node, as they are pretty time consuming), to test whether the search should be aborted.

This is the way VICE does it. In one of the video's, BlueFever/Richard says he found the piece of code he uses on the Winboard forum. I'd have to check the actual video or the original VICE code, but I wouldn't be surprised if this _IS_ the piece of code he found and used. (And it's possibly, probably, used in many derivatives of VICE, or engines inspired by it; if they are written in C or C++.)

[unserializable]

MVV-LVA extends on that. It stands for Most Valuable Victim, Least Valuable Attacker. It is a way of making Alpha-Beta pick certain moves first.
...
You do it as follows:
- create a table that holds all the possible captures, and rank them from good to bad.
- Now sort your moves by score
- Then Search as normal

Thanks Marcel, now I get what you mean about MVV-LVA as requirement for 'decent search'. For Monchester, algorithmic alpha-beta should be relatively simple to add in place of minimax, without even touching move ordering, and still provide some gains, but for maximum gains move-ordering will need to be tuned and that might be not that trivial to do effectively if there has been no design for that beforehand (as there has not been ). So I will think about implications of this and best way to approach this and whether I find some relatively effective move ordering approach (I have not looked into them yet but from your description MVV-LVA seems rather good).

In Fairy-Max I use the following piece of code for providing functions to read the time and peek for input that work under Windows, Linux and OSX:

Code: Select all

...

GetTickCount() returns a wall-clock-time measure in msec (it ticks only every 16 ms on Windows, though). Input() returns nonzero if there is input waiting to be read. These functions can be called from the search every so many nodes (better not in every node, as they are pretty time consuming), to test whether the search should be aborted.

Thanks for the snippet, H.G.M! I will try this out in my upcoming experiments. I do also want to get to parallelism via some kind of threading, but this peeking seems simpler for the start, for e.g. supporting analyze of CECP while being able to break out of the search. Seems it soon might be time to install some Windows virtual machine on my Linux boxes after virtually not touching any Windows computers for years

[hgm]

..., for e.g. supporting analyze of CECP while being able to break out of the search.

This is exactly what Input() is used for in Fairy-Max. It could also be used for terminating a ponder search, but Fairy-Max doesn't ponder at all.

[mvanthoor]

Thanks for the snippet, H.G.M! I will try this out in my upcoming experiments. I do also want to get to parallelism via some kind of threading, but this peeking seems simpler for the start, for e.g. supporting analyze of CECP while being able to break out of the search. Seems it soon might be time to install some Windows virtual machine on my Linux boxes after virtually not touching any Windows computers for years

If you can get your I/O to be threaded, sure.

Personally, I wouldn't bother with adding threading to your engine for search, because going from 1 to 4 cores adds only about 100 Elo. There are search and evaluation additions you can make that are much easier to do, and some (such as teaching an engine about passed pawns and using open lines), can net you close to 100 Elo.

See Eric Madsen's site about MadChess 3.0, where he keeps track of the Elo gain of every feature he adds (I intend to start doing the same in my engine, now that my very first base version is done and only needs wrapping up and releasing properly):

https://www.madchess.net/2020/08/29/mad ... crash-bug/

Adding passed pawn knowledge adds 119 (!) Elo.
Adding piece mobility to the Eval adds 62 Elo.
Adding king safety to Eval adds 63 Elo

That's 250 Elo right there, and much easier to add than threading. (If you haven't made any provisions for threading, it can actually be near-impossible without half a rewrite.)

As there are engines that are over 3000 Elo on one thread, I (personally) don't even think about adding search threading to Rustic until I reach that point... except if it is _very_ easy to do. (I have, obviously, taken threading into account already. I have tested a threaded perft a few weeks ago.)

Still, for the Elo gains, you don't need to do it, as you already know the answer: 1 -> 4 CPU's gets you 80 - 120 Elo (depending on the rest of the engine), on top of your current rating, and that's basically it.

Also, testing with a 4 CPU version takes a lot longer, because you can't run as many games at once.

Oh, and with regard to pondering, which HGM mentions....

I don't know if I will ever implement this. I have NEVER used the ponder option in any engine. Nowadays, most engines beat the pants off of a normal human club player if you give them one second per move thinking time. I can still beat Rustic when using anti-computer strategies, avoid tactics, and make use of its lack of knowledge, but if I try to go one-to-one with it in a "normal" chess game, it toasts me as soon as there are ANY tactics deeper than 8 plies or so in the position.

After I add search enhancements such as killers, heuristics, and (oh my god) a hash table, it will probably steamroll me without even properly waking up the CPU. I don't NEED it to ponder.... building a good Level function is much more important to me, because I want to play against this thing on a DGT board.

[Guenther]

I will look at it tomorrow!

Thank you Guenther, have a good evening :)!

I compiled a default version, just wanna know if a version with a one ply higher default depth is desired too for 1.0?

Code: Select all

git clone --branch 1.0-branch https://github.com/unserializable/monchester.git

Code: Select all

# Monchester 1.0 ~(4338 kN/s)
command : bench 6
Nodecount 124132536, 29.510s, 4206 kN/s
command : help
commands understood: new, resign, help, bench, quit