H. G. Muller wrote on Sat, May 25, 2019 06:40 AM UTC:
I currently put an extra ~ in the names compared to what I proposed here earlier: A~B~(C) instead of A~B(C). This looked more balanced (the latter form suggested a tighter coupling between B and C). This would also make it possible to recognize '1-parameter' sub-variants by the ~ alone, e.g. bird~(10x8), carrera~(10x8).
Name explosion would occur when a sub-variant needs multiple parameters (such as CwDA); with a single parameter the possible parameter values would have to be mentioned anyway. We could solve it by introducing wildcards for the parameters: nutters~*~(cwda) would mean the variant group 'cwda' has two parameters, and 'nutters' would be a possible value for the first parameter. Such a partial variant declaration would be discarded if there weren't also declarations of the form *~rookies~(cwda) in the variants feature to specify some possible values for the second parameter. This is not backward compatible with existing GUIs, though; these would not recognize the * as wildcard, and take the names litterally. This problem could be ameliorated by making the engine such that it would also accept the names with the wildcard in it in the 'variant' command, and would treat the parameter value * as a command to keep the previous value of that parameter. A user could then still make the selection Nutters vs Rookies by first selecting nutters~*~(cwda), and then switch to *~rookies~(cwda). (On second thought, we could adopt the convention that a second parameter that is only given as a wildcard in all the supported sub-variants would be assumed by the GUI to allow the same values as the first parameter. The engine, when confronted with * for this parameter, could then use the previous value of the first parameter for it.)
BTW, many of the problems you mention for Cylinder Chess sound familiar. I remember that at some point of implementing XBetza support in XBoard I decided moves should be generated after 'lifting' the moving piece off the board, in order to allow bent multi-leg moves to pass back over itself (e.g. for igui). That caused XBoard to hang with an oR on an empty rank... I solved it by making the Betza-driven move generator such that it would treat all slides as finite-range slides with the maximum board dimension minus 1 as range. If you already support finite range slides, this would cause no extra overhead.
SEE is indeed troublesome, if there are pieces with fancy moves. But like you say, it isn't really necessary. Pure MVV/LVA already is pretty good, and Fairy-Max gets by with only sorting the MVV/LVA-wise best move in front, and searching the other captures in arbitrary order. My guess is that >90% of the beneficial effect of SEE comes from detecting if a piece is completely unprotected, so that HxL captures on it are safe. So I often use the simpler algorithm BLIND, which postpones HxL capture of protected pieces compared to MVV/LVA. This still requires you to know whether a piece is protected, though. The null-move reply could have told you, but in QS there is no null move. You could get (somewhat inaccurate) protection information as a side effect from the move generation that was done in the parent; this could have marked all pieces that block friendly captures as protected (e.g. in a bitmap of the board or of the piece list, or even a (packed?) set of counters, to be able to correct single protection for the piece that was moved).
KingSlayer uses MVV/LVA, but it has a provision to initially abort the search of HxL captures that go sour, to reschedule them until after the other captures have been searched. To this end it can pass the value of the victim as 'threshold' to the child. When that child then generates a capture of a piece more valuable than 'threshold' on that same square (which it would after H x protected L), it immediately returns 'abort score' INF+1 (so the caller can see that the capture was bad and needs to be rescheduled). As an extra it would also abort if the 'obvious gain' from capture on a different square would exceed 'threshold'. Where that gain is defined as the value of the victim if unprotected, or the difference between victim and attacker value if protected. This protection information is obtained from the parent (inaccurate as it is, but only used in 'second order'). Normally you would only abort on capture of a King (returning +INF, as no rescheduling is needed), i.e. use threshold = INF-1. This is what is done during the search of the rescheduled captures, to prevent it would abort again.
Duplicat moves are not really a very large problem; the duplicat should give a hash hit that makes it fail low immediately. Bifurcating pieces (e.g. bent sliders like the Griffon) also tend to produce them, if you are not careful to define the overlapping part of one of the branches as a lame leap.
Bent sliders (including the ski-jump case) are pretty nasty anyway. They blur the distinction single vs double check, as beside offering the possibility for triple (or even quadruple) check, they can cause double check to occur along a single path. So that contrary to normal double check, it can be resolved by interposition (but still not by capture of the checker). The ski-slide of the Wyvern thoroughly wrecks KingSlayer's implementation of check detection and handling. Perhaps I should not spent further time on that now, and try to get the other armies working as quickly as possible.
In that case I am nearly there; I have implemented a rather general material evaluation that reproduces the general trend of the EGT results, driven by a 32-bit 'properties' word for each piece type. The even bits in this word are used as flags to indicate whether that piece has the corresponding property (e.g. mating potential, color binding, lacking mating potential even as a pair, being rather weak for a major, etc.). As I won't do any score discounting with more than 2 pieces for each side, the property words can be added for each player, and when both pieces have a certain property, this cause a carry to the (originally unused) next-higher (odd) bit. This makes it easy to recognize conditions like having two majors (almost always a win), having a pair of Knights (draw), having only minors (draw against any defender), etc. Pieces with the 'super-piece' property will use a 2-bit field in the properties word to indicate their ranking, so that we can decide whether an extra minor on their side will make it a win.
It also detects uneven distribution of color-bound pieces over the square shades, to penalize that by a fixed score (which is equivalent to awarding a pair bonus), and declaring a draw when it happens to the only two pieces in absence of Pawns. And when both sides have full color binding on opposite shades it will discount the evaluation by a factor 2 even with many Pawns. This seems to capture the most important effects. I guess I could still have it invoke the existing code for detecting a KBP.K draw in all cases where the only remaining piece is color bound.
I currently put an extra ~ in the names compared to what I proposed here earlier: A~B~(C) instead of A~B(C). This looked more balanced (the latter form suggested a tighter coupling between B and C). This would also make it possible to recognize '1-parameter' sub-variants by the ~ alone, e.g. bird~(10x8), carrera~(10x8).
Name explosion would occur when a sub-variant needs multiple parameters (such as CwDA); with a single parameter the possible parameter values would have to be mentioned anyway. We could solve it by introducing wildcards for the parameters: nutters~*~(cwda) would mean the variant group 'cwda' has two parameters, and 'nutters' would be a possible value for the first parameter. Such a partial variant declaration would be discarded if there weren't also declarations of the form *~rookies~(cwda) in the variants feature to specify some possible values for the second parameter. This is not backward compatible with existing GUIs, though; these would not recognize the * as wildcard, and take the names litterally. This problem could be ameliorated by making the engine such that it would also accept the names with the wildcard in it in the 'variant' command, and would treat the parameter value * as a command to keep the previous value of that parameter. A user could then still make the selection Nutters vs Rookies by first selecting nutters~*~(cwda), and then switch to *~rookies~(cwda). (On second thought, we could adopt the convention that a second parameter that is only given as a wildcard in all the supported sub-variants would be assumed by the GUI to allow the same values as the first parameter. The engine, when confronted with * for this parameter, could then use the previous value of the first parameter for it.)
BTW, many of the problems you mention for Cylinder Chess sound familiar. I remember that at some point of implementing XBetza support in XBoard I decided moves should be generated after 'lifting' the moving piece off the board, in order to allow bent multi-leg moves to pass back over itself (e.g. for igui). That caused XBoard to hang with an oR on an empty rank... I solved it by making the Betza-driven move generator such that it would treat all slides as finite-range slides with the maximum board dimension minus 1 as range. If you already support finite range slides, this would cause no extra overhead.
SEE is indeed troublesome, if there are pieces with fancy moves. But like you say, it isn't really necessary. Pure MVV/LVA already is pretty good, and Fairy-Max gets by with only sorting the MVV/LVA-wise best move in front, and searching the other captures in arbitrary order. My guess is that >90% of the beneficial effect of SEE comes from detecting if a piece is completely unprotected, so that HxL captures on it are safe. So I often use the simpler algorithm BLIND, which postpones HxL capture of protected pieces compared to MVV/LVA. This still requires you to know whether a piece is protected, though. The null-move reply could have told you, but in QS there is no null move. You could get (somewhat inaccurate) protection information as a side effect from the move generation that was done in the parent; this could have marked all pieces that block friendly captures as protected (e.g. in a bitmap of the board or of the piece list, or even a (packed?) set of counters, to be able to correct single protection for the piece that was moved).
KingSlayer uses MVV/LVA, but it has a provision to initially abort the search of HxL captures that go sour, to reschedule them until after the other captures have been searched. To this end it can pass the value of the victim as 'threshold' to the child. When that child then generates a capture of a piece more valuable than 'threshold' on that same square (which it would after H x protected L), it immediately returns 'abort score' INF+1 (so the caller can see that the capture was bad and needs to be rescheduled). As an extra it would also abort if the 'obvious gain' from capture on a different square would exceed 'threshold'. Where that gain is defined as the value of the victim if unprotected, or the difference between victim and attacker value if protected. This protection information is obtained from the parent (inaccurate as it is, but only used in 'second order'). Normally you would only abort on capture of a King (returning +INF, as no rescheduling is needed), i.e. use threshold = INF-1. This is what is done during the search of the rescheduled captures, to prevent it would abort again.
Duplicat moves are not really a very large problem; the duplicat should give a hash hit that makes it fail low immediately. Bifurcating pieces (e.g. bent sliders like the Griffon) also tend to produce them, if you are not careful to define the overlapping part of one of the branches as a lame leap.
Bent sliders (including the ski-jump case) are pretty nasty anyway. They blur the distinction single vs double check, as beside offering the possibility for triple (or even quadruple) check, they can cause double check to occur along a single path. So that contrary to normal double check, it can be resolved by interposition (but still not by capture of the checker). The ski-slide of the Wyvern thoroughly wrecks KingSlayer's implementation of check detection and handling. Perhaps I should not spent further time on that now, and try to get the other armies working as quickly as possible.
In that case I am nearly there; I have implemented a rather general material evaluation that reproduces the general trend of the EGT results, driven by a 32-bit 'properties' word for each piece type. The even bits in this word are used as flags to indicate whether that piece has the corresponding property (e.g. mating potential, color binding, lacking mating potential even as a pair, being rather weak for a major, etc.). As I won't do any score discounting with more than 2 pieces for each side, the property words can be added for each player, and when both pieces have a certain property, this cause a carry to the (originally unused) next-higher (odd) bit. This makes it easy to recognize conditions like having two majors (almost always a win), having a pair of Knights (draw), having only minors (draw against any defender), etc. Pieces with the 'super-piece' property will use a 2-bit field in the properties word to indicate their ranking, so that we can decide whether an extra minor on their side will make it a win.
It also detects uneven distribution of color-bound pieces over the square shades, to penalize that by a fixed score (which is equivalent to awarding a pair bonus), and declaring a draw when it happens to the only two pieces in absence of Pawns. And when both sides have full color binding on opposite shades it will discount the evaluation by a factor 2 even with many Pawns. This seems to capture the most important effects. I guess I could still have it invoke the existing code for detecting a KBP.K draw in all cases where the only remaining piece is color bound.
Still have to test everything, though.