algorithm - A* Admissible Heuristic for die rolling on grid -
i need finding heuristic following problem:
you given
r-by-cgrid , six-sided die. letstart,end2 distinct cells on grid. find pathstartendsuch sum of faces of die looking up, die turning along path, minimal.the starting orientation of die following (the "2" facing south):
the way modeled problem considering value of die's face cost of edge in graph. graph's vertices of form (row, col, die) (i.e, position in grid , current state/orientation of die). reason vertex not (row, col) because can end on same cell multiple configurations/orientations of die.
i used a* find solution problem; answers given correct, not efficient enough. i've determined problem heuristic i'm using. i'm using manhattan distance, admissible. if multiply heuristic constant, it's no longer admissible: runs faster doesn't find right answer.
i need in finding better heuristic manhattan distance.
here's algorithm applied paul's example of 300x300 grid, starting (23,25) , ending @ (282, 199). finds minimum path , sum (1515, 2 points less paul's result of 1517) in 0.52 seconds. version look-up tables instead of calculating small sections took 0.13 seconds.
haskell code:
import data.list (minimumby) import data.ord (comparing) import control.monad (guard) rolldie die@[left,right,top,bottom,front,back] move | move == "u" = [left,right,front,back,bottom,top] | move == "d" = [left,right,back,front,top,bottom] | move == "l" = [top,bottom,right,left,front,back] | move == "r" = [bottom,top,left,right,front,back] dietop die = die!!2 --diestartingorientation = [4,3,1,6,2,5] --left,right,top,bottom,front,back rows = 300 columns = 300 paths (startrow,startcolumn) (endrow,endcolumn) diestartingorientation = solve (dietop diestartingorientation,[]) [(startrow,startcolumn)] diestartingorientation leftborder = max 0 (min startcolumn endcolumn) rightborder = min columns (max startcolumn endcolumn) topborder = endrow bottomborder = startrow solve result@(cost,moves) ((i,j):pathtail) die = if (i,j) == (endrow,endcolumn) [(result,die)] else ((i',j'),move) <- ((i+1,j),"u"):next guard (i' <= topborder && i' >= bottomborder && j' <= rightborder && j' >= leftborder) solve (cost + dietop (rolldie die move),move:moves) ((i',j'):(i,j):pathtail) (rolldie die move) next | null pathtail = [((i,j+1),"r"),((i,j-1),"l")] | head pathtail == (i,j-1) = [((i,j+1),"r")] | head pathtail == (i,j+1) = [((i,j-1),"l")] | otherwise = [((i,j+1),"r"),((i,j-1),"l")] --300x300 grid starting @ (23, 25) , ending @ (282,199) applicationnum = let (r,c) = (282-22, 199-24) numrowreductions = floor (r/4) - 1 numcolumnreductions = floor (c/4) - 1 minimalr = r - 4 * frominteger numrowreductions minimalc = c - 4 * frominteger numcolumnreductions in (fst . fst . minimumby (comparing fst) $ paths (1,1) (minimalr,minimalc) [4,3,1,6,2,5]) + 14*numrowreductions + 14*numcolumnreductions applicationpath = [firstleg] ++ secondleg ++ thirdleg ++ [((0,["r"]),[])] ++ [minimumby (comparing fst) $ paths (1,1) (2,4) die2] (r,c) = (282-22, 199-24) --(260,175) numrowreductions = floor (r/4) - 1 numcolumnreductions = floor (c/4) - 1 minimalr = r - 4 * frominteger numrowreductions minimalc = c - 4 * frominteger numcolumnreductions firstleg = minimumby (comparing fst) $ paths (1,1) (minimalr,minimalc) [4,3,1,6,2,5] die0 = snd firstleg secondleg = tail . foldr mfs0 [((0,["r"]),die0)] $ [1..numcolumnreductions - 1] die1 = snd . last $ secondleg thirdleg = tail . foldr mfs1 [((0,[]),die1)] $ [1..numrowreductions - 3 * div (numcolumnreductions - 1) 4 - 1] die2 = rolldie (snd . last $ thirdleg) "r" mfs0 b = b ++ [((0,["r"]),[])] ++ [minimumby (comparing fst) $ paths (1,1) (4,4) (rolldie (snd . last $ b) "r")] mfs1 b = b ++ [((0,["u"]),[])] ++ [minimumby (comparing fst) $ paths (1,1) (4,1) (rolldie (snd . last $ b) "u")] output:
*main> applicationnum 1515 *main> applicationpath [((31,["r","r","r","r","u","u","r","u","r"]),[5,2,1,6,4,3]) ,((0,["r"]),[]),((25,["r","r","r","u","u","u"]),[3,4,1,6,5,2]) ,((0,["r"]),[]),((24,["r","u","r","r","u","u"]),[5,2,1,6,4,3]) ................((17,["r","r","r","u"]),[5,2,1,6,4,3])] (0.52 secs, 32093988 bytes) list of "r" , "u":
*main> let listrl = concatmap (\((a,b),c) -> b) applicationpath *main> listrl ["r","r","r","r","u","u","r","u","r","r","r","r","r","u","u","u","r","r","u","r" ..."u","r","r","r","r","u"] sum of path using starting die , list of "r" , "u":
*main> let sumpath path = foldr (\move (cost,die) -> (cost + dietop (rolldie die move), rolldie die move)) (1,[4,3,1,6,2,5]) path *main> sumpath listrl (1515,[5,2,1,6,4,3]) calculation of (r,c) (1,1) using list of "r" , "u" (since start @ (1,1,), (r,c) gets adjusted (282-22, 199-24):
*main> let rc path = foldr (\move (r,c) -> if move == "r" (r,c+1) else (r+1,c)) (1,1) path *main> rc listrl (260,175)
algorithm/solution
continuing research below, seems minimal face-sum path (mfs) can reduced, mod 4, either rows or columns so: mfs (1,1) (r,c) == mfs (1,1) (r-4,c) + 14, r > 7 == mfs (1,1) (r,c-4) + 14, c > 7 makes finding number minimal path straightforward: mfs (1,1) (r,c) = let numrowreductions = floor (r/4) - 1 numcolumnreductions = floor (c/4) - 1 minimalr = r - 4 * numrowreductions minimalc = c - 4 * numcolumnreductions in mfs (1,1) (minimalr,minimalc) + 14*numrowreductions + 14*numcolumnreductions minimalr , minimalc less eight, means can pre-calculate minimal-face-sums these , use table output overall solution. but how find path?
from testing, seems work out similarly:
mfs (1,1) (1,anything) = trivial mfs (1,1) (anything,1) = trivial mfs (1,1) (r,c), r,c < 5 = calculate solution in favorite way mfs (1,1) (r,c), either or both r,c > 4 = mfs (1,1) (minimalr,minimalc) -> roll -> mfs (1,1) (min 4 r-1, min 4 c-1) -> roll -> ...sections must arranged last 1 includes 4 rotations 1 axis , @ least 1 other. keeping 1 row or column same till end seems work. (for paul's example above, after initial mfs box, moved in fours along x-axis, rolling 4x4 boxes right, means y-axis advanced in threes , section in fours going up, until last box of 2x4. suspect, haven't checked, sections must divide @ least 1 axis in fours work)... mfs (1,1) (either (if r > 4 4 else min 2 r, 4) or (4, if c > 4 4 else min 2 c)) => (r,c) reached for example,
mfs (1,1) (5,13) = mfs (1,1) (1,5) -> roll right -> mfs (1,1) (1,4) -> roll right -> mfs (1,1) (5,4) mfs (1,1) (2,13) = mfs (1,1) (1,5) -> roll right -> mfs (1,1) (1,4) -> roll right -> mfs (1,1) (2,4)
properties of dice observed in empirical testing
for target points farther (1,1) (2,3), example (1,1) (3,4) or (1,1) (4,6), minimum path top-face-sum (mfs) equal if reverse target (r,c). in other words: 1. mfs (1,1) (r,c) == mfs (1,1) (c,r), r,c > 2 not that.
2. mfs (1,1) (r,c) == mfs (1,1) (r',c'), r,c,r',c' > 2 , r + c == r' + c' e.g., mfs (1,1) (4,5) == mfs (1,1) (5,4) == mfs (1,1) (3,6) == mfs (1,1) (6,3) but here's gets interesting:
the mfs target box (meaning startpoint endpoint) can reduced symmetrical combination of (r,c) (r,c) or (r,c) (c,r), r,c > 2, can expressed sum of mfs of 2 smaller symmetrical parts, if die-roll (the change in orientation) between 2 parts accounted for. in other words, if true, can breakdown calculation smaller parts, much faster. example: target-box (1,1) (7,6) can expressed as: (1,1) (4,3) -> roll right -> (1,1) (4,3) different starting orientation check it, baby: mfs (1,1) (7,6) = mfs (1,1) (4,3) + mfs (1,1) (4,3) (when accounting change in starting orientation, rolling right in between) eq. 2., implies mfs (1,1) (7,6) == mfs (1,1) (5,8) , mfs (1,1) (5,8) can expressed (1,1) (3,4) -> roll right -> (1,1) (3,4) check again: mfs (1,1) (7,6) = mfs (1,1) (5,8) = mfs (1,1) (3,4) + mfs (1,1) (3,4) (when accounting change in starting orientation, rolling right in between) not that.
the symmetrical parts can apparently combined in way: 3. mfs (1,1) (r,c) -> roll-right -> mfs (1,1) (r,c) equals mfs (1,1) (r,c) -> roll-right -> mfs (1,1) (c,r) equals mfs (1,1) (r,c) -> roll-up -> mfs (1,1) (r,c) equals mfs (1,1) (r,c) -> roll-up -> mfs (1,1) (c,r) equals mfs (1,1) (2*r-1, 2*c) equals mfs (1,1) (2*r, 2*c-1), r,c > 2
Comments
Post a Comment