|Slow Chess Blitz by Jonathan Kreuzer|
I'll add more info here periodically.
Extensions Used, Detailed Description: The extensions used change often when I'm working on the program, so this may not be up to date after an update, and these extensions are certainly not optimal. Slow Chess uses fractional extensions, and any time they add up over a full ply 1 is added to depth remaining next time search is called. Also if a single move triggers multiple extensions, only the largest extension is done, the others are ignored. I didn't add any extensions until the transposition table seemed to work how I wanted, and I had already added Null-Move pruning. These seem to help quite a bit in extending interesting lines and not losing too much search depth.
Check Extension: This was the first extension added, and also the easiest to add. I'd certainly guess it results in the largest increase in playing strength. Simply put, any time the side to move is in check, depth remaining is increased by 1 full ply. Since it's quite unlikely that a move to get out of check will check the enemy king, even in situations with many checks possible it will rarely extend more than once in 2 ply. This extension helps greatly in a) Chasing down the enemy king to a mate or a gain in material b) Seeing past delaying tactics, as in a search checks can often push obvious gains in material or mates past the horizon... for instance a pawn could be 1 square from promoting, but a rook might be able to issue 5 delaying checks to a king until it can take cover and the pawn can promote.
Pawn Push Extensions: Seeing pawn promotions are very important as they amount to trading a pawn for a queen, a very big material swing. Slow Chess will always extend the depth by 1 ply anytime a pawn is moved to the 7th rank. (And it includes pawn promotions to a queen in the Quiscence-search.) So a 1 ply search sees a promo in 3 ply. Pawn moves to the 6th rank are also extended by 1 ply if the all of the following are true: a) The opposing side has 1 or fewer pieces b) the square in front of the pawn is empty c) neither square diagonally in front of the pawn has an enemy pawn.
Single Response Extensions: When in check, there are usually only a few moves that get you out of check. If there is only one legal move to get you out of check, there's a larger chance that you are in trouble and will be mated soon. Also, when there is only one response extending very deeply won't cost so many extra nodes, since there is only 1 move to search. When getting out of check, Slow Chess first makes a list of all the legal moves. (This slows down the search some, but could be much better optimized than I have it now.) If there is only 1 legal move, depth is extended by 3/4ths of a ply. (When there are 2 legal moves, depth is extended by 1/4th of a ply.) This is done on the move out of check, so since the move before was a check, depth is extended by 1.75 ply in only 2 ply of search, so these lines can be investigated very deeply.
Mate threat extension: (extending when the side to move would get mated in 1 move if it passed.) A well done mate threat extension can find some mates much quicker, since it can find when there's a mate possible, but a few delaying moves can delay it 2 to even 6 or more ply. Also extending when under mate threat doesn't hurt the branching factor as much as some random extension, because most moves won't counter the threat, they'll only be searched 1 ply deep (at which point mate is declared) no matter how much depth is remaining. Currently I extend 1/2 a ply when there's a mate threat, and also test for some specific mate threats before calling the Q-search. (One of the specific mate threats is mating-touch-checks with the queen when the enemy king as at the edge of the board.) I ignore many kinds of mate threats, so there's still room for a lot of improvement here.
King Safety Extensions: I added a few odd King Safety extensions to keep things interesting, so sometimes when a side has attacking chances, classic bishop sacs( or knight sacs) or a queen move that gains control of all squares around an enemy king on the edge of the board are extended more. (There are some limitations, like sometimes requiring a move to be a capture, so these extensions don't get called too often.) These are kinda fun, I'll probably add more if I do more work on the search.
Recapture Extension: This one is probably the least important (or maybe just least noticeable.) Any time a piece captures another piece of a similar value, (RxR or BxN etc...) the square the capture takes place on is marked. If on the next ply the opponent captures on that square, the search is extended by 3/4ths of a ply. The idea is that recaptures are often the only reasonable move available, and therefore semi-forced, so it's good to look deeper into these lines. If the previous move was a check (and thus check extended), this only extends 1/4th of a ply.
Recapture to pawn endgame: I extend 2 ply when one side captures to a 0 piece endgame (and on the previous ply the other side captured a piece.) Pawn endgames generally don't take many nodes to search, but it's important to see if the pawn endgame entered is lost or won, and this definitely helps.
When to call the Quiesence search: Slow Chess doesn't always call the quiescence search when depth remaining is less than 1. (Note that since some of these extend anyway, for a couple of these this only matters if the search already has no depth remaning. I actually added the first two listed before I added the extensions.) It will continue with the main search if a) The side to move is in check. It could be mate or a fork, etc.. so keep searching. b) The last move was a pawn push, keep searching in case it can promote next move. c) The last move was a single-reply to check. This can allow Slow to see some very deep mates on low ply, if they end in checks/single responses. However I set a max search depth after which the Q-search is always called to be completely sure the search doesn't get bogged down too much. d) On the last move there were 2 replies to check and we haven't extended past the depth remaining already. This will find some mates 1 ply earlier.Chess Programming Links: Although I'd like to think Slow Chess is a pretty original chess program, I made extensive use of information available on the internet. Even some ideas I came up with myself I later found on webpages, so chances are if you come up with a good idea, something similar or the same has been done before. So it's a good idea to look over available info if you're want to make a chess program. (I want to put a caution here about looking *too* closesly at program source. It's more fun and satisfying to do your own, possibly original, implementation of ideas. ) Here are some links I found helpful:
Bob Hyatt - Download Crafty, an open source chess program. When I was starting chess programming I didn't understand the code at first glance and set it aside. Now I can understand the code much better, and it can be quite helpful looking at the eval and search (or just reading the comments there) even if your chess program is very different from Crafty.
Bruce Moreland - Chess programming info and the Gerbil program. Lots of good basic info on these pages. I looked at Gerbil to see how to interface my program to winboard. I also use the epd2wb to run test suites with Slow Chess.
Paul Verhelst - A collection of chess programming info, I remember looking at this page when I was starting work on Slow Chess 2. A recent look shows that most of the links there are now dead.
Ed Schröder - I've found this webpage by the author the the chess program Rebel more recently, and saw it explained well many of the ideas I was already using in Slow Chess, and quite a few new ones, two of which I have added, and the ones I haven't look interesting. I hope he'll finish the page someday.