Open nellore opened 7 years ago
Note there is a bandaid that doesn't require hacking annoy
: search for B
, I(B)
, F(B)
and I(F(B))
, and combine results.
On further reflection, I think the best way to solve this problem right now is to choose one of {B, I(B), F(B), I(F(B))}
to represent a board B
in the index. This way, the board index has fewer records---we don't care if we lose info about flips and color inversions. An easy way to implement this is as follows. Before checking if a board B
is in the index and adding it if it isn't, compute the ASCII representation of each of {B, I(B), F(B), I(F(B))}
. Now choose the one that's lexicographically smallest. (min()
function works for this.) Then when performing a search for a query board B
, search for each of {B, I(B), F(B), I(F(B))}
, and combine results.
I think left-right flips also give strategically identical boards! So let's use two functions f(B)
and F(B)
to represent the two kinds of flips, and then the set of strategically equivalent boards is {B, I(B), F(B), f(B), F(f(B)), F(I(B)), f(I(B)), F(I(f(B)))}
.
Consider inverting piece colors on a given board
B
to form a new boardI(B)
. The distance betweenB
andI(B)
could be large, but it makes sense for that distance to be zero; the game does not change from a strategic standpoint. The same is true if one flips the boardB
to form a new boardF(B)
. So we should use the corrected metricmin(d(X, Y), d(I(X), Y), d(F(X), Y), d(I(F(X)), Y))
given some uncorrected metricd(X, Y)
between two boardsX
andY
.