Mark Gritter (markgritter) wrote,
Mark Gritter

Solving Xian-Xiang?

One of the Kado-Kado games, Xian-Xiang, is a perfect-information puzzle.

You are given a 6x7 tiled board; each square contains a playing piece that has a color, a shape, and a glyph:

The game proceeds by picking pairs of pieces that are connected by 1 or 2 rookwise moves over empty spaces. On the same row or column with no intervening pieces, or else a clear path along one of the minimum-length 'L's:

X.....X    XX    X     X...
                 X        .

You gain 1000 points if the pieces match all three attributes, 300 for two points of similarity, 50 for one matching attribute, or 1 pity point if there's no match at all. (The empty space doesn't have to be a single region like the example above. The '2's indicate that the player just made a partial match.)

I think this game is small enough to be computationally tractable, but it's not straightforward.

(1) Dynamic programming: Start with the empty board and play games backwards, noting the maximum score for each configuration visited. In addition to the rookwise rule, legal reverse moves should not separate the empty space into two odd-sized regions.

I implemented a prototype of this in Python (but without the odd-size check).

3x2: max size 15 @ 4 pieces
3x4: max size 906 @ 6 pieces
4x4: max size 12750 @ 8 pieces
3x6: max size 43730 @ 10 pieces

I thought that the maximum size should be far less than N choose N/2 but 16C8 = 12870 and 18C10 = 43758 so it is actually pretty close. (I can't see the odd-sized check making a huge difference here.) So unless we're prepared to deal with 42C20 =~ 5*10^11 entries in a row, this doesn't look feasible.

(2) Heuristic move search: For each configuration we ought to be able to identify a maximum score based on matches without the empty-space rule. Or, we could identify a guranteed minimum score based on a greedy algorithm. Neither of these bounds are likely to be tight enough to make an optimal answer feasible through searching just the space of moves.

(3) Subgoal search: The structure of the problem is that one perfect match is worth far more than an imperfect match. This suggests a hierarchal search where we first identify the largest possible set of perfect matches, assuming an otherwise empty board. Then, given those as fixed, we can try adding possible 300-point matches and look for the biggest feasible subset of those.

This search would miss cases where breaking a 1000-point match would give us 1200 points in 300-point matches, but those should be relatively rare. The algorithm could refine the answer by looking for those cases in a second pass, but it seems likely that there's a bound on how many 1000-point matches could possibly be worth breaking.

The biggest portion of the search is probably looking for 300-point matches. (This seems to be the case from playing the game, too.) Top scores of 14000 points and a typical 6-8 perfect matches (there must be at least 6 given the pigeonhole principle) leaves 20+ matches to search. We don't have to search all 20! cases; it should be feasible to identify ordering constraints. But, unfortunately, most will be of the form "A must be chosen after (X and Y) or (W and Z)" so it's closer to satisfiability than to mere order-checking.

(ETA: oops, the space is much worse than 20 matches because there will be multiple options for which partial match to take. Plus slotting them in between the perfect match ordering is nontrivial too.)
Tags: algorithm, games, programming
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.