Connect with us

# Using Artificial Intelligence to solve the 2048 Game (JAVA code)

Published

on

By now most of you have heard/played the 2048 game by Gabriele Cirulli. It’s a simple but highly addictive board game which requires you to combine the numbers of the cells in order to reach the number 2048. As expected the difficulty of the game increases as more cells are filled with high values. Personally even though I spent a fair amount of time playing the game, I was never able to reach 2048. So the natural thing to do is to try to develop an AI solver in JAVA to beat the 2048 game. 🙂

In this article I will briefly discuss my approach for building the Artificial Intelligence Solver of Game 2048, I will describe the heuristics that I used and I will provide the complete code which is written in JAVA. The code is open-sourced under GPL v3 license and you can download it from Github.

## Developing the 2048 Game in JAVA

The original game is written in JavaScript, so I had to rewrite it in JAVA from scratch. The main idea of the game is that you have a 4×4 grid with Integer values, all of which are powers of 2. Zero valued cells are considered empty. At every point during the game you are able to move the values towards 4 directions Up, Down, Right or Left. When you perform a move all the values of the grid move towards that direction and they stop either when they reach the borders of the grid or when they reach another cell with non-zero value.  If that previous cell has the same value, the two cells are merged into one cell with double value. At the end of every move a random value is added in the board in one of the empty cells and its value is either 2 with 0.9 probability or 4 with 0.1 probability. The game ends when the player manages to create a cell with value 2048 (win) or when there are no other moves to make (lose).

In the original implementation of the game, the move-merge algorithm is a bit complicated because it takes into account all the directions. A nice simplification of the algorithm can be performed if we fix the direction towards which we can combine the pieces and rotate the board accordingly to perform the move. Maurits van der Schee has recently written an article about it which I believe is worth checking out.

All the classes are documented with Javadoc comments. Below we provide a high level description of the architecture of the implementation:

### 1. Board Class

The board class contains the main code of the game, which is responsible for moving the pieces, calculating the score, validating if the game is terminated etc.

### 2. ActionStatus and Direction Enum

The ActionStatus and the Direction are 2 essential enums which store the outcome of a move and its direction accordingly.

### 3. ConsoleGame Class

The ConsoleGame is the main class which allows us to play the game and test the accuracy of the AI Solver.

### 4. AIsolver Class

The AIsolver is the primary class of the Artificial Intelligence module which is responsible for evaluating the next best move given a particular Board.

## Artificial Intelligence Techniques: Minimax vs Alpha-beta pruning

Several approaches have been published to solve automatically this game. The most notable is the one developed by Matt Overlan. To solve the problem I tried two different approaches, using Minimax algorithm and using Alpha-beta pruning.

### Minimax Algorithm

The Minimax is a recursive algorithm which can be used for solving two-player zero-sum games. In each state of the game we associate a value. The Minimax algorithm searches through the space of possible game states creating a tree which is expanded until it reaches a particular predefined depth. Once those leaf states are reached, their values are used to estimate the ones of the intermediate nodes.

The interesting idea of this algorithm is that each level represents the turn of one of the two players. In order to win each player must select the move that minimizes the opponent’s maximum payoff. Here is a nice video presentation of the minimax algorithm:

Below you can see pseudocode of the Minimax Algorithm:

```function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE))
bestValue := max(bestValue, val);
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE))
bestValue := min(bestValue, val);
return bestValue
(* Initial call for maximizing player *)
minimax(origin, depth, TRUE)```

### Alpha-beta pruning

The Alpha-beta pruning algorithm is an expansion of minimax, which heavily decreases (prunes) the number of nodes that we must evaluate/expand. To achieve this, the algorithm estimates two values the alpha and the beta. If in a given node the beta is less than alpha then the rest of the subtrees can be pruned. Here is a nice video presentation of the alphabeta algorithm:

Below you can see the pseudocode of the Alpha-beta pruning Algorithm:

```function alphabeta(node, depth, α, β, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
for each child of node
α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
if β ≤ α
break (* β cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
if β ≤ α
break (* α cut-off *)
return β
(* Initial call *)
alphabeta(origin, depth, -∞, +∞, TRUE)```

## How AI is used to solve the Game 2048?

In order to use the above algorithms we must first identify the two players. The first player is the person who plays the game. The second player is the computer which randomly inserts values in the cells of the board. Obviously the first player tries to maximize his/her score and achieve the 2048 merge. On the other hand the computer in the original game is not specifically programmed to block the user by selecting the worst possible move for him but rather randomly inserts values on the empty cells.

So why we use AI techniques which solve zero-sum games and which specifically assume that both players select the best possible move for them? The answer is simple; despite the fact that it is only the first player who tries to maximize his/her score, the choices of the computer can block the progress and stop the user from completing the game. By modeling the behavior of the computer as an orthological non-random player we ensure that our choice will be a solid one independently from what the computer plays.

The second important part is to assign values to the states of the game. This problem is relatively simple because the game itself gives us a score. Unfortunately trying to maximize the score on its own is not a good approach. One reason for this is that the position of the values and the number of empty valued cells are very important to win the game. For example if we scatter the large values in remote cells, it would be really difficult for us to combine them. Additionally if we have no empty cells available, we risk losing the game at any minute.

For all the above reasons, several heuristics have been suggested such as the Monoticity, the smoothness and the Free Tiles of the board. The main idea is not to use the score alone to evaluate each game-state but instead construct a heuristic composite score that includes the aforementioned scores.

Finally we should note that even though I have developed an implementation of Minimax algorithm, the large number of possible states makes the algorithm very slow and thus pruning is necessary. As a result in the JAVA implementation I use the expansion of Alpha-beta pruning algorithm. Additionally unlike other implementations, I don’t prune aggressively the choices of the computer using arbitrary rules but instead I take all of them into account in order to find the best possible move of the player.

## Developing a heuristic score function

In order to beat the game, I tried several different heuristic functions. The one that I found most useful is the following:

```private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) { int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore); return Math.max(score, Math.min(actualScore, 1));
}
```

The above function combines the actual score of the board, the number of empty cells/tiles and a metric called clustering score which we will discuss later. Let’s see each component in more detail:

1. Actual Score: For obvious reasons, when we calculate the value of a board we have to take into account its score. Boards with higher scores are generally preferred in comparison to boards with lower scores.
2. Number of Empty Cells: As we mentioned earlier, keeping few empty cells is important to ensure that we will not lose the game in the next moves. Board states with more empty cells are generally preferred in comparison to others with fewer. A question rises concerning how would we value those empty cells? In my solution I weight them by the logarithm of the actual score. This has the following effect: The lower the score, the less important it is to have many empty cells (This is because at the beginning of the game combining the cells is fairly easy). The higher the score, the more important it is to ensure that we have empty cells in our game (This is because at the end of the game it is more probable to lose due to the lack of empty cells.
3. Clustering Score: We use the clustering score which measures how scattered the values of our board are. When cells with similar values are close they are easier to combine meaning it is harder to lose the game. In this case the clustering score has a low value. If the values of the board are scattered, then this score gets a very large value. This score is subtracted from the previous two scores and acts like a penalty that ensures that clustered boards will be preferred.

In the last line of the function we ensure that the score is non-negative. The score should be strictly positive if the score of the board is positive and zero only when the board of the score is zero. The max and min functions are constructed so that we get this effect.

Finally we should note that when the player reaches a terminal game state and no more moves are allowed, we don’t use the above score to estimate the value of the state. If the game is won we assign the highest possible integer value, while if the game is lost we assign the lowest non negative value (0 or 1 with similar logic as in the previous paragraph).

## More about the Clustering Score

As we said earlier the clustering score measures how much scattered are the values of the board and acts like a penalty. I constructed this score in such a way so that it incorporates tips/rules from users who “mastered” the game. The first suggested rule is that you try to keep the cells with similar values close in order to combine them easier. The second rule is that high valued cells should be close to each other and not appear in the middle of the board but rather on the sides or corners.

Let’s see how the clustering score is estimated. For every cell of the board we estimate the sum of absolute differences from its neighbors (excluding the empty cells) and we take the average difference. The reason why we take the averages is to avoid counting more than once the effect of two neighbor cells. The total clustering score is the sum of all those averages.

The Clustering Score has the following attributes:

1. It gets high value when the values of the board are scattered and low value when cells with similar values are close to each other.
2. It does not overweigh the effect of two neighbor cells.
3. Cells in the margins or corners have fewer neighbors and thus lower scores. As a result when the high values are placed near the margins or corners they have smaller scores and thus the penalty is smaller.

## The accuracy of the algorithm

As expected the accuracy (aka the percentage of games that are won) of the algorithm heavily depends on the search depth that we use. The higher the depth of the search, the higher the accuracy and the more time it requires to run. In my tests, a search with depth 3 lasts less than 0.05 seconds but gives 20% chance of winning, a depth of 5 lasts about a 1 second but gives 40% chance of winning and finally a depth of 7 lasts 27-28 seconds and gives about 70-80% chance of winning.

## Future expansions

For those of you who are interested in improving the code here are few things that you can look into:

1. Improve the Speed: Improving the speed of the algorithm will allow you to use larger depth and thus get better accuracy.
2. Create Graphics: There is a good reason why Gabriele Cirulli’s implementation became so famous. It is nice looking! I did not bother developing a GUI but I rather print the results on console which makes the game harder to follow and to play. Creating a nice GUI is a must.
3. Tune Heuristics: As I mentioned earlier, several users have suggested different heuristics. One can experiment with the way that the scores are calculated, the weights and the board characteristics that are taken into account. My approach of measuring the cluster score is supposed to combine other suggestions such as Monotonicity and Smoothness, but there is still room for improvement.
4. Tuning the Depth: One can also try to tune/adjust the depth of the search depending on the game state. Also you can use the Iterative deepening depth-first search algorithm which is known to improve the alpha-beta pruning algorithm.

Don’t forget to download the JAVA code from Github and experiment. I hope you enjoyed this post! If you did please take a moment to share the article on Facebook and Twitter. 🙂

My name is Vasilis Vryniotis. I’m a Data Scientist, a Software Engineer, author of Datumbox Machine Learning Framework and a proud geek. Learn more

Published

on

# Cartoon: Cloud Dating

New KDnuggets cartoon looks at how AI can transform love and romance.

New KDnuggets cartoon gives you a respite from the virus and politics and issues of the day, and looks at how AI can transform love and romance.

A Scientist:

Our AI has come up with “Dating in the cloud”. It scans your social media posts and comes up with a great profile for you, automatically inflating your resume and making you more attractive. And no need to decie who pays for the meal!”

and KDnuggets posts tagged
cartoon.

# How AI Revolutionize the Way Video Games Developed and Played

Published

on

Artificial intelligence is simplifying our lives and changing the way we perform everyday tasks. An AI revolution has already taken place in many industries, like healthcare and marketing. But is it going to affect the future of video games as well? The simple answer is yes.

“Although AI has been an important part of video games since their birth in the ’50s, it’s only lately developed to a point where it can be used to control complex characters.”

The technology can now process information from players and make the environment more suitable for their needs.  And what can we expect for video games in the future? Can we soon see self-thinking characters with complex countertactics in first-person shooter games? Or all the human staff replaced by robots in online websites with games like Eye of Horus? Let’s take a closer look at how exactly artificial intelligence will revolutionize the gaming industry. Ready?

### Will Video Games Get Smarter?

To be honest, there hasn’t been a radical change in how AI governs the behaviour of various virtual entities or powers the procedural generation. AI’s most important components are still pathfinding and finite state machines.

Pathfinding is basically getting from one point to another in the simplest way, and it’s used in all games. And a finite state machine is built for non-playable characters (NPCs), and it allows them to change between different states.

However, some new video games are now also using behaviour and decision trees that have become more sophisticated recently. And although most developers are operating with the same basic concepts (pathfinding and finite-state), they can utilize them on bigger scales thanks to higher processing powers in 2020.

### Games Will Become More Adaptable to Smartphones

A gaming console is not the only equipment to play games on. A smartphone offers the unique possibility to play on the go, so it has become an increasingly popular option for gaming. And since the processing power of mobile phones grows every year, the games for these devices keep getting better and more immersive.

However, video game fans still need a PC or a console to play the latest games since the weaker filling is not enough to enable mobile platforms to run them. But here’s where AI comes to play.

Every mobile game developer who creates new video games for smartphones is constantly coming up with new AI algorithms and the games keep getting smarter. Looking at mobile games only 3 years ago, we can see immense improvements. Let’s take a look at some key improvements in games made possible by advanced AI.

### Environments Are Getting More Authentic

Everyone’s probably noticed that video games are getting more realistic every year. The environments get more responsive and richer in detail. And that’s all thanks to AI. Using machine learning, AI can respond to any actions a player takes in the game more accurately. AI itself can generate environments that predict your expectations.

For example, the scripted plots that follow only one possible sequence of events are hardly present in any modern game. Instead, it’s up to the player’s decision on which direction the game takes. The plot has many possible directions. This means that you can play the game many times, and the scenario will always be fresh.

However, surprisingly enough, a powerful AI might not provide the most fun gaming experience. Because here’s the thing: if AI gets too unpredictable, the non-player characters it leads can start to direct the players to unnecessary routes. To places that lead to nowhere. It may be a fun experiment, but ultimately players are loving gaming because of the thrill of advancing to the next level. So most probably

AI in games will keep getting more intelligent to interact with players more convincingly. But it will still be completely controlled to keep everything on track.

### Improved Visuals

The video graphics in modern games are so good that sometimes you can even mix your sense of what’s virtual and what’s reality. This has obviously not been achieved overnight. It’s made possible by hundreds of developers constantly working on new solutions. But we can hope AI to considerably accelerate the process by automating it.

Maybe in the future, we can have software that generates a game environment by scanning real cities. Just imagine having battles with zombies on the streets of your own hometown.

### Conclusion

In the future, we can expect more advanced AI in games making the non-player characters react to your actions with more variety. In first-person shooter games, NPCs can soon make more decisions and coordinate tactical attacks against the player. We can also expect more automized gaming sites.

And AI is not only powering the characters and scenarios in games. It’s also put to work to develop games faster and cheaper than ever before. And that’s all revolutionary in the gaming business. Are you ready for it?

How do you think video games will look like in the future? Completely powered by AI? Leave comments below, we’d love to hear your thoughts.

— Thomas Glare endeavoured to explore the world of tech and is currently in his master’s program of Cyber Security who loves to create slot machine games for android.

# Internet of Things Impact in 2021

Published

on

The internet of things — smart devices that connect to the internet to share and receive data — is probably one of the biggest tech success stories of the past 10 years.

While most consumers know about IoT from consumer-oriented smart devices — like home assistants and security systems — the tech is also vital to many industries. From remote patient monitors to technology that collects factory data and controls massive industrial machinery, sending information over the internet has major benefits for all types of companies.

“The IoT revolution isn’t done yet. 2021 is likely to be another big year for it. We may soon see some of the biggest changes to date as developers find new ways to apply the tech to other industries.”

Based on the IoT industry’s current momentum and direction, these eight changes are some of the most likely to happen next year.

### 1. New, More Interoperable Smart Home Devices

As the range of smart home devices grows, interoperability — having tools from different developers that can “talk” with each other — will become much more important.

Manufacturers of IoT devices are making communication between them a key design consideration. It may soon be more normal to coordinate devices from a handful of developers rather than depend on all-in-one solutions that manage your home environment or provide extra security. Instead, smart homeowners may be able to string together complex IoT tech systems, customizing based on their needs and preferences.

### 2. Adoption of IoT Will Be Almost Universal

According to a new report from Microsoft, 91% of global businesses have adopted IoT technology, up from 85% the year before. The same report showed that more than half of all companies plan to invest even more in IoT technology going forward.

The growing range of IoT solutions — from office management tech to new maintenance tools — means that any business can benefit from IoT tech regardless of industry.

In 2021, it could be unusual to work with a company that doesn’t use the internet of things in one way or another. By the end of that year, we may see something close to 100% adoption of IoT.

### 3. 5G and Edge Computing Will Make Near-Real-Time Analysis Possible

After a slow rollout in 2019, major carriers are beginning to deliver 5G coverage on a national scale.

The speed of 5G, plus edge computing tech — which establishes nodes on the edge of the network that can be used for simple calculations — may make close-to-real time analytics in IoT devices possible. This ultra-fast communication will make the technology like driverless cars and real-time industrial sensors more practical going forward.

### 4. Hospitals Will Adopt a Range of IoT Tech

Over the past few years, developers have started to create various IoT devices for health care professionals. These devices — like internet-connected patient monitors or health-tracking wearables — make it easy for doctors and hospital staff to track a patient’s health, no matter where they are in the building. This could help staff check up on people across floors from one workstation or respond faster to a health crisis.

Shortly, real-time location systems for health care, which allow hospitals to track patients, manage assets and ensure compliance, may become central to the industry. At the least, it could become another valuable tool for health care professionals.

### 5. Cybersecurity Will Become a Serious Concern

As IoT devices proliferate, they’ll also become a bigger target for hackers. IoT security has improved significantly in the past few years, but they remain uniquely vulnerable to attacks. These safety risks make IoT devices a major opportunity for hackers wanting to break into a secure home or business network.

For developers and companies using IoT devices, keeping IoT tech secure will become critical. Investment in cybersecurity technology will likely grow to levels higher than anything we’ve seen so far.

### 6. Big-Name Retailers Will Implement Smart Store Technology

Following the semi-successful launch of Amazon’s line of cashier-less stores, Amazon Go, retailers have started to invest more in smart technology for their brick-and-mortar locations.

There are smart shelves, for example, outfitted with weight sensors and cameras to detect when products have run out. Similar tech can automatically check if there are carts that need to be pulled in or customers waiting to check out.

The data from these devices, coupled with AI-powered analytics, may make retail management more efficient. Right now, the tech is still experimental — but a few brands, like Walmart, are already testing smart store management at a few locations.

### 7. Predictive Maintenance Will Remain Key for Heavy Industry

Predictive maintenance is one of the more practical applications of the internet of things, and a decent number of industrial businesses already use it. The owner of heavy machinery or industrial infrastructure — like a robot arm, transformer or earth-mover — installs special sensors on certain pieces of high-value equipment.

These sensors gather data on operational characteristics, like vibration, sound or temperature. Over time, this data analysis can give owners a heads-up when equipment is behaving unusually — a sign that it may need emergency maintenance or repairs.

The predictive maintenance market has grown fast over the past few years, and industry analysts estimate it will be worth more than \$12 billion by 2025 — up from just \$4 billion in 2020. 2021 will probably be a key year for the industry — one where we’ll see continued adoption of predictive maintenance tools and platforms.

### 8. Self-Driving Car Tests Will Ramp Up

More companies are getting involved in self-driving vehicles in one way or another. Ride-sharing companies, Big Tech businesses and logistics experts are all invested in making vehicles that can drive themselves.

Demand for self-driving cars, as well as other issues — like the ongoing shortage of truck drivers — will likely push companies to expand their tests in 2021. These vehicles still need some serious testing, and its likely tests won’t be done for a while. However, some of those experimental autonomous cars could be on the road by the end of 2021.

### How the IoT Could Reshape Businesses in 2021

The internet of things is likely to continue having a major influence on the economy through next year. New IoT devices, plus supporting techs like 5G and edge computing, mean that just about any business, regardless of industry, will be able to take advantage of what these tools can offer.

Consumers are also likely to see big benefits as well. While self-driving cars aren’t expected to hit the market until later in the decade, other consumer IoT devices will probably become much more user-friendly. For smart home fanatics who want to outfit their living space with gadgets that can adjust the temperature, dim lights and keep an eye on the front porch, big changes to interoperability will make life better than ever.