R. Tomasi wrote: ↑Fri Sep 17, 2021 11:20 pm
I'm currently implementing futility pruning in Pygmalion. This is a part of the engine that I do not want to just transfer from my old engine, since I suspect that many of the instabilities and tactical weaknesses that I had in the old engine are due to a bad implementation of futility pruning. At the time I wrote the respective code, I did simply not grasp the concept fully.
Currently I have a working Implementation in Pygmalion that seems to be tactically stable. I do not prune moves that give check. Now, a straight-forward improvement would be to implement "general futility pruning" in a way that is similar to what HGM describes on his Micro-Max homepage (
https://home.hccnet.nl/h.g.muller/deepfut.html). However, I want to keep the philosophy of not pruning moves that give check. Therefore I would like to not prune the entire node, if the side to move might have a move that gives check.
Obviously, the whole idea of HGMs "general futility pruning" is to prune the node
before any moves are generated, therefore I do need a way to determine if such a move might exist in a fast way, without generating the moves. I am sure I will be able to come up with code that does that, but I guess other people (who are smarter than me) have already thought about this, so any ideas or hints are very welcome.
Assuming you mean does the move result in a check:
The quickest way to do that is with a pre-computed move matrix including every possible move a K,Q,R,B can make from each of 8 positions {64 * 9] = 576 elements on every square. A separate [64 *3] for pawns, and [64 * 9] for knights. Label the vectors 1-8, 9 for the knight and 10 for the king's square. I use [8,-8,1,-1,9,-9,7,-7], [7,9], [6, 10, 15, 17,-6,-10,-15,-17] for the knight.
Then, overlay the piece positions on the board, cutting off the vectors that intersect the Check array.
The rest is quick and easy, If a queen move falls anywhere on a vector marked 1-8, it's check. Rooks 1-4, and bishops 5- 8.
the Check array is computed before your search ply, so there's no looping, just a quick lookup. If there is no check the array vector will be 0, so simply multiply the Check vector square by the move. Zero = no check, non-zero = check.
This is very fast. It reduces the speed of my engine about 9%, but, it more than makes up for it in solution time.