StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
16599424
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
13
CommunityOwnedDate
CreationDate
2013-05-17T00:06:43.327
FavoriteCount
0
LastActivityDate
2013-05-18T00:41:01.730
LastEditDate
2013-05-18T00:41:01.730
LastEditorUserId
834521
OwnerUserId
834521
ParentId
16547724
PostTypeId
2
Score
10
ViewCount
0
LastEditorDisplayName
text
Body
Main Edit 3: Proof that the optimal admissible heuristic should be based on <code>3.5m</code> The average cost of travelling along the board has to approach <code>3.5m</code> over the long run where <code>m</code> is the Manhattan distance. Therefore the best admissible heuristic should be <code>3.5m</code> plus or minus some small constant. The reason for this is that whenever you move in a direction, x, say, from face <code>x1</code>, the next move in the same direction, to face <code>x2</code> has to satisfy <code>x1 + x2 = 7</code>. This is because any moves in the perpendicular direction leave the orientation of face x2 the same. Think about rotating a die left to right -- the front and back faces stay the same no matter how many rotations you do. Conversely if you rotate a die front to back, the left and right faces stay the same. It's easiest to see this with some examples (all starting in the configuration pictured in the question) <pre><code> 6 2453 1 </code></pre> here you can see that we start with <code>y1=1</code>, and however many times we move in the x-direction afterwards, the next move in the y-direction has to be <code>y2=6</code>, so <code>y1+y2=7</code>. (Also in the x-direction, there is a simple pairing of <code>2+5 = 7</code> and <code>4+3 = 7</code>). Another example is <pre><code> 35 26 14 </code></pre> In this example we start with <code>x1=1</code>, and however many times we move in the y-direction afterwards, the next move in the x-direction has to be <code>x2=6</code>. (Also, we see pairings of <code>4+3=7</code> in the y-direction, <code>2+5=7</code> in the x-direction. And we know in this case the next move in the x-direction has to be <code>4</code>, and the next move in the y-direction has to be <code>1</code>.) This all assumes it's never worth backtracking, but hopefully this can be taken as read. The original post below just fills in some details of how the estimate of <code>3.5m</code> should be adjusted to take account of the ability for it to be beaten over the short term. As a side-note, as I just commented on the OP, A* search might not be required at all. It ought to make sense to simply choose a path made out of 4-long horizontal pieces and 4-long vertical pieces, say, which are optimal. And then make up the remainder with a search or a lookup table based on orientation and x-y offset. (But the question asks for an admissible heuristic so I'm going to leave my answer.) Main Edit 2: summarize original empirical work, taking account of comments below In the long term, as explained above, your average cost per move is 3.5. This can also can be seen empirically in the exploration of the data below. This gives a naive estimate of <code>3.5m</code> where <code>m</code> is the Manhattan distance. However this is an over-estimate, because in the short term it is possible to do better than the average. A good hypothesis for this is to explore how we can avoid using any faces larger than 3. <ul> <li>If we start with face 1, we can use faces 2 and 3 on our first 2 moves, going 2 moves better than <code>3.5m</code> predicts.</li> <li>If we start with face 2, we can use faces 1 and 3 on our first 2 moves, going 3 moves better than <code>3.5m</code> predicts.</li> <li>If we start with face 3, we can use faces 1 and 2 on our first 2 moves, going 4 moves better than <code>3.5m</code> predicts.</li> <li>If we start with face 4,5, or 6, we can use faces 1, 2 and 3 on our first 3 moves, going 4.5 moves better than <code>3.5m</code> predicts.</li> </ul> This hypothesis can be confirmed empirically by simply running the script below for every starting possibility of the die, as suggested by BlueRaja - Danny Pflughoeft. So a simple admissible statistic is <code>3.5m - k</code>, where <code>k = max(f+1, 4.5)</code>, and <code>f</code> is the starting face. But this is a bit klunky, giving negative numbers for small values of <code>m</code>. It's easy to write a programmatic version that takes account of whether you have just 1 or 2 or 3 moves to go, see below <pre><code> static double Adm(int x, int y, int face /* start face */, out int m) { double adm = 0; m = Math.Abs(x) + Math.Abs(y); if (m >= 1) { if (face == 1) adm += 2; else adm += 1; m--; } if (m >= 1) { if (face <= 2) adm += 3; else adm += 2; m--; } if (m >= 1 && face >=4) { // 4,5,6: we can still use a 3 without backtracking adm += 3; m--; } adm += 3.5 * m; return adm; } </code></pre> Running this across a search space with <code>|x|,|y| <= 100</code>, this function underestimates the actual cost by between 0 and 6, with a median of 0.5 or 1.5 depending on the start face. Main Edit 1: original post My basic thought was that it would be good to explore the data. So I had a go at <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm" rel="noreferrer">Dijkstra's algorithm</a> to see what the space of solutions looks like. What I found is supportive of what's been said already. Some factor times the Manhattan distance is appropriate, but there may be some justification for a higher factor than 1.5. This is nicely indicated by the shape of a contour plot of cost against deviation from initial x y position. <img src="https://i.stack.imgur.com/UFaUc.png" alt="cost against deviation from initial x y position"> Here's a wire frame plot -- to be honest this is just for eye candy. <img src="https://i.stack.imgur.com/QJOWY.png" alt="enter image description here"> What's interesting is that if you add another column to your data for the manhattan distance (man) and regress the cost (v) against the manhattan distance in R, you get the following <pre><code>Coefficients: Estimate Std. Error t value Pr(>|t|) (Intercept) -0.6408087 0.0113650 -56.38 <2e-16 df$man 3.4991861 0.0001047 33421.66 <2e-16 </code></pre> I.e. it's telling you that for every move you make horizontally or vertically, your cost is 3.4991861, or v close to 3.5. That just happens to be the average of 1 to 6, so my intuition is that the data is telling us that on average, it's most efficient to use all the faces of the die equally over a long distance. Over short distances you can be more optimal. I tried <code>3.5man - k</code> as an estimate, with <code>k = 2.5</code>. This seemed to work ok. When I subtracted the actual cost from this I got -0.5 as the highest value. <pre><code>> summary(df$est - df$v) Min. 1st Qu. Median Mean 3rd Qu. Max. -6.500 -2.500 -2.000 -1.777 -1.000 -0.500 </code></pre> However A* search has to work for all configurations including those after the start where the die is not in the original configuration, so the constant <code>k</code> can't be as low as <code>2.5</code> in general. It either needs to be raised, e.g. to <code>4</code>, or be dependent on the configuration of the die, as suggested in another answer. It's quite possible that I've made some horrible mistake in all of this so I've put the code below. Like I said, I think the approach of generating the data and investigating it is sound even if my results aren't. Here are some lines of the result file first. <blockquote> 17,-100,410 17,-99,406 17,-98,403 17,-97,399 17,-96,396 </blockquote> C# code <pre><code>class Die { int top; int bottom; int front; int back; int left; int right; public int Top { get { return top; } } public int Bottom { get { return bottom; } } public int Front { get { return front; } } public int Back { get { return back; } } public int Left { get { return left; } } public int Right { get { return right; } } public Die(int top, int bot, int fro, int bac, int lef, int rig) { this.top = top; bottom = bot; front = fro; back = bac; left = lef; right = rig; } public Die RotateLeft() { return new Die( top: right, rig: bottom, bot: left, lef: top, fro: front, bac: back ); } public Die RotateRight() { return new Die( rig: top, top: left, lef: bottom, bot: right, fro: front, bac: back ); } public Die RotateUp() { return new Die( top: front, fro: bottom, bot: back, bac: top, lef: left, rig: right ); } public Die RotateDown() { return new Die( fro: top, top: back, bac: bottom, bot: front, lef: left, rig: right ); } } class DieXY { public Die Die { get; set; } public int X { get; set; } public int Y { get; set; } public DieXY(Die die, int x, int y) { Die = die; X = x; Y = y; } public override int GetHashCode() { return Die.Top + Die.Bottom*6 + Die.Front*6^2 + Die.Back*6^3 + Die.Left*6^4 + Die.Right*6^5 + X*6^6 + Y*6^8; } public override bool Equals(object obj) { DieXY die = (DieXY)obj; return die != null && die.Die.Top == Die.Top && die.Die.Bottom == Die.Bottom && die.Die.Front == Die.Front && die.Die.Back == Die.Back && die.Die.Left == Die.Left && die.Die.Right == Die.Right && die.X == X && die.Y == Y; } } class Program { static void Main(string[] args) { Dictionary<DieXY, int> dict = new Dictionary<DieXY, int>(); int n = 100; int sofar = -1; DieXY root = new DieXY(new Die(1, 6, 2, 5, 4, 3), 0, 0); Queue<Tuple<DieXY, int>> queue = new Queue<Tuple<DieXY, int>>(); queue.Enqueue(new Tuple<DieXY,int>(root,0)); while (queue.Count > 0) { Tuple<DieXY, int> curr = queue.Dequeue(); DieXY dieXY = curr.Item1; Die die = dieXY.Die; int x = dieXY.X; int y = dieXY.Y; if (Math.Max(x,y) > sofar) { sofar = Math.Max(x, y); Console.WriteLine("{0}", sofar); } int score = curr.Item2; if (Math.Abs(x) <= n && Math.Abs(y) <= n) { int existingScore = 0; if (!dict.TryGetValue(dieXY, out existingScore) || score < existingScore) { dict[dieXY] = score; Die newDie = null; newDie = die.RotateLeft(); queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x - 1, y), score + newDie.Top)); newDie = die.RotateRight(); queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x + 1, y), score + newDie.Top)); newDie = die.RotateUp(); queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x, y + 1), score + newDie.Top)); newDie = die.RotateDown(); queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x, y - 1), score + newDie.Top)); } } } int[,] scores = new int[2*n+1,2*n+1]; for (int aX = 0; aX < 2 * n + 1; aX++) for (int aY = 0; aY < 2 * n + 1; aY++) scores[aX, aY] = int.MaxValue; foreach (KeyValuePair<DieXY, int> curr in dict) { int aX = curr.Key.X + n; int aY = curr.Key.Y + n; if (curr.Value < scores[aX, aY]) { scores[aX, aY] = curr.Value; } } using (System.IO.StreamWriter file = new System.IO.StreamWriter("out.csv")) { file.WriteLine("x,y,v"); for (int aX = 0; aX < 2*n+1; aX++) { int x = aX - n; for (int aY = 0; aY < 2 * n + 1; aY++) { int y = aY - n; file.WriteLine("{0},{1},{2}", x, y, scores[aX, aY]); } } } Console.WriteLine("Written file"); Console.ReadKey(); } } </code></pre> R code below <pre><code>library(lattice) df = read.csv("out.csv") df=transform(df, man=abs(x)+abs(y)) v50=df[abs(df$x)<=50 & abs(df$y)<=50,] with(v50, wireframe(v ~ x*y)) with(v50, contourplot(v ~ x*y)) summary(lm(df$v ~ df$man)) df$est = df$man * 3.5 - 2.5 summary(df$est - df$v) </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POA* Admissible Heuristic for die rolling on grid
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USTooTone
UserOwnerUserId
1. USTooTone
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.