📝Greg Strong wrote on Sat, Jan 6, 2018 03:29 AM UTC:
Do these "rules of thumb" work for the huygens chess piece? As far as I know this piece does not appear in any chess engines, but it could be a good exercise to test the robustness of any new code.
Thanks, that is an excellent idea. Although I've never added the Huygens, it should work and consider the entire board to be one slice, since the Huygens has no color-binding. It cannot move a single space directly, but since it can leap three forward, and then two back, it can effectively move a single space, and the recursive algorithm would find this.
That said, it seems that we have other problems. I've had this algorithm for a while, but since it wasn't really used for much, any issues went unnoticed. I now notice that we do, indeed, have some issues, and it is nothing so fancy as the Huygens. The problems start with the venerable chess pawn...
A pawn placed on a1 cannot visit the whole board, only a little over half the board. So it considers that triangular-shaped half the first slice. (Nevermind that a pawn cannot even exist on a1, that's a whole 'nother problem.) Since this did not find the whole board, it detects the second slice by throwing a pawn on b1 - but this only finds 7 more squares! For slice three, throw a pawn on c1 and find 6 more squares ... Obviously, this is not at all what we want to happen. In fact, as far as the pawn goes, I'm not even sure what the theoretically correct answer is, although I'm quite sure this ain't it. A slight improvement would be to ignore the pawn's capture-only moves on the grounds that it might never have the opportunity to do that. This would leave each file as a separate slice. There is some logic to this. It might even be the correct answer to some questions. But, for purposes of making a material hash table, to detect draws by insufficient material and probably do other groovy stuff as well, I believe we want to consider all pawns to be identical (although I'm not 100% sure of that either...) So I guess the pawn just gets a special flag that tells the system to treat it as though it is not colorbound even though it really is.
The pawn also points out another potential problem with this algorithm. It begins by visiting the "first" space. This, for the pawn, was bad, but not truely terrible because it considered a1 to be the "first" space. But what if pawns went backwards instead of forwards? Now instead of considering the board to be split into 8 different slices, it would be split into 64 different slices! Clearly, for asymmetric pieces, the choice of which square to visit first is very important. I can see two potential ways to deal with this. First, we can look at how the piece moves and then be wicked smart about which square to visit first. This would be awesome, but I'm not sure how to determine this (it makes my head hurt, and, frankly, I'm just not that smart.) And I'm not 100% sure that there even is a best answer for all kinds of pieces. The other possible solution is to leave it as-is, with the addition that when we are doing our recursive analysis to detect a new slice, if we happen to stumble across a square that we have visited while discovering a previous slice, we now need to consider this new traversal to be part of that original slice. I think this approach is solid, although the algorithm is now becoming more complicated ... But, well, that's why this particular project fascinates me so much. The various interesting issues to ponder are practically never-ending.
Another potential issue, alluded to above - we probably only want to consider squares to which a piece can theoretically move. It doesn't matter what a pawn on the first rank can do. But for a better example, consider: Pocket Knight. The knight "drop" is not really a normal move, so I think (although I'm not sure) that our fancy colorbinding-detector should not consider it. Therefore, it should consider the knight to see the board as three separate slices (three different meta-colors) - the main board, White's pocket square, and Black's pocket square. Groovy. But what we don't want to happen is for it to then consider the bishop to also have three meta-colors, since the bishop isn't in the pocket and can't go there. So this would be the next change to the algorithm - don't find the entire board when the game is created. Only start this process when a piece is actually placed on a square and that square hasn't been visited yet (meaning it hasn't yet been segregated into any given slice.) Strangely, this is how the old C++ ChessV used to do it. I changed it because I thought I was simplifying things, when apparently I was breaking things :)
One final random thought ... If a piece type has two meta-colors, you can NOT assume that it is equivalent to all other pieces with two meta-colors. Example: Alice Chess. In Alice Chess, both the Knight and the Bishop can see exactly 50% of the squares. But their color-bindings are NOT the same!
Thanks, that is an excellent idea. Although I've never added the Huygens, it should work and consider the entire board to be one slice, since the Huygens has no color-binding. It cannot move a single space directly, but since it can leap three forward, and then two back, it can effectively move a single space, and the recursive algorithm would find this.
That said, it seems that we have other problems. I've had this algorithm for a while, but since it wasn't really used for much, any issues went unnoticed. I now notice that we do, indeed, have some issues, and it is nothing so fancy as the Huygens. The problems start with the venerable chess pawn...
A pawn placed on a1 cannot visit the whole board, only a little over half the board. So it considers that triangular-shaped half the first slice. (Nevermind that a pawn cannot even exist on a1, that's a whole 'nother problem.) Since this did not find the whole board, it detects the second slice by throwing a pawn on b1 - but this only finds 7 more squares! For slice three, throw a pawn on c1 and find 6 more squares ... Obviously, this is not at all what we want to happen. In fact, as far as the pawn goes, I'm not even sure what the theoretically correct answer is, although I'm quite sure this ain't it. A slight improvement would be to ignore the pawn's capture-only moves on the grounds that it might never have the opportunity to do that. This would leave each file as a separate slice. There is some logic to this. It might even be the correct answer to some questions. But, for purposes of making a material hash table, to detect draws by insufficient material and probably do other groovy stuff as well, I believe we want to consider all pawns to be identical (although I'm not 100% sure of that either...) So I guess the pawn just gets a special flag that tells the system to treat it as though it is not colorbound even though it really is.
The pawn also points out another potential problem with this algorithm. It begins by visiting the "first" space. This, for the pawn, was bad, but not truely terrible because it considered a1 to be the "first" space. But what if pawns went backwards instead of forwards? Now instead of considering the board to be split into 8 different slices, it would be split into 64 different slices! Clearly, for asymmetric pieces, the choice of which square to visit first is very important. I can see two potential ways to deal with this. First, we can look at how the piece moves and then be wicked smart about which square to visit first. This would be awesome, but I'm not sure how to determine this (it makes my head hurt, and, frankly, I'm just not that smart.) And I'm not 100% sure that there even is a best answer for all kinds of pieces. The other possible solution is to leave it as-is, with the addition that when we are doing our recursive analysis to detect a new slice, if we happen to stumble across a square that we have visited while discovering a previous slice, we now need to consider this new traversal to be part of that original slice. I think this approach is solid, although the algorithm is now becoming more complicated ... But, well, that's why this particular project fascinates me so much. The various interesting issues to ponder are practically never-ending.
Another potential issue, alluded to above - we probably only want to consider squares to which a piece can theoretically move. It doesn't matter what a pawn on the first rank can do. But for a better example, consider: Pocket Knight. The knight "drop" is not really a normal move, so I think (although I'm not sure) that our fancy colorbinding-detector should not consider it. Therefore, it should consider the knight to see the board as three separate slices (three different meta-colors) - the main board, White's pocket square, and Black's pocket square. Groovy. But what we don't want to happen is for it to then consider the bishop to also have three meta-colors, since the bishop isn't in the pocket and can't go there. So this would be the next change to the algorithm - don't find the entire board when the game is created. Only start this process when a piece is actually placed on a square and that square hasn't been visited yet (meaning it hasn't yet been segregated into any given slice.) Strangely, this is how the old C++ ChessV used to do it. I changed it because I thought I was simplifying things, when apparently I was breaking things :)
One final random thought ... If a piece type has two meta-colors, you can NOT assume that it is equivalent to all other pieces with two meta-colors. Example: Alice Chess. In Alice Chess, both the Knight and the Bishop can see exactly 50% of the squares. But their color-bindings are NOT the same!
Fun stuff!!!