using pseudo‐moves to improve engine performance

[zamfofex]

I have recently opened a thread about my own bot (“engine”) asking for advice on how to improve its speed: https://talkchess.com/forum3/viewtopic.php?f=7&t=80336

I realized that a lot of my issue has to do with the inefficient search algorithm I came up with (it simply traverses most/all nodes at a given depth). But the move generation algorithm seems fairly efficient from what I was able to tell! Forty million nodes per seconds using only one thread in a considerably low end computer if I measured appropriately. (Using the C program I shared lower into the thread.) My trick is: I only generate pseudo‐legal moves and ignore castling and e.p. moves.

The idea is that, at depth zero, I still consider all strictly valid moves, but at other depths, I use the more efficient pseudo‐move heuristic. The king may be captured, and is worth many points, which makes the bot naturally avoid putting the king in check.

My entire search and evaluation algorithm is stupid, but I wonder whether people who are more proficient than I am would be able to take this idea further. Has anyone ever used this kind of strategy in a reasonably decent bot? Does this idea have merit?

Of course, the bot wouldn’t be able to find strategies that involve castling and e.p., so it wouldn’t always be entirely accurate, but the hope would be that those would be far enough apart for that to not matter that much.

[hgm]

Most engines use pseudo-legal moves, and test for exposure of teh King only after the move is made. Sometimes even when generating the moves in the daughter node, although more efficient algorithms exist to test that. The point is that most moves do not put you in check, and having a dedicated test for their legality that is applied to all moves wastes a lot of time. Generating all moves and testing whether the most valuable victim that can be captured is a King takes longer than the dedicated test, but this is wasted time only in the rare case where the preceding move actually did expose the King.

Beware, though: treating the King merely as a high value piece does not work! You really should return the maximum score immediately when you detect the capture of a King, and not play it and search deeper, as you would on capture of, say, a Queen. The problem is that no matter how valuable you make the King, trading Kings would always be neutral. So a check might be replied to with a counter check. And then when you capture his King, the program retaliates by capturing yours.

Generating castlings or e.p. captures should not take much time, as it can only be done very rarely. Most of the game castling will not be possible, because it has already been done, or the King has been moved otherwise. E.p. capture can only be done after a Pawn double-push, which is also rare. If you just keep track of which castling rights exist (e.g. by an integer variable that contains 4 flags, one for each castling, and a board-size table that indicates which flas should be cleared when the corresponding square occurs in a move) you have a very fast first 'filter' by testing whether any of the two castling flags for that player are set. If not, you are done.

For e.p. the most common method is to pass the e.p. square to the daughter node, and only have a valid value for that after a double-push. The daughter node can then first test whether that e.p. square is valid, and if not (the most common case) it is done. If it is you can test if there are any Pawns of the side to move diagonally in front of it, and generate the e.p. captures for those.

I don't think there will be much speed gain by not thinking about e.p. or castling; especially e.p. can mean the difference between winning and losing in an end-game:


[fen]8/8/8/8/1p6/1P6/P2k4/7K w[/fen]

[zamfofex]

Thank you for the thorough answer! I guess the answer to my question is that my idea is (perhaps unsurprisingly) not innovative after all. I suppose what made me confused is how people usually talk about the efficiency of finding properly valid moves if that’s not something that actually matters for most chess programs.

Beware, though: treating the King merely as a high value piece does not work! You really should return the maximum score immediately when you detect the capture of a King, and not play it and search deeper, as you would on capture of, say, a Queen. The problem is that no matter how valuable you make the King, trading Kings would always be neutral. So a check might be replied to with a counter check. And then when you capture his King, the program retaliates by capturing yours.

I noticed that too. If you go through my code, you’ll see that besides considering the king a high‐value piece, I also terminate the search once either side doesn’t have a king.

Generating castlings or e.p. captures should not take much time, as it can only be done very rarely. […]

I don't think there will be much speed gain by not thinking about e.p. or castling; […]

I suppose so. To be honest, I elided those possibilities mostly for the sake of simplicity. Specially for castling, since I’d need to verify whether any of the squares the king passes through are being attacked, and also because I want my bot to be able to play chess 960 too. (If I wanted to be thorough.)

For e.p. the most common method is to pass the e.p. square to the daughter node, and only have a valid value for that after a double-push. The daughter node can then first test whether that e.p. square is valid, and if not (the most common case) it is done. If it is you can test if there are any Pawns of the side to move diagonally in front of it, and generate the e.p. captures for those.

In my program specifically, I make use of mutual recursion to perform the search, so it isn’t so trivial for me to just “pass an argument to the child node”. I’m sure there are better ways to write the algorithm I came up with, though I’m not really sure about what they are yet! At any rate, thank you for the advice.

[hgm]

A simple way to enforce castling legality is to generate pseudo-legal castlings (i.e. not caring whether they move into, out of or through check), and weed out the illegal ones in the daughter node. Also here aplies that they would be illegal only very rarely. You could for instance perform castling initially only as removing the Rook, and placing extra Kings on all squares that the King moved through, as well as the final destination square. When the opponent generates moves in the child node he would then see a King capture when the castling was illegal. Immediately after move generation you would finish the castling move by removing the extra Kings, and placing the Rook.