Which features offer the best return?

[lojic]

Hello:

I've just fulfilled (partially) a dream I've had for a long time - to write a chess engine in a lisp. I've implemented an engine in Racket which is essentially a version of Scheme. It plays reasonably well for how simple it is. I have alpha beta pruning and a very simple evaluation function. It can only search to ply 7 now (and be fast enough for a 10+5 game) after I added some heuristics to the evaluation function.

My goal is a modest one - simply for it to consistently beat me (I'm roughly 1,650), and it's not quite there yet, I think it's probably ~ 1,550.

Given that I'm not trying to make it super competitive, I'm mainly looking for a few more features that will accomplish my goal of being ~ 1,700 - 1,800, or so. In other words, I'm looking for the "best bang for the buck", as my dad says :) Of course, I may get hooked and want it to continue to improve!

My hunch is that if I implemented "depth extension", or whatever it's called, to search deeper in certain circumstances, such as w/ captures, that might do the trick. I was surprised at the decrease in speed when I changed my evaluation function from a simple piece value count to having just a few more simple heuristics. It seems the tradeoff with evaluation is the smarter the evaluation, the shorter the depth of search.

I saw someone posted the Stockfish Evaluation Guide in another thread, and it looks much better than the pages I've looked at thus far - what's your opinion of the info in that guide? It seems like it would slow the search down significantly, but maybe it's worth it.

To keep things simple, I'm using a 10x12 board instead of bitboards. I'm mutating the board state using make-move and unmake-move, and that seems to be working well. Alpha beta pruning certainly helped a ton. Now I'm looking for the next one, or two features to give it a boost.

I'd like to make the single threaded version faster before considering parallelizing it, although w/ 16 hyperthreads on my Macbook Pro, maybe I should do that sooner.

Here's the github source code - if you're not used to lisp, mostly ignore the parentheses and follow the indentation, and realize functions are like (generate-king-moves b idx piece) instead of generate_king_moves(b, idx, piece) :)

Thanks for any tips for this newbie!

Brian Adkins

[Ferdy]

Try passed pawns, mobility and king safety of course.

[lojic]

Try passed pawns, mobility and king safety of course.

Thanks. My question was more general i.e. better evaluation function vs. adding quiescent search vs. ?? Sounds like you're implying "better evaluation" offers a good return on time invested.

[Ferdy]

Try passed pawns, mobility and king safety of course.

Thanks. My question was more general i.e. better evaluation function vs. adding quiescent search vs. ?? Sounds like you're implying "better evaluation" offers a good return on time invested.

For comparison of the performance of each feature you have to run engine vs engine matches. At this stage of your development I believe passed pawn is good.

[jdart]

Many, many engines are weak because they are buggy. Verifying each feature does exactly what it is supposed to do is more important IMO than adding more features.

That said, if you don't have a quiescence search, you definitely need that. Also hash table, if you have not implemented.

Search-wise, recursive null move and late move reductions are important for strength.

Evaluation: passed pawns, mobility, and king safety are important.

[derjack]

Aside for bug hunting, the search can be improved without unsafe pruning for now. Do you use iterative deepening (sorry can't read lisp so I don't know )? Do you do some move ordering now? Like MVV/LVA, SEE, transposition tables, killer moves or history heuristic? That would give more depth without sacrificing accuracy for now.

[hgm]

Quiesence Search is extremely important. Or at least something that just grabs the most valuable piece it can on the last ply with its Queen, not caring whether it is protected or not. At the very least you will have to allow each player to capture the last-moved piece, for as many turns as is needed.

Make sure you have good move ordering. It enormously increases the depth for a given amount of thinking time.

After that, null-move pruning will bring you most Elo, and is very simple to implement.

A lot of strength comes from making sure your evaluation does not encourage bad behavior. This is not so much a matter of adding features, as well as making sure the features you do have are well tuned. E.g. if it has the tendency to centralize its King in the middle game, that would be pretty lethal. The same would be the case when it has its King cower away in a corner in the late end-game. Be sure the King stays in a safe place when there is still lots of material on the board, and that it maintains a Pawn shield where it is. Be sure it is sufficiently awarded for pushing Pawns (but not those in the King shield!) forward, especially in the end-game. And especially passers, if you can recognize those.

[mvanthoor]

Many, many engines are weak because they are buggy. Verifying each feature does exactly what it is supposed to do is more important IMO than adding more features.

This is true. I've noticed this in matches against Shallow Blue. Feature list. Version 1.1.0 already has a massive feature list, including a transposition table, but it only rates 1565 in CCRL Blitz. I have done a 200 game test against this version, using Rustic Alpha 1 (no features apart from QSearch, MMV-LVA and in-check extension), and Rustic won this match with a +200 Elo difference.

That would put Rustic Alpha 1 at a rating of 1765. RA1 lost a 200 game match against SB version 2.0.0 (CCRL 1715), with a rating of -65 ELO. That would put Rustic Alpha 1 at 1650 ELO.

This means Rustic would possibly be tentatively rated around CCRL 1650-1750; matches against other engines confirms this rating. It is much stronger than Shallow Blue 1.1.0, and almost as strong as version 2.0.0, even though Shallow Blue has a huge amount of extra features.

The engine Drofa is derived from Shallow Blue, and the developer fixed a huge amount of bugs. Drofa quickly increased to 2000+ and 2450+ ELO.

[lojic]

...Do you use iterative deepening (sorry can't read lisp so I don't know )? Do you do some move ordering now? Like MVV/LVA, SEE, transposition tables, killer moves or history heuristic? ...

For simplicity, instead of iterative deepening, I'm fine with just using the maximum depth I can while having it move in a reasonable amount of time i.e. instead of 1, 2, ... , max-depth, I just went straight to max-depth.

The only move ordering I'm doing now is keeping two lists of moves - quiet moves and capture moves, then I examine the capture moves first. This should help with quiescence since I'll already have a list of capture moves.

I think I'll start with adding quiescence, then maybe some refinements to the static evaluation, and then transposition tables. I'm looking forward to the opening book functionality a bit later, and I know I'll need something for the end game, because it just flailed around aimlessly when it had king + queen to the opponent's king Although, for my initial purposes, if the engine is clearly in a winning position, I'm satisfied for now w/o actually doing the end game mate, but I'm sure I'll add that for completeness later.

[mvanthoor]

I know I'll need something for the end game, because it just flailed around aimlessly when it had king + queen to the opponent's king Although, for my initial purposes, if the engine is clearly in a winning position, I'm satisfied for now w/o actually doing the end game mate, but I'm sure I'll add that for completeness later.

My engine had the same problem. This is easy to fix with a second King PST for the endgame. Just use a PST with a centralized king after the material dwindles below a certain amount of points. Yesterday, my engine actually managed to mate with KBN vs. K... but I have to say that it was helped by the opponent who actually ran towards the corner the bishop controlled, and "suddenly" the engine saw the mate in 10 moves.

It can reliably mate with KQ vs. K, KR vs. K, and KBB vs. K though, assuming it is not in time trouble. This will become even better after I've implemented transposition tables.