You are right, the first cost function doesn't make a lot of sense, but I didn't divide by the number of leafs - so it basically also was based on the number of unassigned tiles.
So in the end you are right these approaches are more or less the same.
That does not depend much on the solution, mostly it depends at the speed at which numbers are generated (which you can approximate constant to 20.8 + 40.2).
Interesting work. I'd be curious to see this algorithm applied to the original game. Since this is a re-implementation of the game in Java, it may be solving a completely different game.
I could be wrong here, but from my reading of the source this doesn't look like an A* search algorithm. For starters, the search space is nondeterministic, and since you can only explore in one direction, you're not really performing a search space exploration as much as choosing a direction and going with it.
Secondly, the implementation doesn't perform the combination of current state score and proposed state score that lies at the heart of the A* algorithm. Instead it takes the current state for granted (which, again, it must given the inability to backtrack) and chooses the available move with the largest score.
Thirdly, and I'm reaching a little here, I can't find any place where any heuristic is used to optimize search performance by pruning the search tree. The search space is brute forced on each iteration, and the entire tree is scored.
At the expense of seeming pedantic I suggest this is a greedy play algorithm rather than A*. You can be even more precise and call it a single-ply minimax.
Now that that's out of the way, I should temper my criticism with the fact that this implementation works. It's not algorithmically complicated because it doesn't have to be. It doesn't use any of the typical performance tricks because it doesn't need to. What it lacks in sophistication it makes up in "good enough."
Thanks for sharing this. I may have missed this answer between all of the threads related to 2048, but has anyone found if there is a limit for the 4x4 tile size?
The highest tile you can get is 2^17, 131072. Each doubling of the tile size requires another extra space, as you have to construct two of the previous tile, and once you construct one, it has to go somewhere. In the end, the final board will have a string of every power of two from 2^16 to 4, and then another 4 in the last empty space. The 4s then combine, then the 8s, and so on, rippling up like binary addition until you get 2^17. Hope that makes sense, I thought about this for a while but it's not the easiest concept to put to words.
Hello everyone, I am currently taking a course in Artificial Intelligence and have been planning to implement the A* algorithm towards 2048. But seeing here that people believe that this isnt a "true" A* implementation, would the hackerNews community be interested in an actual working Javascript implementation of multiple AI methods? (i.e. having a dropdown selector for the method to use and implementation via a button)
This would be cool. Please don't just post the code though... Have a working, interactive 2048 game that runs your algorithm so I can watch it without doing anything. Not everyone here is a coding guy...
I'm not really an AI person, but I think it's interesting, yes:
Each individual decision is simple (choose from 4 directions), but the overall strategy is difficult (the arrival of each new piece has a random element).
The game tree[0] is awkward to draw in full, because of this random element. If we can draw it out well enough to analyse it, we can come up with a perfect play algorithm that wins as often as possible. Tic-tac-toe is 'solved' in this sense: we always know what the best play is.
Since 2048 remains unsolved (for now), AI algorithms which simplify and try to approximate that process come into play. As long as nobody has come up with perfect play, it's still interesting to see who can come up with the best play.
2048 is relatively simple game to remain unsolved, so it's nice and accessible to apply algorithms to (and still relevant to do so).
I'd rather not say how many hours I sank into 2048 before I could beat it. But, it's interesting to recall the little rules, preferences and maybe even aesthetics that I picked up along the way and the order they came in. HN was all 2048 AI that day so I was noticing how I was learning the game.
An early strategic step was deciding to play in only 3 directions, with one direction as the least favorite, potentially dangerous direction. If my high square is on the bottom right with the second highest to its left then up is not allowed and left is dangerous because it could put a 2 in the high square's place.
If I hadn't been "recording" the process at the time I would have missed what sent me down the '3 directions' path. I started by deciding to have the high square in the corner. Then I decided I wanted to lock the whole row as a way of keeping it there.
Another more subtle reason reason was that this simplified the rules of the game and let me learn a few other strategies. Moving in all directions was too complicated.
An early strategy that i tried and abandoned was trying to getting high squares to one another. Instead I concentrated my attention on the squares in the locked row that stay in place fore a while and started worrying about doubling only those.
This was another way of simplifying the game. It meant that my attention could be focused on certain spaces, not on everything. For example, I want to double square D2. Line D is locked I need to get D2's value to C2. It's easiest to do this if outside of line D all values are lower than D2.
Interesting stuff. makes me want to learn a new games just to watch me learn it.
So the question: How doable is it to watch humans develop learn and represent them?
And a second one: is there a '_why's shoes' equivalent for AI?
Essentially it communicates via an API to a webserver where you write your "brain" logic and respond to the API requests with which move to choose next:
Since it's over web, you can write your webserver in the language of your choosing. I wrote a small dumb Python webserver using the Flask microframework:
This can be adapted obviously for whatever logic you choose. The reason I forked this version and not a totally server-side one (which would be better for performance obviously) is that you can actually watch the moves this one makes as it chooses them, which makes it kinda fun.
Given the number of straight 2048 implementations out there now that appear to have slightly different rules making the game easier, perhaps it would be a great idea for the definitive 2048 rules to be published.
Let me start by saying that I'm glad you ported this game to Java, it certainly increases the reach of the game and the number of people who can hack on it. You're also a really organized Java programmer, which makes it a lot easier for other people to build on what you made.
With that said, this Java implementation needs a lot of performance improvement. I made some trivial changes on it and benchmarked it at a significant speed boost, I'll send you my revisions on GitHub so you can take a look. Also, as another commenter mentioned, this isn't true A*, but good work nonetheless.
Here's a simple performance improvement: Java's ArrayList is just a wrapped array with two fields:
private transient Object[] elementData;
private int size;
When you initialize it, it initializes elementData to a null array of size of 10. When you put the 11th thing into the list, it creates a new array of size 15 (in general, a 50% increase), and copies references from the old array. This means that in your search, a board with 11 or more open tiles will trigger a resize. This is easily prevented by initializing the list with
new ArrayList <Tile> (15)
Bam! One optional parameter, 9% runtime improvement. As the performance gets optimized you can search larger trees in less time.
40 comments
[ 3.6 ms ] story [ 32.5 ms ] threadQuestion that I didn't understand the answer to:
> There are implemented 3 cost functions:
> 1. sum of all tiles in the playing field
is this a useful cost function at all? Surely the sum of the tiles is not affected by strategy played, only by whether a 2 or 4 was randomly received.
> 2. number of all unassigned tiles in the playing field
> 3. average value of an occupied tile
Then, for similar reason, I would be surprised if these were not equivalent.
So in the end you are right these approaches are more or less the same.
So I think it can win all games?
Secondly, the implementation doesn't perform the combination of current state score and proposed state score that lies at the heart of the A* algorithm. Instead it takes the current state for granted (which, again, it must given the inability to backtrack) and chooses the available move with the largest score.
Thirdly, and I'm reaching a little here, I can't find any place where any heuristic is used to optimize search performance by pruning the search tree. The search space is brute forced on each iteration, and the entire tree is scored.
At the expense of seeming pedantic I suggest this is a greedy play algorithm rather than A*. You can be even more precise and call it a single-ply minimax.
Now that that's out of the way, I should temper my criticism with the fact that this implementation works. It's not algorithmically complicated because it doesn't have to be. It doesn't use any of the typical performance tricks because it doesn't need to. What it lacks in sophistication it makes up in "good enough."
Only reach 8192, but with the game implemented in the right way :)
2, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768
You could theoretically beat that if you happened to get a 4 just when you needed it (starting with 4, 4, 8, 16, etc.)
Each individual decision is simple (choose from 4 directions), but the overall strategy is difficult (the arrival of each new piece has a random element).
The game tree[0] is awkward to draw in full, because of this random element. If we can draw it out well enough to analyse it, we can come up with a perfect play algorithm that wins as often as possible. Tic-tac-toe is 'solved' in this sense: we always know what the best play is.
Since 2048 remains unsolved (for now), AI algorithms which simplify and try to approximate that process come into play. As long as nobody has come up with perfect play, it's still interesting to see who can come up with the best play.
2048 is relatively simple game to remain unsolved, so it's nice and accessible to apply algorithms to (and still relevant to do so).
[0]https://en.wikipedia.org/wiki/Game_tree
I'd rather not say how many hours I sank into 2048 before I could beat it. But, it's interesting to recall the little rules, preferences and maybe even aesthetics that I picked up along the way and the order they came in. HN was all 2048 AI that day so I was noticing how I was learning the game.
An early strategic step was deciding to play in only 3 directions, with one direction as the least favorite, potentially dangerous direction. If my high square is on the bottom right with the second highest to its left then up is not allowed and left is dangerous because it could put a 2 in the high square's place.
If I hadn't been "recording" the process at the time I would have missed what sent me down the '3 directions' path. I started by deciding to have the high square in the corner. Then I decided I wanted to lock the whole row as a way of keeping it there.
Another more subtle reason reason was that this simplified the rules of the game and let me learn a few other strategies. Moving in all directions was too complicated.
An early strategy that i tried and abandoned was trying to getting high squares to one another. Instead I concentrated my attention on the squares in the locked row that stay in place fore a while and started worrying about doubling only those.
This was another way of simplifying the game. It meant that my attention could be focused on certain spaces, not on everything. For example, I want to double square D2. Line D is locked I need to get D2's value to C2. It's easiest to do this if outside of line D all values are lower than D2.
Interesting stuff. makes me want to learn a new games just to watch me learn it.
So the question: How doable is it to watch humans develop learn and represent them?
And a second one: is there a '_why's shoes' equivalent for AI?
http://pastebin.com/VwwGCYYy
https://github.com/loisaidasam/2048
Essentially it communicates via an API to a webserver where you write your "brain" logic and respond to the API requests with which move to choose next:
https://github.com/loisaidasam/2048/blob/master/js/autonomou...
Since it's over web, you can write your webserver in the language of your choosing. I wrote a small dumb Python webserver using the Flask microframework:
https://github.com/loisaidasam/2048/blob/master/py/webserver...
And it simply returns a random direction:
https://github.com/loisaidasam/2048/blob/master/py/game.py
This can be adapted obviously for whatever logic you choose. The reason I forked this version and not a totally server-side one (which would be better for performance obviously) is that you can actually watch the moves this one makes as it chooses them, which makes it kinda fun.
Enjoy!
With that said, this Java implementation needs a lot of performance improvement. I made some trivial changes on it and benchmarked it at a significant speed boost, I'll send you my revisions on GitHub so you can take a look. Also, as another commenter mentioned, this isn't true A*, but good work nonetheless.
Here's a simple performance improvement: Java's ArrayList is just a wrapped array with two fields:
When you initialize it, it initializes elementData to a null array of size of 10. When you put the 11th thing into the list, it creates a new array of size 15 (in general, a 50% increase), and copies references from the old array. This means that in your search, a board with 11 or more open tiles will trigger a resize. This is easily prevented by initializing the list with Bam! One optional parameter, 9% runtime improvement. As the performance gets optimized you can search larger trees in less time.