Why does my engine want to perpetually check?

[mvanthoor]

To be very clear, the code as it stands now is not in the form it will need to be in to be instructive for beginners. It's going to take a lot of work to take it from "working well", once I get there, to "very readable/understandable", but I'm looking forward to that process. I expect it will involve a fair amount of refactoring, and I'll likely sacrifice some speed for clarity. Having said that, I understand that even when it's in good shape, it may still be difficult to understand for a set of people simply due to being a lisp.

Rather than blog about the process as I go, I think I'd rather complete version 1.0, and then essentially re-build it piece by piece and post a blog article about each piece. With me doing manual time management, it's beaten a number of 1,800+ human players, so I think I'm making reasonable progress. It seems much weaker against other chess engines, e.g. I have to give it a decent amount of time per move to beat Wukong at the "Code Monkey King (1700)" level If my engine moved as fast, it would be crushed every time, but I've yet to add TT & other features; I only have quiescent search & a super simple PST now.

I look forward to be able to try and play against your engine.

Remember that you can always download older versions of my engine after newer versions become available. Rustic Alpha 1 is just a smidge under 1700 on CCRL now, and it's very stable. It will be able to play a 1000 game match without issues (which cannot be said of some of the other engines around that strength).

As I've said many times before: Rustic Alpha 1 has no features, apart from MVV-LVA, because I wanted to get everything as perfect as I reasonably could, with ONLY this basic move sorting, and check extension in place. (Some move ordering is necessary, as without it, your engine will waste massive amounts of time. Check extension is needed to make QSearch work as it should, as the engine should not do QSearch when the king is in check.)

My advise would be to go for this basic version first:

- Move generator
- Board representation
- Alpha/Beta
- Qsearch
- Check extension
- MVV-LVA
- Simple time management

Then you will be able to optimize that code to be bug free, readable, and as fast as it reasonably can be, and then you'll have a basic version to compare everything against, including your own progress, feature by feature. Don't add any new features before you're 100% sure that the stuff you have is bug free and as clear to read as possible. Having to go back finding bugs in features where one feature can influence the other can be very hard.

Resist the attempt to go feature hoarding. The best example I always (regrettably) have to point to in this regard is Shallow Blue. This engine ranks at 1711 in the rating list. Rustic ranks at 1695. The difference is Rustic has no features, but also no (known) bugs... SB has a MASSIVE feature count, but lots of bugs. Drofa 2.0, which is basically "Shallow Blue without bugs + optimizations", ranks at 2450. Shallow Blue lost 750 ELO (!) due to bugs and poor optimization.

[lojic]

...
My advise would be to go for this basic version first:

- Move generator
- Board representation
- Alpha/Beta
- Qsearch
- Check extension
- MVV-LVA
- Simple time management
...

I have all of that, except for "check extension", plus a PST. The engine is very stable at the moment. I was going to add TT next, but if check extension has a higher benefit/cost ratio, I could do that next.

[mvanthoor]

I have all of that, except for "check extension", plus a PST. The engine is very stable at the moment. I was going to add TT next, but if check extension has a higher benefit/cost ratio, I could do that next.

Check extension is really simple. It's just:

Code: Select all

if square_attacked(king_square) {
	depth += 1;
}

Just before QSearch. That line is:

Code: Select all

if depth == 0 {
	return qsearch(....);
}

This makes the engine skip qsearch if the king is in check, and go another ply deeper.

Forgot about the PST. They are obviously also necessary.

Do you have enough time management and UCI or XBoard commands implemented to run a tournament? Then, after you add the check extension, you could provide a binary (or I could try to compile the engine myself) and run a preliminary tournament.

[emadsen]

I was just reading in Jon Bentley's "Programming Pearls" about Andrew Appel's account of progressively reducing the run time...

I need to re-read Bentley's book. I remember it opened my eyes 20 years ago to what is meant by "software engineering."

I find enjoyment in working with certain constraints and pushing the boundary of what can be done within them. If I do get the competitive itch, I would probably give Julia a try - I'm pretty sure it would get me close enough to C++ w/ less pain

I believe Tord Romstad is doing some chess programming in Julia. I remember reading something about that on this forum.

I guess I'm a little turned off, Marcel, by your attitude that everyone else says they'll write a didactic engine but they fail miserably at the attempt and you'll be the one who actually does it. Many people have done it, past and present. I hope you add to the canon of free, instructive material. I hope lojic does too. I'd like to think I have also. There's room for all of us.

It appears we'll have to agree to disagree on the importance of programming language and the infatuation with perft speed.

Lojic: Rather than blog about the process as I go, I think I'd rather complete version 1.0, and then essentially re-build it piece by piece and post a blog article about each piece.

Mvanthoor : 35%+ of Rustic's source code is actually comments, explaining what and why the code is doing, and documentation to go with it. (I'm writing that now, actually.)

Great! I'll follow both of your efforts with interest.

C# is the perfect tool for my career writing business software- websites, REST APIs, application integration, that sort of thing. However, I would like to learn a systems programming language for hobby programming. C++ and Rust are obvious choices. For years I've read Raymond Chen's The Old New Thing blog with fascination and horror at the dark recesses of the C++ language. Maybe that's more an indictment of Microsoft's abuse of C++ for Win32 development than the C++ language itself. Rust looks like a fascinating alternative to me from a distance. Perhaps I'll dive into it some day. If so, I'll check out the source code of Rustic, FabChess, Asymptote, and other Rust chess engines.

[mvanthoor]

I guess I'm a little turned off, Marcel, by your attitude that everyone else says they'll write a didactic engine but they fail miserably at the attempt and you'll be the one who actually does it. Many people have done it, past and present. I hope you add to the canon of free, instructive material. I hope lojic does too. I'd like to think I have also. There's room for all of us.

You certainly have provided some valuable information on your blog. There are also certainly some engines that I can call truly didactic. Some to mention:

- VICE by Richard Allbert (accompanied by a video series)
- Wukong and BBC by Maksim Korz (accompanied by Video series)
In the past:
- Gerbil by Bruce Morland (website)
- Roche, by ... (forgot) (website)
- Mediocre ... (blog)
- Vajolet ... (blog)
- Actually... Shallow Blue (great article on bitboards)
- TSCP by John Stanback (website; but this is very old now)

And I'm probably forgetting a few.

I've just seen too many engine sources stating that the engine is didactic (or going to be), while it just isn't true. I'm not trying to boast that I will be the one to write THE definitive, ultimate, didactic engine to the exclusion of everything else. I'm just saying that it could be used as such, should someone want to, as opposed to quite a few engines that state that they're useful for learning chess programming, but actually aren't.

It appears we'll have to agree to disagree on the importance of programming language and the infatuation with perft speed.

I'm not talking about perft speed. If two programs are written in different languages, but have the the exact same feature set (and none have poor implementation of these features), the program in the faster language will be stronger. If the language runs 4x-5x as fast, as is the case with Rust vs. Go, then the faster program will be 100 ELO stronger.

And as a different poster said... thinking in the back of my head "this could have been 800 elo stronger if had written it in C instead of Python" (which is actually not that far fetched I think, knowing Python...); I wouldn't be able to bear it.

Lojic: Rather than blog about the process as I go, I think I'd rather complete version 1.0, and then essentially re-build it piece by piece and post a blog article about each piece.

Mvanthoor : 35%+ of Rustic's source code is actually comments, explaining what and why the code is doing, and documentation to go with it. (I'm writing that now, actually.)

Great! I'll follow both of your efforts with interest.

Thanks I'm following the current blogs/sites/video series I know of with regard to chess programming, especially with engines in the earlier stages of development.

C# is the perfect tool for my career writing business software- websites, REST APIs, application integration, that sort of thing.

Sure is; it was designed to write business software, and it shows. I'm writing a new application at work, and it's in C#; I wouldn't even DREAM of writing this application in something else. Utmost speed is not one of the targets of this application. Development speed, easily hosted in Azure, long-term support by a well-known programming language and consistency are.

However, I would like to learn a systems programming language for hobby programming. C++ and Rust are obvious choices. For years I've read Raymond Chen's The Old New Thing blog with fascination and horror at the dark recesses of the C++ language. Maybe that's more an indictment of Microsoft's abuse of C++ for Win32 development than the C++ language itself. Rust looks like a fascinating alternative to me from a distance. Perhaps I'll dive into it some day. If so, I'll check out the source code of Rustic, FabChess, Asymptote, and other Rust chess engines.

With those three chess engines, I think you have covered the current ones in development. There are some others, but they are so old and long out of development that they don't even compile with current Rust compilers anymore. (Cicada and Crabby are the ones that come to mind.) If there are any others, I don't know of them.

[lojic]

Check extension is really simple. It's just:

Code: Select all

if square_attacked(king_square) {
	depth += 1;
}

Just before QSearch. That line is:

Code: Select all

if depth == 0 {
	return qsearch(....);
}

This makes the engine skip qsearch if the king is in check, and go another ply deeper.

That seems simple enough. I suppose you don't have to worry about going too deep since it's unlikely for a reply to check to check the other king, and even if it did, that would end pretty quickly.

Do you have enough time management and UCI or XBoard commands implemented to run a tournament? Then, after you add the check extension, you could provide a binary (or I could try to compile the engine myself) and run a preliminary tournament.

I still need to add UCI commands. I should do that soon to allow me to test my changes to see if they improve play, or not, w/o having to manually test which is so time consuming. Time management is very simple currently, but I do have the ability to change the think time for each move, so modifying it to work for a tournament, should be simple enough. I'll probably be able to play in an automated way w/ UCI in less than a week.

[hgm]

In micro-Max doing an unconditional check extension did not bring any Elo. Later I discovered that this was because the beneficial effect in the middle-game was offset by a detrimental effect in the end-game. So now it uses check extension only in the middle-game.

I guess there is some logic in this: in the end-game you need the King to leave its shelter, and participate in the fight. It can afford to do that because checks are no longer dangerous, and usually a waste of time. So the check extension would draw most search effort to chasing the King around the board, often helping it to get to where it wanted to go anyway. And as a result the most important lines would be searched less deep.

Also note that you have to be a bit careful with the TT, to determine whether a probe has enough depth to be used for a cutoff. If you store the extended depth in the TT, you would have to compare it with the extended depth. But you would only know it has to be extended after testing whether you are in check, and if you finally do get a hash cutoff, the time for the check test would have been wasted; it would have been easier to take the hash cut immediately. You can achieve that by always storing the unextended depth in the TT. Then you can compare it to the requested depth directly, and only have to worry about being in check and extending when you don't get the hash cut. You would still have to know whether you should extend before you can search the hash move. To avoid having to do a check test for that you could put a bit flag in the TT entry that tells you you are in check (or in general that you should extend, if you use other extensions). Then you also save the check test when you get a cutoff from the hash move (which will happen very frequently). If you can afford the space you could of course also put all the info that the in-check test normaly delivers (e.g. which piece is checking, and from which direction, to help generating the evasions) in the TT entry. Then you only have to do an in-check test on a hash miss.

And you are right; in Chess checks in consecutive plies are rare, and mutual perpetual check is impossible. In variants with Cannons or Nightriders this is a problem, though, and older Fairy-Max versions, which did not check for repetitions in the tree, would crash due to infinite recursion there.