Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Xian-Xiang update

I have a working A* search using a pretty good heuristic. When it works, it works pretty well:


b3t y3t b4t y4x r4x b3d
g4x g1w y4t y3w y4d y1d
y1d b4w r4w b4w y1x r3w
b3t y4t y4w y1d g4w g3d
y3d b3x b4w b1w b4x y3d
Greedy solver gives minimum score: 5351
Visiting node w/ weight 30 score 0 f 8000 [Queue size 0 closed 1 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 49 children
Visiting node w/ weight 28 score 300 f 8000 [Queue size 48 closed 2 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 49 children
Visiting node w/ weight 26 score 350 f 7750 [Queue size 96 closed 3 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 49 children
Visiting node w/ weight 24 score 650 f 7750 [Queue size 144 closed 4 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 48 children
Visiting node w/ weight 22 score 950 f 7750 [Queue size 191 closed 5 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 44 children
Visiting node w/ weight 20 score 1250 f 7750 [Queue size 234 closed 6 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 47 children
Visiting node w/ weight 18 score 1550 f 7750 [Queue size 280 closed 7 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 42 children
Visiting node w/ weight 20 score 1250 f 7750 [Queue size 321 closed 8 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 47 children
Visiting node w/ weight 20 score 1250 f 7750 [Queue size 359 closed 9 dupsInQ 0 dupsAvoided 8 minrejected 0 ] 47 children
Visiting node w/ weight 18 score 2250 f 7750 [Queue size 399 closed 10 dupsInQ 3 dupsAvoided 14 minrejected 0 ] 45 children
Visiting node w/ weight 16 score 3250 f 7750 [Queue size 443 closed 11 dupsInQ 3 dupsAvoided 14 minrejected 0 ] 38 children
Visiting node w/ weight 16 score 3250 f 7750 [Queue size 480 closed 12 dupsInQ 3 dupsAvoided 14 minrejected 0 ] 47 children
Visiting node w/ weight 14 score 3550 f 7750 [Queue size 520 closed 13 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 41 children
Visiting node w/ weight 12 score 3850 f 7750 [Queue size 560 closed 14 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 38 children
Visiting node w/ weight 10 score 4150 f 7750 [Queue size 597 closed 15 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 26 children
Visiting node w/ weight 8 score 5150 f 7750 [Queue size 622 closed 16 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 17 children
Visiting node w/ weight 6 score 6150 f 7750 [Queue size 638 closed 17 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 5 children
Visiting node w/ weight 4 score 6450 f 7750 [Queue size 642 closed 18 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 3 children
Visiting node w/ weight 2 score 6750 f 7750 [Queue size 644 closed 19 dupsInQ 3 dupsAvoided 20 minrejected 0 ] 1 children
Visiting node w/ weight 0 score 7750 f 7750 [Queue size 644 closed 20 dupsInQ 3 dupsAvoided 20 minrejected 0 ] Solution found.
(0,4)-(5,4) 7750
(1,4)-(4,4) 6750
(2,4)-(3,4) 6450
(0,0)-(0,3) 6150
(0,2)-(3,3) 5150
(4,0)-(0,1) 4150
(1,1)-(4,3) 3850
(3,0)-(4,2) 3550
(1,2)-(3,2) 3250
(2,1)-(1,3) 2250
(2,2)-(2,3) 1250
(5,0)-(5,3) 950
(3,1)-(5,2) 650
(1,0)-(2,0) 350
(4,1)-(5,1) 300


y4w b1x r3d r4t y1t b1x
g1x g4w g3x g3x r4x b3t
y3w y4w b4w b1w g4d r3t
r1x y3w b3x y4d r3w r3x
g1t y1d r3t b3d b3w g4w
Greedy solver gives minimum score: 6350
Visiting node w/ weight 30 score 0 f 8700 [Queue size 0 closed 1 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 49 children
...
Visiting node w/ weight 0 score 8450 f 8450 [Queue size 2751 closed 68 dupsInQ 34 dupsAvoided 186 minrejected 0 ] Solution found.
(0,1)-(0,3) 8450
(0,2)-(1,3) 8150
(0,0)-(1,2) 7150
(1,1)-(5,4) 6150
(1,0)-(5,0) 5150
(4,0)-(0,4) 4150
(4,3)-(5,3) 3850
(2,0)-(1,4) 3550
(5,2)-(2,4) 3500
(5,1)-(2,3) 2500
(3,0)-(4,1) 2200
(2,1)-(3,1) 1900
(3,4)-(4,4) 900
(4,2)-(3,3) 600
(2,2)-(3,2) 300


Weight == number of pieces remaining
score == score
f == A* f(x) measure == sum of score + heuristic
closed == positions visited
dupsInQ == duplicate positions in queue for which a better score has been found
dupsAvoided == duplicate positions generated but not added to queue due to existing >= score
minrejected == positions generated but not explored due to low heuristic

But when it's bad, it's pretty awful:

r3t y1x g1d y4t y1t r4w
y3w r1t y3t b4t g3x y1t
g3d b4t y3x r4w y3t r1w
b4x r1t r4d y3w r1x r1w
r1x b4w r1d r3t y4t r1d
b4d g1t r1t g3w g4t b1w
Greedy solver gives minimum score: 9100
Visiting node w/ weight 36 score 0 f 12801 [Queue size 0 closed 1 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 60 children
Visiting node w/ weight 34 score 1000 f 12850 [Queue size 59 closed 2 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 60 children
Visiting node w/ weight 32 score 1050 f 12850 [Queue size 118 closed 3 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 64 children
Visiting node w/ weight 34 score 50 f 12850 [Queue size 181 closed 4 dupsInQ 0 dupsAvoided 0 minrejected 0 ] 64 children
Visiting node w/ weight 32 score 1001 f 12801 [Queue size 243 closed 5 dupsInQ 0 dupsAvoided 1 minrejected 0 ] 60 children
Visiting node w/ weight 32 score 1300 f 12801 [Queue size 296 closed 6 dupsInQ 1 dupsAvoided 7 minrejected 0 ] 60 children
Visiting node w/ weight 30 score 1301 f 12801 [Queue size 353 closed 7 dupsInQ 1 dupsAvoided 9 minrejected 0 ] 58 children
Visiting node w/ weight 32 score 1001 f 12801 [Queue size 410 closed 8 dupsInQ 1 dupsAvoided 9 minrejected 0 ] 58 children
Visiting node w/ weight 34 score 300 f 12801 [Queue size 464 closed 9 dupsInQ 1 dupsAvoided 12 minrejected 0 ] 60 children
...
Visiting node w/ weight 34 score 50 f 12150 [Queue size 11569 closed 224 dupsInQ 316 dupsAvoided 1482 minrejected 0 ] 60 children
Visiting node w/ weight 30 score 1600 f 12101 [Queue size 11612 closed 225 dupsInQ 321 dupsAvoided 1498 minrejected 0 ] 59 children
Visiting node w/ weight 30 score 1301 f 12101 [Queue size 11662 closed 226 dupsInQ 327 dupsAvoided 1506 minrejected 0 ] 60 children
Visiting node w/ weight 30 score 1301 f 12101 [Queue size 11710 closed 227 dupsInQ 329 dupsAvoided 1517 minrejected 0 ] 60 children
Visiting node w/ weight 32 score 1300 f 12101 [Queue size 11757 closed 228 dupsInQ 336 dupsAvoided 1529 minrejected 0 ] 59 children
Visiting node w/ weight 32 score 600 f 12101 [Queue size 11800 closed 229 dupsInQ 340 dupsAvoided 1544 minrejected 0 ] 60 children
Visiting node w/ weight 32 score 301 f 12101 [Queue size 11850 closed 230 dupsInQ 346 dupsAvoided 1553 minrejected 0 ] 60 children
Visiting node w/ weight 32 score 301 f 12101 [Queue size 11896 closed 231 dupsInQ 353 dupsAvoided 1566 minrejected 0 ] 60 children


(Killed, memory usage approaching 1GB.)


So, I haven't successfully solved any 6x6 or 7x6 instances. For this size there seems to be a lot of work involved in determining that a f-value is unattainable.

This is making me wonder whether it's better to explore the clique space directly. That is, come up with a matching and test whether it's feasible rather than using the idealized matchings as a heuristic.

Alternately, the clique could maybe be used to trim the search space--- there's no sense trying multiple orders to satisfy the same clique, but A* will try anyway... trimmed a little bit by duplicate position detection.

Recap of comments in last post: the heuristic I'm using is to pick a set of matchings--- a clique--- that are all pairwise compatible and maximize score. This set might be infeasible because of a three-way (or more) interaction or because it doesn't contain any adjacent matchings to get started.
Tags: algorithm, games, programming
Subscribe
  • Post a new comment

    Error

    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.
  • 3 comments