What is the best admissible heuristic function for 2048 video game? Please give example of initial state and next state and how to compute the value of the evaluation function?
Asked
Active
Viewed 475 times
-7
-
It is hard to determine the best admissible heuristic, that could take some years of research and we would never know (probably) if there exists anything better. So, the only thing that comes to my mind right now is to use as heuristic 2048-current maximum as it estimates your cost to go somehow at it will never be lower than the real cost to go. – Javi Sep 28 '14 at 05:22
-
ok lets say from any given state I have 4 moves/options to play. How do I know which is better and would lead me towards goal? How do I estimates the cost? – jpp Sep 28 '14 at 05:25
-
For setting an heuristic first thing to do is to set your cost. What is our cost to come? – Javi Sep 28 '14 at 05:28
-
yes, but to get the max, first I have evaluate each child of current state. – jpp Sep 28 '14 at 05:28
-
Well, you are thinking on an heuristic in a wrong way probably. The heuristic tells you which node to "expand" in the next iteration, and that expand means to evaluate the 4 children. If you use the heuristic I proposed, it is likely that you have to expand less nodes. So you have to apply that heuristic to current node. – Javi Sep 28 '14 at 05:30
-
yes, but after expanding we need to compare each child with the parent based on our heuristic function right? which child gets us near to our goal? – jpp Sep 28 '14 at 05:33
-
I mean apply our heuristic function on each child and then take max of them. – jpp Sep 28 '14 at 05:35
-
Or the min! be careful, since you are doing 2048-current_max you want to minimize that value. If you take as heurisitic just current_max you have to maximize. – Javi Sep 28 '14 at 05:36
-
ohh now i got it..current_max means the maximum value tile in any particular state right? It could be possible that more than one child has the same current_max, in this case we need some other heuristic to differentiate between them. right? – jpp Sep 28 '14 at 05:39
-
Well, it is not a problem to have same values for the same heuristic, it does not have to be unique. I even would say that most of the heuristic have repeated values. Obviously it is not the best heuristic, but I cannot come up with anything else. Do you want me to include it as an answer? – Javi Sep 28 '14 at 05:52
-
yes please, If you have a better heuristic in mind. Thanks Javi V – jpp Sep 28 '14 at 05:53
-
Here are some ideas for heuristics: (I'm not sure how to compute them)http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048 – jpp Sep 28 '14 at 05:57
-
Wow I haven't seen that. It looks really cool. – Javi Sep 28 '14 at 06:01
-
but heuristics are explained in words, not sure how to compute it, give weight to each factors, etc.. – jpp Sep 28 '14 at 06:04
1 Answers
1
It is hard (if not impossible) to label an heuristic as "best".
One idea I have in mind is evaluate the heuristic for the current state as the maximum value of all the tiles at this state. And then, that with the higher value is supposed to be better ("closer") to the goal.
And it is admissible because it is never would be lower than the real value (that would mean that the current maximum is not the maximum, and that is not possible).
Probably, you can expand this heuristic with something as: given the current maximum position, is one of its (up to) 4 neighbours of the same value so they can sum up? But that requires a bit more of sophistication in order to keep it admissible.
Javi
- 3,440
- 5
- 29
- 43
-
+1 http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048 (can I use some of heuristics mentioned in here?) – jpp Sep 28 '14 at 06:02
-
-
You can get the code of those guys. For instance: https://github.com/limoragni/2048/blob/master/js/ai.js – Javi Sep 28 '14 at 06:09