TalkChess.com

Hi

Yesterday I've implemented the magic bitboards for sliders and are about to test them. My engine Rustic is slowly crawling towards the state that it can actually start to play. I'm curious about what to expect.

I'm not looking at other engines for code. I'm studying concepts and reading about them across the internet, but I'm looking into the capabilities of lower rated engines on the CCRL/CGET lists.

Some of the lower rated engines have been in development for many years, and have loads of functions such as bitboards, a transposition table, quiescence search, extensions, LMR... but they're still below the 2000 ELO rating mark. Other engines have no bitboards, not much optimization and few features. One of those engines is the well-known tutorial engine VICE, but it's already over the 2000 ELO mark.

It seems (magic) bitboards and a lot of features don't automatically translate into a stronger engine. So, what could I expect of the strength of a barebones engine, assuming it has no bugs?
It would have:

- Bitboard board representation
- Magic bitboards for move generation
- Pseudo-legal move generator
- Make/Unmake paradigm
- Alpha/Beta in its simplest form
- Evaluation: material count and PSQT
- Detect mate, threefold draw, 50 move draw
- Basic time management
- And obviously a (minimal) UCI interface to enable it to play.

The very first version of my engine I'll release, Rustic Alpha 1, will have no optimizations and no functions that aren't 100% essential for making it play. So, no transposition table, no move ordering, no LMR, no nothing. Those will be added one by one in Alpha 2 and up, so I can track engine improvement, like Eric Madsen is doing with Madchess.

If I'd test such a barebones engine, what CCRL-rating could be expected? 800 ELO? 1000? Or maybe just slightly better than a random mover?

qsearch is quite important, move ordering as well, but even without these, assuming you have a working search, your engine should beat any random mover easily.

Without any form of move ordering it might be difficult to get beyond 1500. What is also important is whether you have some form of QS or not. But beware that an all-capture search without move ordering usually gives a search explosion, which causes the nominal depth of the search to drop somewhere in the middle-game to 1 or 2 ply in almost every game, after which a game-losing blunder is usually played. So your QS should probably be limited to capture of the last-moved piece.

Beating a random mover should be no problem at all. Even beating other non-searching engines, such as N.E.G. should be easy.

Thanks for the info

What sort of engines are those that are on the CCRL 40/2 (BLITZ) list, with ELO ratings under 800, even as low as 450 ELO? Are they all random movers? I'm just trying to get a feeling for what I can expect to see after I finish the barebones version of Rustic, and start testing it against the lowest engines on the list. And as said, that version, Alpha 1, will have nothing, except the bare minimum of functionality to be able to play legal chess.

First additions will probably be simple Lvv-Mva move-ordering to make the alpha/beta somewhat more efficiënt, and a transposition table after that. LAter on, I'll see what other optimizations will bring. I just want to see what all the improvements bring. (Though, its hard not to try and already implement them before Rustic has even played its first game.)

I just wonder what the engines that are in the 1500-2000 range, having (magic) bitboards, a plethora of features, and sometimes 10+ years of work behind them, are doing wrong as compared to much simpler engines that are already in the 2000+ range.

I think the engines below 1000 are just incredibly buggy. I am not aware that any of the engines above N.E.G. is non-searching; I think they are all alpha-beta or minimax. The Elo of the non-searching engines is highly overrated, btw. They should be more around -5000 Elo. But the gap between them and searching engines is just too big and empty to be measured. Another complication is that the engines in this region do not behave like the Elo model assumes. These engines will score a fair amount of losses irrespective of the strength of the opponent, due to their own bugs. Imagine an engine that plays half the games as Stockfish, and half the games as a random mover (e.g. because somewhere in the opening its table with piece values got overwritten by a longer-than-expected opening line). Such an engine would score 50% against a 2500-Elo opponent, but it would also score 50% against N.E.G., creating the impression for Elo-extraction programs that the difference between N.E.G. 0.3d and Fruit 2.1 isn't all that big. This greatly compresses the Elo scale.

Usurpator II (1131 Elo), for instance, is an old 6502 program that runs on a 6502 emulator. In the days it was written the number of nodes that could be searched was so small that one had to extend very aggressively to see any tactics at all. But when it can search more nodes this makes the search so unbalanced that it overlooks too many threats in lines that are not extended.

Note that magic bitboards are just an implementation technique, not a strength-providing feature. That an engine uses magic bigboards instead of mailbox means just as much as that it is programmed in C++ rather than Pascal.

I agree about the buggy part. I think a lot of engines with markedly poor performance are just buggy. They have not properly implemented an alpha-beta zero window search with quiescence, hash table, and the basic kinds of pruning: null move, futility, etc. If you are not doing this completely correctly, you are likely to have horrible branching factor in the search, and so reach limited depth.

I also agree about the bitboards. Properly done, this can give you a relatively small speed increase. Nothing huge.

--Jon

Thanks It could be that most of the very low rated engines are buggy and therefore waste huge amounts of time doing nothing, or the wrong thing.

With regard to (magic) bitboards: I understand that this is not a feature that imparts strength per se, but still it imparts speed.

If you want to know something about the position, you'd just need to and/or/xor a few bitboards and you'll know. If the engine iterates over pieces and squares, it has to do many iterations to find the answer. The bitboards should be (a lot) faster.

The author of Shallow Blue states that even moving from 'simple'/classic bitboards to magic bitboards improved engine speed by 30%:

https://rhysre.net/2019/01/15/magic-bitboards.html

"Magic bitboards show a 30% speedup over the classical approach." That's only perft; and its often stated that move generation is just a small part of the engine with regard to time usage. Thus I suspect (magic) bitboards to be even more helpful in parts that take more time (evaluation?).

Languages such as C/C++ are faster than (for example) Java, Go, or C#. All of those speed gains should at some point be enough to make the engine look one or two ply deeper than without those speed gains, and thus make it stronger.

I understand that using (magic) bitboards doesn't automatically impart hundreds of extra ELO to an engine, all other things being equal, but they'll make a difference. Even just compiling an engine for 64-bit instead of 32-bits will impart about 30-40 ELO according to CCRL.

If you have a bare-bones engine with the following features:

• Piece-square evaluation
• Quiescent search
• Basic Null Move
• Transposition table
• Move ordering including Killers

I'd expect it to play at about 2200 ELO on the CCRL scale. Adding mobility to the evaluation will add up to ~100 ELO; likewise for passed pawn evaluation. Late move reduction will add between 50 and 100 ELO. This takes the strength up to about 2450 ELO and covers all the easy-to-implement important features. This strength would be in line with Fruit 1.0 / 2.0 and Maverick 1.0. To improve above this point you'll most likely need more than just a bare-bone engine (YMMV). Of course bugs can have a serious impact on strength, which is why writing bug-free code should be top priority.

Steve

That's already not a barebones engine anymore IMHO. It's what is expected nowadays, but not the minimum to actually start playing.

mvanthoor wrote: ↑Mon Mar 02, 2020 4:46 pmWith regard to (magic) bitboards: I understand that this is not a feature that imparts strength per se, but still it imparts speed.

Even that is debatable. It depends a lot on what you want to compute in the evaluation, and what algorithms you would use to do that. I am sure that it will always be possible to pick stupid algorithms with either technology, which then makes that technology look bad.

That "magic bitboards show a 30% speedup over the classical approach" doesn't mean very much if we don't know what is meant by "classical approach". It could likely mean "rotated bitboards". It could be read as "Bitboards are slow, but magic bitboards are somewhat less slow than other bitboards". For a long time qperft (based on mailbox) was one of the fastest perft generators, and I think (magic) bitboard perfters only started to become competitive with the introduction of popcnt instructions in the hardware.