Free Time Remaining For Today: 4:59
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский2048
Jumlah bilangan permainan: 859180
Jumlah kemenangan: 104188
Jumlah kemenangan: 104188
Permainan Anda Sebelum Ini
Introduction Description & How to Play2048 is a single-player game where one slides and merges tiles. The game is played on a rectangular board (4 x 4 by default), where some squares of the board have numbered tiles in them.
To play, swipe or use the arrow keys to slide all of the tiles in the corresponding direction.
Tiles will keep moving until they are stopped by either the edge of the board or another stopped tile.
If two tiles with the same number collide, then they will merge together into a single tile numbered with the sum of the two tiles that collided. This new tile will move in the same direction until stopped in the same way as other tiles.
After a move, a new tile will randomly appear. The new tile's number value has a 90% chance of being a 2, and a 10% chance of being a 4.
If you make a move that does not move or change any of the tiles on the board, then your move will not count (i.e. it will be treated as not making a move at all). If you cannot make a move, then the game ends.
To play, swipe or use the arrow keys to slide all of the tiles in the corresponding direction.
Tiles will keep moving until they are stopped by either the edge of the board or another stopped tile.
If two tiles with the same number collide, then they will merge together into a single tile numbered with the sum of the two tiles that collided. This new tile will move in the same direction until stopped in the same way as other tiles.
After a move, a new tile will randomly appear. The new tile's number value has a 90% chance of being a 2, and a 10% chance of being a 4.
If you make a move that does not move or change any of the tiles on the board, then your move will not count (i.e. it will be treated as not making a move at all). If you cannot make a move, then the game ends.
Additional Technical RulesIn the following, □ refers to an empty grid square.
If a tile is the result of a merge in a move, then it cannot be part of another merge in the same move (e.g. If there is a row with 2 2 4 8, then moving right will only result in □ 4 4 8).
If 3 consecutive equal tiles move together, then the 2 furthest along the direction of motion will merge (e.g. If there is a row with 2 2 2 □, then moving right will result in □ □ 2 4).
If 4 consecutive equal tiles move together, then the first 2 and the last 2 will merge (e.g.If there is a row with 2 2 2 2, then moving right will result in □ □ 4 4).
If a tile is the result of a merge in a move, then it cannot be part of another merge in the same move (e.g. If there is a row with 2 2 4 8, then moving right will only result in □ 4 4 8).
If 3 consecutive equal tiles move together, then the 2 furthest along the direction of motion will merge (e.g. If there is a row with 2 2 2 □, then moving right will result in □ □ 2 4).
If 4 consecutive equal tiles move together, then the first 2 and the last 2 will merge (e.g.If there is a row with 2 2 2 2, then moving right will result in □ □ 4 4).
Goal of the GameThe goal is to create a tile with the highest number value possible. The game is called 2048 because in the classical version of the game, you win when you have created a tile with the number 2048. In our version of the game, the score is the total of all tiles. On one hand, this sum is closely related to the top value. On the other hand, this better allows one to measure smaller progress.
2048, like all games on Caribou Contests, is sometimes featured on our math contests. We will announce beforehand when this happens. When 2048 is used as an interactive contest question,victory can be based either on your highest-value tile or on your total score.
2048, like all games on Caribou Contests, is sometimes featured on our math contests. We will announce beforehand when this happens. When 2048 is used as an interactive contest question,victory can be based either on your highest-value tile or on your total score.
Minimal Time to Reach a Large ScoreImagine you are playing 2048. Let's say you make one move every 2 seconds and manage to reach a high score (total sum) of, for example, 2048.
How long would that take?When making 10 moves then on average there will nine 2s and one 4 generated. They will increase the tile sum by 9×2+4 = 22. This will take on average 2048 points / (22 points / 10 moves) ≈ 930 moves, and 930 moves×2 sec/move = 1860 seconds = 31 minutes. In reality it will take much longer. Many attempts will be needed because of the game ending earlier.
Strategy Observations- A new tile appears every time a move is made.
- The only way to reduce the number of tiles on the board is to merge them.
- It takes more merges to create larger tile numbers than smaller tiles.
Where to Place Tiles?It is important to position your tiles correctly. For example, consider a row that looks like this: □ 2 8 2.
If you move left or right, no merges will take place on that row. This is because the 8 ‘blocks’ the 2s from merging together. If we had the 8 on the leftmost square or the rightmost square, such as □ 2 2 8, then merging would be easy. Therefore, we want big tiles to be on the edges. Small tiles are easy to merge, so their placement is not as important.
∴ Hence, the biggest tile should be on a corner,because the neighbourhood of very different tile numbers just costs space without a chance of a future merge.
But what about the second biggest? Consider another possible row: 128 2 2 128. Moving left or right would not combine the 128s. It would be difficult to create another 128 tile, and it would require multiple moves to merge the 128s.
We need to merge tiles in as few moves as possible. Every move, another tile appears. The more tiles there are, the worse the situation becomes, and the only way to reduce the number of tiles is to merge them.
∴Therefore the second biggest tile should be next to the biggest tile, because it makes merging big tiles easier.
∴Tiles should be moved so that the bigger they are, the closer they are to the corner with the biggest tile.
If you move left or right, no merges will take place on that row. This is because the 8 ‘blocks’ the 2s from merging together. If we had the 8 on the leftmost square or the rightmost square, such as □ 2 2 8, then merging would be easy. Therefore, we want big tiles to be on the edges. Small tiles are easy to merge, so their placement is not as important.
∴ Hence, the biggest tile should be on a corner,because the neighbourhood of very different tile numbers just costs space without a chance of a future merge.
But what about the second biggest? Consider another possible row: 128 2 2 128. Moving left or right would not combine the 128s. It would be difficult to create another 128 tile, and it would require multiple moves to merge the 128s.
We need to merge tiles in as few moves as possible. Every move, another tile appears. The more tiles there are, the worse the situation becomes, and the only way to reduce the number of tiles is to merge them.
∴Therefore the second biggest tile should be next to the biggest tile, because it makes merging big tiles easier.
∴Tiles should be moved so that the bigger they are, the closer they are to the corner with the biggest tile.
'Good' and 'Bad' Directions to Move InOne should try to keep the biggest tile in a corner. However, sliding tiles may move it out of the corner, and if a tile then randomly appears in the corner then you are in trouble.
Before we go on, we will choose the top-left corner for the sake of this discussion. You can choose whichever corner you prefer, and apply the same logic as we do.
If the biggest tile you have is in the top-left corner, then if you move up or left then you will always keep the biggest tile in the top-left corner. However, this works only for a few moves. You will quickly get into a situation where you cannot move up or left.
Then we will have to move in a third direction. Sometimes, it may be possible to slide the tiles such that the biggest tile does not leave the corner. For example, if we first ensure that the left column contains no empty □ nor equal-value tiles that will merge, then we can slide down without moving the biggest tile out of the corner. Similarly, we can slide right if we make sure the top row is filled without equal neighbours beforehand.
There is a cost to moving down or right. If you move down, then the tiles in the top row will move out. If you move right, then the tiles in the left column will move out. Unless, of course, they are blocked from moving as described above. Either way, you will have to spend moves remaking the top row or the left column. What one could do is to give a priority between moving down or right, for example, moving right only if no other move is possible.
∴ In general, you should move in the two directions that push the biggest tile against the corner it is in. Try to arrange tiles sorted by the size of their number. Have the left column filled so you have the option to move in a third direction without moving the corner tile. If you ever have to move in the fourth direction (in our example, to the right) then it pays off to have the top row filled to keep the maximal value in the corner.
Before we go on, we will choose the top-left corner for the sake of this discussion. You can choose whichever corner you prefer, and apply the same logic as we do.
If the biggest tile you have is in the top-left corner, then if you move up or left then you will always keep the biggest tile in the top-left corner. However, this works only for a few moves. You will quickly get into a situation where you cannot move up or left.
Then we will have to move in a third direction. Sometimes, it may be possible to slide the tiles such that the biggest tile does not leave the corner. For example, if we first ensure that the left column contains no empty □ nor equal-value tiles that will merge, then we can slide down without moving the biggest tile out of the corner. Similarly, we can slide right if we make sure the top row is filled without equal neighbours beforehand.
There is a cost to moving down or right. If you move down, then the tiles in the top row will move out. If you move right, then the tiles in the left column will move out. Unless, of course, they are blocked from moving as described above. Either way, you will have to spend moves remaking the top row or the left column. What one could do is to give a priority between moving down or right, for example, moving right only if no other move is possible.
∴ In general, you should move in the two directions that push the biggest tile against the corner it is in. Try to arrange tiles sorted by the size of their number. Have the left column filled so you have the option to move in a third direction without moving the corner tile. If you ever have to move in the fourth direction (in our example, to the right) then it pays off to have the top row filled to keep the maximal value in the corner.
Difficulty of the GameIt may surprise you that some random strategies are pretty effective. For example, if you repeat moving Left, Up, Right, Down, .. then you will tend to obtain a 256 before the game ends, and you will sometimes get a 512 before the game ends. On the other hand, repeating Left, Right as long as possible, then Up, Down as long as possible and so on will reach lower scores on average.
However, any such strategy will almost never get a 1024, and is nearly guaranteed to never get a 2048. It is still good to have a concrete game plan, even if luck is part of the game.
As you gain experience you will learn to think 2, 3 or even 4 moves ahead. For example, if the top two rows are
128 64 32 4
□ □ 2 32
then the plan could be to alternate Left + Right until there is a new number to the right of 32 in the 2nd row and then do Right + Up + Left + Left to merge the 32s, the 64s and 128s.
2048 starts off easy, but gets difficult very fast. Obtaining 512 is only a quarter of the way to the 2048 tile, and it only gets harder from there. Keep trying! You will find useful sequences of moves yourself.
However, any such strategy will almost never get a 1024, and is nearly guaranteed to never get a 2048. It is still good to have a concrete game plan, even if luck is part of the game.
As you gain experience you will learn to think 2, 3 or even 4 moves ahead. For example, if the top two rows are
128 64 32 4
□ □ 2 32
then the plan could be to alternate Left + Right until there is a new number to the right of 32 in the 2nd row and then do Right + Up + Left + Left to merge the 32s, the 64s and 128s.
2048 starts off easy, but gets difficult very fast. Obtaining 512 is only a quarter of the way to the 2048 tile, and it only gets harder from there. Keep trying! You will find useful sequences of moves yourself.
AlgorithmsThis section is for students who have a background in coding, or are interested in becoming code developers. It is technical and contains details on algorithms that are not taught in high school but should be understandable for anyone interested.
Given how mechanically simple 2048 is, it comes as no surprise that some developers have written their very own AI (Artificial Intelligence) to play the game.
In this section, we will talk about some programs and methods to implement your very own 2048 AI.
Given how mechanically simple 2048 is, it comes as no surprise that some developers have written their very own AI (Artificial Intelligence) to play the game.
In this section, we will talk about some programs and methods to implement your very own 2048 AI.
What are some simple strategies?In the ‘Difficulty of the Game’ section in 'Strategy' above, we outlined an algorithm that simply moves in the same sequence, 'left, right, up, down' over and over again.
How could you write this strategy in pseudocode?
Pseudocode implementation might look like this:
where the (m-1)th entry of the list of 4 directions is output and m cycles between 0 and 3. This poses an interesting question: are there other ‘simple’ algorithms that can achieve better results than this one?
You could try something like alternating Up and Down until neither move is possible, then Left and Right until neither move is possible, and so on. This tends to yield significantly worse scores. Try it out!
Attempting to ‘approximate’ the strategy section by repeating 'moving Left and Up until neither move is possible, then moving Right and Up' does not achieve results that are significantly different from our first strategy.
All of these simple strategies do not take the state of the board into account. To get better results, we need to build a more complicated program that does not aimlessly move independent of the board layout. Such a program would be qualified to be called an AI (Artificial Intelligence), defined as a device capable of perceiving an environment and taking actions to achieve a goal.
How could you write this strategy in pseudocode?
Pseudocode implementation might look like this:
m = 0
while game has not ended:
output [left,up,right,down][m]
m = (m + 1) modulo 4
while game has not ended:
output [left,up,right,down][m]
m = (m + 1) modulo 4
where the (m-1)th entry of the list of 4 directions is output and m cycles between 0 and 3. This poses an interesting question: are there other ‘simple’ algorithms that can achieve better results than this one?
You could try something like alternating Up and Down until neither move is possible, then Left and Right until neither move is possible, and so on. This tends to yield significantly worse scores. Try it out!
Attempting to ‘approximate’ the strategy section by repeating 'moving Left and Up until neither move is possible, then moving Right and Up' does not achieve results that are significantly different from our first strategy.
All of these simple strategies do not take the state of the board into account. To get better results, we need to build a more complicated program that does not aimlessly move independent of the board layout. Such a program would be qualified to be called an AI (Artificial Intelligence), defined as a device capable of perceiving an environment and taking actions to achieve a goal.
Layout of an AI What are some characteristics of 2048 shared by other board games?- The 2048 board is a discrete state space, meaning that there are a finite number of possible board layouts that are connected together through possible moves and random generations.
- Apart from the randomness, 2048 is a perfect information game, meaning nothing about what has happened or is happening is hidden from the player. To give some other examples, chess is a perfect information game (since both players can see all the pieces and all the moves that are played), but poker is not (since neither player can see the other’s cards). Note that a perfect information game does not include knowledge about what will happen. Such a game would be called a complete information game.
- 2048 is a turn-based game. The game is partitioned into moves, and the player has as much time as they want to analyze and make a move.
The characteristics of 2048 are shared by other popular games, like chess and Go, so we can take ideas from AIs for those games.
There are many ways to construct AIs for games like chess, ranging from neural networks to massive amounts of offline computation. Explaining them all would extend this Food for Thought discussion into a full novel.
The main difference between these games and 2048 is that 2048 has an element of randomness. In the game 2048, one player tries to play optimally against the computer which plays randomly. If both would try to play optimally then one could use a search technique called minimax search to determine the best next move.
There are many ways to construct AIs for games like chess, ranging from neural networks to massive amounts of offline computation. Explaining them all would extend this Food for Thought discussion into a full novel.
The main difference between these games and 2048 is that 2048 has an element of randomness. In the game 2048, one player tries to play optimally against the computer which plays randomly. If both would try to play optimally then one could use a search technique called minimax search to determine the best next move.
Standard Minimax SearchIn a minimax search, after each move a player makes, all possible opponent moves are investigated and so on, i.e. the full tree of possible move sequences is played through.
Such a tree explodes in size the deeper one searches. One therefore introduces a maximal search depth, i.e., each sequence is stopped at a maximal search depth, unless the sequence has already ended before that depth is reached.
If the game has ended, then the game result of this sequence is known, otherwise, if the sequence is stopped at the maximal research depth then the result has to be estimated. This estimate has some inevitable inaccuracy.
Based on these outcomes, each player determines the best move at successively earlier times. The best move is that which minimizes the optimum reachable by the opponent after that move. The word minimax stands for minimizing the maximum result which the opponent can reach after one's own move.
Let us assume that I am a player, and for a given board position one of my possible moves has been fully investigated: I therefore know how good a position the opponent can reach after that move. If it is clear without further searching that a potential move is bad, i.e., it would benefit my opponent more than the best moves I have investigated so far, then this move and the full tree of further moves from the resulting position can be ignored. Thus, there is no time or effort wasted investigating what is known to be a disadvantageous move and its offshoots. The saved time and effort can instead be applied to further investigating possible advantageous trees of moves.
This technique is called alpha-beta pruning. It leads to a thinner search tree which therefore can be searched deeper with the same effort so that inaccurate estimates at maximal search depth are avoided and are replaced by a more accurate result from searches.
To decide whether a move is probably good or bad without searching one uses estimates called heuristics. The more reliable the heuristics are, the more one can prune the search tree.
Such a tree explodes in size the deeper one searches. One therefore introduces a maximal search depth, i.e., each sequence is stopped at a maximal search depth, unless the sequence has already ended before that depth is reached.
If the game has ended, then the game result of this sequence is known, otherwise, if the sequence is stopped at the maximal research depth then the result has to be estimated. This estimate has some inevitable inaccuracy.
Based on these outcomes, each player determines the best move at successively earlier times. The best move is that which minimizes the optimum reachable by the opponent after that move. The word minimax stands for minimizing the maximum result which the opponent can reach after one's own move.
Let us assume that I am a player, and for a given board position one of my possible moves has been fully investigated: I therefore know how good a position the opponent can reach after that move. If it is clear without further searching that a potential move is bad, i.e., it would benefit my opponent more than the best moves I have investigated so far, then this move and the full tree of further moves from the resulting position can be ignored. Thus, there is no time or effort wasted investigating what is known to be a disadvantageous move and its offshoots. The saved time and effort can instead be applied to further investigating possible advantageous trees of moves.
This technique is called alpha-beta pruning. It leads to a thinner search tree which therefore can be searched deeper with the same effort so that inaccurate estimates at maximal search depth are avoided and are replaced by a more accurate result from searches.
To decide whether a move is probably good or bad without searching one uses estimates called heuristics. The more reliable the heuristics are, the more one can prune the search tree.
Minimax Search for 2048A standard minimax search assumes that both players play optimally. However, in 2048 one of the players, the computer, plays randomly.
The first version of a computer player to implement would just use heuristics to decide on a move without performing any search.
A second version may implement the standard minimax search and thus assume intelligent computer play (where the best computer move, for example, is probably to put a number in the corner immediately if the largest tile moves out of the corner).
Then one might experiment with a minimax search where the best player move minimizes not the maximum possible damage of the computer random placement but instead some kind of average damage of the subsequent computer random placement.
In any case, one would first start working on a heuristic for good player moves because that is beneficial for any computer player.
The first version of a computer player to implement would just use heuristics to decide on a move without performing any search.
A second version may implement the standard minimax search and thus assume intelligent computer play (where the best computer move, for example, is probably to put a number in the corner immediately if the largest tile moves out of the corner).
Then one might experiment with a minimax search where the best player move minimizes not the maximum possible damage of the computer random placement but instead some kind of average damage of the subsequent computer random placement.
In any case, one would first start working on a heuristic for good player moves because that is beneficial for any computer player.
Such searches are made more efficient by Heuristics, which we discuss in the next section.
HeuristicsWhat is a heuristic?
A heuristic is an unproven educated guess for what to do next, like a 'rule of thumb'. For example, the ‘scarcity heuristic’, the tendency for people to assign high values to rare items, is a heuristic. It is a method that attempts to guess the price of an item. It is not perfect (e.g. many things are rare without being valuable: your DNA may be one-of-a-kind but it is unlikely that many people want to buy it), but it is a good enough estimator for many objects.
Heuristics appear in coding all the time. For this case, we will use heuristics to approximate how ‘good’ a board layout is.
Assign a value to a board layout signifying how ‘good’ it is; a higher number means a ‘better’ layout and a lower number means a ‘worse’ layout. We have no way of calculating exactly how ‘good’ a board layout is, but we can use a number of heuristics to help decide on our next move. Try to think of some possible heuristics to decide whether a board layout is 'good' before continuing.
A heuristic is an unproven educated guess for what to do next, like a 'rule of thumb'. For example, the ‘scarcity heuristic’, the tendency for people to assign high values to rare items, is a heuristic. It is a method that attempts to guess the price of an item. It is not perfect (e.g. many things are rare without being valuable: your DNA may be one-of-a-kind but it is unlikely that many people want to buy it), but it is a good enough estimator for many objects.
Heuristics appear in coding all the time. For this case, we will use heuristics to approximate how ‘good’ a board layout is.
Assign a value to a board layout signifying how ‘good’ it is; a higher number means a ‘better’ layout and a lower number means a ‘worse’ layout. We have no way of calculating exactly how ‘good’ a board layout is, but we can use a number of heuristics to help decide on our next move. Try to think of some possible heuristics to decide whether a board layout is 'good' before continuing.
Examples of Heuristics For 2048 Free TilesIf there are few free tiles □ on the board, then your options become very limited. Therefore, a higher value can be given to boards with more spots open.
An improved version would also estimate the chance for occupied tiles to merge with a neighbouring tile of half the value depending on the probability that this neighbour can be merged and so on. Such an estimate would start with tiles of value 2 or 4 located next to free tiles.
An improved version would also estimate the chance for occupied tiles to merge with a neighbouring tile of half the value depending on the probability that this neighbour can be merged and so on. Such an estimate would start with tiles of value 2 or 4 located next to free tiles.
Potential MergesIf there are a lot of adjacent equal tiles, then a large number of merges can take place, leading to a large number of free tiles and thus more options. Therefore, a higher value can be given to boards with many potential merges. Do also consider that if you move in one direction, then the potential merges in the perpendicular direction will most likely disappear, so an effort should be made to account for that possibility.
AdversarialThis heuristic treats the random generation like a hostile second player. That is, it will assume the random generation will always lead to the worst possible outcome, and so higher values can be given to the boards that minimize the risk of bad outcomes.
MonotonicityA monotone sequence is a sequence of numbers where either each number is greater than or equal to all previous numbers (monotone increasing) or each number is smaller than or equal to all previous numbers (monotone decreasing). For example, 1,1,1,2,3 and 3,2,1,1,1 are monotone increasing and monotone decreasing respectively but 1,1,1,2,1 is not monotone. We can assign higher values for board layouts that are monotone increasing or close to monotone increasing towards a corner, i.e. a tile closer to that corner is greater than or equal to all tiles farther away from that corner. This is an emulation of the strategy discussed in the previous section, where the focus was to keep the biggest tile in a corner and all other big tiles clustered around that corner.
SmoothingAny 2 neighbouring tiles that are not equal in value pose a cost because they take space which is needed for moving tiles around and merging them.
This cost is higher if the tiles are very different with little chance of being merged in future. The following simple heuristic easily sums up all these 'costs' or negative heuristics.
On an M×N board (with M rows and N columns), there are N−1 neighbourhood relations in each row and M−1 such relations in each column, so in total (M × (N−1)) + (N × (M−1)) = 2MN − M − N separators between neighbouring tiles. We attach a negative heuristic (i.e. a cost) to each one of them which is a measure of the number of merges needed for the smaller of both numbers to become equal to the bigger one. In other words, we count the number of factors of 2 separating both. Equivalently, but in more formal terms, if we let A equal the smaller tile's value, and B equal the larger tile's value, we take log2 (A/B) as a cost, i.e. this would be a negative score.
This cost is higher if the tiles are very different with little chance of being merged in future. The following simple heuristic easily sums up all these 'costs' or negative heuristics.
On an M×N board (with M rows and N columns), there are N−1 neighbourhood relations in each row and M−1 such relations in each column, so in total (M × (N−1)) + (N × (M−1)) = 2MN − M − N separators between neighbouring tiles. We attach a negative heuristic (i.e. a cost) to each one of them which is a measure of the number of merges needed for the smaller of both numbers to become equal to the bigger one. In other words, we count the number of factors of 2 separating both. Equivalently, but in more formal terms, if we let A equal the smaller tile's value, and B equal the larger tile's value, we take log2 (A/B) as a cost, i.e. this would be a negative score.
These are not the only heuristics that are available, but are nevertheless good food for thought.
If heuristics are more reliable then they can be used to be more selective in which moves are to be investigated further. For some games, the heuristics change from the start of the game to the middle game and end game. If heuristics are very unreliable then one might simulate many games from a position to the end and use statistics for judging which moves seem to be better and in turn investigate them more. But such strategies are more suitable for games with larger boards, not for 2048.
If you are interested in writing your own 2048 AI, you may access our interactive problem at cariboutests.com/judge.
Mathematical Properties & ProofsThis section is for students who are interested in new mathematics. We introduce concepts found in undergraduate university mathematics courses. This section is for high school students or interested middle school students.
While 2048 is a fun arcade game, there are also some details about it that can be shown to be true through mathematical methods. To do that, however, we will need some tools, the most notable of which is called invariant.
While 2048 is a fun arcade game, there are also some details about it that can be shown to be true through mathematical methods. To do that, however, we will need some tools, the most notable of which is called invariant.
InvariantsAn invariant is a property of an object that does not change when certain operations are performed with that object.
ExampleAn even number leaves no remainder when being divided by 2 (such as ..−2,0,2,4,6,..) and an odd number leaves the remainder 1 when being divided by 2 (such as ..−1,1,3,5,..). Adding or subtracting 2 to an even number gives an even number and adding or subtracting 2 to an odd number gives an odd number. Therefore the operation of adding or subtracting 2 does not change the property of being an even or an odd number.
The property of a number to be even or odd is also called its Parity. We can therefore say, the parity of a number is an invariant under adding/subtracting 2. Adding or subtracting 2 multiple times does still not change the parity. Therefore:
∴ The parity of a number is an invariant under addition and subtraction of any even number.
The property of a number to be even or odd is also called its Parity. We can therefore say, the parity of a number is an invariant under adding/subtracting 2. Adding or subtracting 2 multiple times does still not change the parity. Therefore:
∴ The parity of a number is an invariant under addition and subtraction of any even number.
An invariant (such as Parity) of a certain operation (such as adding/subtracting an even number) is useful to prove that an object (such as a number) with one invariant value (such as being even) cannot be transformed into another object (such as another number) with a different invariant value (such as being odd) under such a type of operation (in this case, addition/subtraction of an even number).
Invariants can have innumerable forms in mathematics. Some of the most notable ones are knot invariants. Before knot invariants were discovered in the 1920s, mathematicians could not prove that any two knots were different from each other (i.e. cannot be deformed into each other), or were different even from a simple loop!
If you're curious about knots and their properties, our Unknotting game is a good place to start.
Invariants can have innumerable forms in mathematics. Some of the most notable ones are knot invariants. Before knot invariants were discovered in the 1920s, mathematicians could not prove that any two knots were different from each other (i.e. cannot be deformed into each other), or were different even from a simple loop!
If you're curious about knots and their properties, our Unknotting game is a good place to start.
Under the operation of making moves in the 2048 game, the following are invariants:
Lemma 1: A tile's number will always be a power of 2.- If two tiles with equal powers of 2 merge, then the result will be the next power of 2.
- All generated tiles start with either 2 or 4, which are powers of 2.
- Therefore, by the principle of mathematical induction, all tiles’ numbers are powers of 2.
Lemma 2: In a move, the sum of all tile numbers changes only through the random generation of the new tile.- If none of the tiles merge, then the sum is preserved.
- If any two tiles merge, then the sum is still preserved as the resulting tile has the same sum as the initial two tiles (like evaluating the addition of some numbers).
- Therefore, as the sum of the initial tiles is always preserved, the total sum is changed only by the generation of a new tile which has a random value.
With these properties, we can now prove some interesting results about 2048.
More Lemma- Lemma: Let N be the nth even number, i.e. N = 2 n and let the board size be large enough so that the game has at least n moves. Then the probability that the total sum of numbers on tiles will at any point in the game be exactly equal to N is equal to (10 + (−1⁄10)n)/(11).
Proof- Since the sum of all tile numbers does not change in a merge, the only way for the sum to increase is by the random tile generation. Therefore, after any turn, the sum increases by 2 with a 90% chance or by 4 with a 10% chance.
- Let P(n) be the probability that at some point in the game the total sum is exactly N = 2n and Q(n) = 1 − P(n) be the probability that the sum will never be equal N.
- At the start of the game the sum is zero with a probability of 100%, i.e. P(0) = 1 and Q(0) = 0.
- The only possibility that an even number N cannot be the sum of all tiles is that N−2 occured as a sum (with probability 1−Q(n−1) ) AND a 4 is generated (with probability 1⁄10). The probability is therefore Q(n) = (1−Q(n−1))/(10) which is the linear recurrence relation 10Q(n) + Q(n−1) = 1.
- The general solution of this inhomogeneous linear recurrence relation (with a 1 on the right-hand side) is equal the general solution of the homogeneous version (with a 0 on the right-hand side) plus a particular solution of the inhomogeneous version.
- The general solution of the homogeneous version 10Q(n) + Q(n−1) = 0 is Q(n) = a(−1⁄10)n with a being an arbitrary number.
- A particular solution of the inhomogeneous version is Q(n) = 1/11 for all n because 10(1/11) + 1/11 = 1.
- The constant a is determined from the case n=0: 0 = Q(0) = a(−1⁄10)0 + 1/11 = a + 1/11 and therefore a = −1/11,
- Substituting a into the formula for Q gives Q(n) = 1/11 − 1/11(−1⁄1⁄1⁄10)n and therefore
- P(n) = 1 − Q(n) = ( 10 + (−1⁄10)n )/(11). ■
- Lemma: It is impossible to achieve a tile of 262144 = 218.
Proof- We start the proof by assuming the opposite: that some board configuration managed to get to a tile of 262144 = 218.
- Then one move before, the sum must have been either 218 − 4 or 218 − 2.
- But 218 − 4 takes a minimum of 16 tiles to represent (16 is the number of 1s in the binary representation of 218 − 4 = 217+216+..+23+22, and comes about as a result of the numbers of tiles being powers of 2. Having, for example, two tiles with a 16 instead of one tile with a 32 would increase the number of tiles even further).
- 218 − 2 would take a minimum of 17 tiles to represent.
- Therefore, it is impossible to go past 218 − 4 and thus impossible to reach 218 = 262144. ■
- Lemma:To reach a tile sum of 131072 = 217, apart from incredible luck to be able to merge sufficiently many tiles, there is a final luck of approximately 1 in 11 necessary.
Proof- As shown before, the tile sum always increases by 2 or 4 in each move due to the random tile generation.
- Therefore, one move before the tile sum reaches 217 it must have been 217− 2 or 217− 4.
- Following the argument in the previous proof, the minimal number of tiles to represent 217− 2 is 16
- The maximal number of tiles on the board is 16, so if 217 − 2 is reached then it is sure to be impossible to continue since there will be no room for a new tile to appear and no merges would be possible owing to the uniqueness of all tiles on the board.
- Therefore, the only way for a tile sum of 217 to be reached is to achieve 217− 4 (which takes 15 tiles at minimum, leaving room for another tile to appear), and then generate a 4.
- The probability of reaching any given even tile sum approaches 10⁄11 and a 4 is generated with probability 1⁄10 giving a product of 1⁄11 as the chance of skipping 217− 2 and finally reaching a tile sum of 131072 = 217. ■
Ikuti atau langgan untuk kemas kini: