Two by Two: 2048 AI Chain Building

The AI

The AI I am building for 2048 will be written in C++ and imported into the C# game. It is written in a different language for two primary reasons – firstly because using pointers and references significantly reduces the memory requirements and increases the speed of the program when searching through potentially large grids of cells, and secondly because I would personally like to get better at the language through practice.

The speed advantage is not to be ignored. It is possible that the AI could be adapted later to search at greater depths, in which case the time complexity increases rapidly, along with total time. It is also possible that the AI could be asked to perform on larger grids – the UI has the capability to play on grids up to 100 cells square, and that requires a lot of searching and a lot of memory if references are not employed.

The Principle

The chain starts at 64 and stops at the 8

When playing 2048, one of the most effective strategies is to build chains of ascending power of two. This means that once the chain has been completed down to a 2 or 4, when a new cell is added to the board, it can be joined with the end of the chain to double the final cell. Each subsequent cell in turn can be doubled as it is adjacent to the most recently improved cell, up to improving the largest cell on the board having combined all of the cells in the chain.

However, before the chain can even be created, there are a few ways that the available moves can be narrowed down to make searching more efficient. This includes testing how many moves are possible, and whether the chain can even be built at all: As we will see later, the chain can only be built if there is a cell in the corner of the grid.

Checking the Grid

The first check that is done on the grid is to check which directions are valid moves. It is clearly not worth checking if a move in an impossible direction is best. A side effect of this is that if only one move is possible, it can be selected without doing any further analysis.

The board is dangerous in this situation, because only one move can be made

It is also possible for the board to become ‘dangerous’, if a particular situation arises where the newly spawned cell can leave the board in a situation where there is only one possible move, and it will move all of the cells on the board. This is likely to mess up the grid, and should therefore be avoided – a move which causes a dangerous board is ‘unsafe’. The situation arises when a move would leave all rows and columns either full of cells or completely empty, except for one which can be filled by the new cell. This is checked before doing anything more with the AI, and if it leaves only one safe move on the grid, this is selected.

Finding the Corner

The next key step in the AI is to start to build the chain. The chain starts at a corner of the board, and snakes outwards in ways that allow moves without disturbing earlier cells in the chain. The idea is to build large cells on edges or corners, to maximise the number of ways the board can move without disturbing the chain, and while keeping a large, continuous free area for manipulating the small cells. Leaving gaps in the corners means new cells can appear in them, and they are very difficult to improve with limited routes in to the cell. The small cells are kept in the middle, and large cells kept in the corners, to avoid this gridlock situation.

To build the chain requires a seed – the point where the chain starts. This is always a cell in the corner of the board, for reasons mentioned earlier, so if (always near the start of the game) a corner is unfilled, the AI will try to fill it. It chooses the corner to be filled based on the weighting of the grid – trying to keep large cells in corners. The corner with the greatest number of large cells near it is chosen, on the basis that it is best suited to building a chain. If it is unfilled, the AI will move to fill this corner with the largest possible cell. However, if it is filled, this corner cell is used as the basis of the chain.

The chain will search for the 8 and two as shown, and prioritise the 8

Building the Chain

Now the chain can be built in full. This can be done recursively quite neatly, but it is inherently unstable so this AI favours a loop. The chain spreads out from the corner by searching away from the current cell. The next cell in the chain is found by looking for adjacent cells. The final aim of the chain is to collapse it all into one cell, so it is critical that earlier cells in the chain do not move when combining the later cells: this will break the chain. As a result, the AI only searches in directions opposite to those which will not disturb the chain as built so far.

When a cell is found, the value is analysed. The value found defines what happens to the remainder of the chain. If the value is higher than our current end cell, it cannot be added to the chain because this would form a blockage – it cannot be used to double the current end cell. If a cell is found with the same value as the previous cell in the chain, we can begin to collapse the chain because the penultimate cell can be doubled immediately. Otherwise, if a lower value is found, it is set as the current end cell, and is added to the chain. The search then continues.

Code for building the chain of cells

A lower value cell can either be exactly half of the previous one, in which case it forms part of a major chain which is ready to be collapsed as soon as the end cell is doubled, or it can be lower than that, in which case it becomes the start of a minor chain. It will take more than one step to get this cell to a value where it can combine with the previous one. This does not change the logic in this AI, but adding a much lower cell to the chain could be given a lower priority than some other moves in other AIs.

Collapsing the Chain

A move within the chain can only be made if the penultimate and final cells are equal. The AI’s chain builder returns a variable specifying whether this is the case. Once it is established that the chain can accept a move, the direction in which the move needs to take place is found. The two end cells in the chain are retrieved and the row and column indices checked, which establishes the direction in which a move must be made in order to combine the two.

Code for finding the direction of a move, given the two cells that should be combined

It is a result of the careful elimination of different directions in the chain building algorithm that this direction will never be an unsafe direction, so the move can go ahead whenever it is found. If the chain values are halved all the way through, the process will repeat until there is only one cell in the major chain, and then other methods must be used to re-build a chain that can be collapsed once again.

These methods will be described in a later entry.

An AI for 2048

The simple mobile application 2048 went viral around the start of 2014, as a seemingly easy and fast paced online game which was still difficult to complete. As the game became more and more popular, a range of different variations appeared, as did a complementary range of artificial intelligences to solve the variations.

As a game based purely on logic, and with just four possible moves, the game is very well suited to an AI, and I couldn’t resist the challenge of building my own AI.

About the game

The grid before a move…

…And after a move upwards

 

 

 

 

 

 

 

 

 

The game is played on a 4 by 4 square grid. Cells are filled with numbers in ascending powers of 2, formed by combining other equal cells on the grid. The four available moves correspond to the four directions, left, up, right, and down, with each move causing all cells to move as far as they can in that direction, while maintaining the original order. If two adjacent cells have the same value, they will combine in the course of the move to form a single cell with double the value, but this cell cannot merge in the same move. Once all moving is complete, a new number is added to the grid in a previously empty cell. This is a 2 90% of the time; the remainder it is a 4.

One example of the board on startup.

To start with, the grid has two random cells placed on it. After the first move, a third cell is added, and the game proceeds as normal. The game ends when no more moves can be made. Each game is different, because the new numbers are added in random locations and have a random value.

Principles of an AI

The reason 2048 lends itself to an artificial intelligence is that there are only four possible outputs (moves). This allows all four of the outputs to be tested easily and quickly to determine the best output. Most systems are based on an analysis of the current game status, testing of all possible future moves, and then re-evaluation of the game situation. The move which adds the most value to the game is then chosen. This can be repeated to a search depth to identify the best move several moves into the future.

However, 2048 introduces a large amount of randomness, which makes searching to any depth inefficient. It would be possible to eliminate some of these eventualities, but a neater solution is to analyse the grid as it stands, and take a deterministic view to the best move. Often, this is easily found, so the deterministic AI has performance advantages. It also acts in a more human way, which tends more to the intelligence aspect of an AI.

I also wanted to avoid, as far as possible, scoring the board against certain measures and adjusting the weighting of these measures. This feels like a sub-optimal process, which leads to a rule-based AI. This means that a list of true-false cases describing board parameters are tested, and whenever a true case is found, a move is generated based on this case.

The AI will be a set of if-else statements, with each if case testing if a move can be found in a certain way. These categories are, for example, trying to fill a corner, or moving to avoid a dangerous situation where the board could be blocked by the next move. There will be more on the AI in later posts.

Building the game

In order to build the 2048 AI, the game needs to be built first. The game and AI are built in C#, so the application uses the WPF framework. This also provides animations and XAML, making the design of the game easy.

Designing the interface using WPF

The board consists of a 4×4 integer array, with blank cells represented by zeros. To move the cells requires a carefully designed algorithm but can be done in O(n2) time, by scanning in the opposite direction to the move. As the grid is scanned, the system keeps a record of the position that the next cell is moved to, and the value of the previous numerical cell. If a cell with the same value is found, it can be merged. Otherwise, any cell is moved to the next free cell. The algorithm is carefully designed to cope with all possible eventualities.

When a move is made, instead of updating the grid through bindings which limits the potential to use animations, the moves made are passed to the UI, which rearranges labels on a canvas. Working this way allows the move, merge, and appear animations to be synchronised. It also means that the game logic is independent of the UI, so the graphics can be changed at any time without affecting the rest of the game.

The animations take significantly longer than processing the moves, which means that separating the two leads to lag in the game if moves are not queued. Thankfully, wpf runs the animations in a separate thread, which means with a careful bit of planning the moves can be queued and the board updated in the background, with the animations running on the user interface.

To integrate the artificial intelligence, the AI subscribes to an event on the game, which is fired whenever the grid is updated and ready to receive another move. At this point, the AI calculates the best move, and returns it to the game. This generates a loop, which repeats until the AI cannot find a move.

There will be more in further posts about the development of the artificial intelligence. Now that the framework has been established, development can proceed quickly.

Adapting for Learning, Learning to Adapt

Recently, work on the Southampton University Virtual Learning Environment Review has focussed on analysing general trends in the use of VLEs, and in how these trends have come about, by evaluating reviews undertaken by other universities in recent years.

These trends and statistics will provide an insight into how the market is changing, and may allow a simple satisfaction rating to be determined. Reviews at other institutions will help to inform decisions made in this review, and may guide some of the steps.

The investigations uncover opposing trends in the sector, and opposing approaches to reviews. Some show universities adapting and selecting their VLEs for learning, while others decide that the best approach is to get more out of the current system, learning to adapt to the software and use it as it was designed.

Usage Trends

A spreadsheet was compiled of the Virtual Learning Environment used at a range of different institutions. The VLE used in 2010, 2012, and 2015 was listed, so that the change over time could be assessed. Once the data was compiled, a level of statistical analysis and data representation was applied. The full report is here.

Firstly, out of the 65 universities surveyed, the proportions using each different make of VLE over the period was represented, along with the corresponding trends in usage of each system.

Trends in VLE usage from 2010 to 2015

Number of universities using each system from 2010-15

The graphs show a general trend away from Blackboard, with a growing market share for Moodle. Other systems hold generally constant, with only a slight trend away to Moodle. Over the five year period, Moodle is the only VLE to have grown in popularity. This shows a tendency for universities to pick a system designed for a slightly different form of learning. It is also a general trend towards open source software which is more flexible – institutions are keen to adapt the system to tailor their learning.

The general trend also sees more universities moving away from Blackboard than Moodle – in fact, no universities migrated away from Moodle at all. This is interesting, and a statistical significance test demonstrates that there are fewer reasons to move away from Moodle than Blackboard.

Seven of the 39 universities using Blackboard in 2010 migrated, in addition to three of eight not using Blackboard. Using this, we can construct a null hypothesis that there is a 21% (10/47) chance of a university changing its VLE in the space of five years.

Now applying this hypothesis to the universities which have maintained Moodle throughout – 16 in total – the chance that none have migrated away from Moodle in the five years is 2%. There is therefore evidence at the 5% level that the null hypothesis can be rejected, in favour of a hypothesis which suggests there are fewer reasons to move away from Moodle than from other providers.

If we were to assume that these figures are exactly on the 5% level of significance, to allow comparison between satisfaction ratings, it emerges that in a five year period, it is equally likely for 30% of universities to migrate from Blackboard as it is for 17% to move away from Moodle. It could therefore be suggested that Blackboard is more likely to be replaced as a VLE than Moodle.

Trends due to Situations

The number of students at a university could impact the choice of VLE. In particular, some systems may be better designed to handle large numbers of courses and deal with large numbers of students submitting and storing work online. To test this theory, the mean and variance in the number of students at universities using each VLE was calculated. Calculating these parameters allows normal distributions to be generated, showing the likelihood that a university of a given number of students uses a given VLE. In effect, this shows the most popular VLE given a university of a specified size.

Popularity of VLEs against number of students at university

The graph demonstrates that for a wide range of attendances, Blackboard is preferred. Moodle is third-most popular for most of the distribution, as it also lags behind bespoke systems, which are typically implemented at small institutions. Canvas is also considered here, with data from the USA being used to form the distribution.

The reason for this trend could be a general tendency for larger universities to favour a managed, supported system in Blackboard and Canvas, while smaller universities are able to tailor their requirements more effectively using an open source and customisable system.

It is also conceivable that fewer large universities have migrated away from Blackboard, because of the technical challenge required to move all of the courses onto a new system. More students means more courses, and this takes extra time and therefore cost to set up on a new system. Smaller universities are able to adapt the system for their learning, but larger universities must learn to adapt to the proprietary software.

The trend due to university group was also investigated. It was suggested that Russel Group universities may tend towards a different system to University Alliance group members. This was evaluated using a grouped chart:

University VLE usage, grouped by University group

No signifiant trend was seen in this grouping, although this gave further weight to the theory that university size had an effect. A large bias towards Moodle is seen in the 1994 group, composed of the smallest universities. The largest universities are seen in the University Alliance and Russel Groups, which both favour Blackboard. Canvas, only seen here in the USA, is a middle ground.

Other Reviews

A range of other reviews were collected, summarised, and analysed, in order to determine the way that other universities had gone about choosing their VLE. Each university studied had approached the problem in a slightly different way. This drew some important points to consider when conducting the Southampton Review.

There are a range of parameters that need to be considered in conducting a review, and the way in which the review is conducted will be influenced by the specification and scenario. In particular, reviews can be conducted by setting up either a specification or test cases to evaluate the effectiveness of a system. The systems can then be piloted, or user satisfaction surveyed, in order to respond to these specification points and gather sufficient data to rate the effectiveness of each system against the requirements.

Also important to consider are the costs and the hidden costs. For example, the cost of upgrading the system and the cost of maintaining the new system, in addition to any infrastructure changes that this may require. The cost of training new users of the system, and as a result losing time and momentum on existing projects, is not negligible.

Finally, it may be possible to improve user satisfaction simply by redesigning the content provided on the same VLE. The design of the content and the actual content provided has an impact on the ease of use and overall satisfaction in addition to the design and layout of the software used.

Summary

The outlook in the VLE market is changing. Blackboard is becoming less popular, in favour of Moodle, and Canvas is also breaking into the UK. To arrest the decline, Blackboard has released a major overhaul of its interface, focussing more strongly on the user satisfaction while using the system.

However, the fact remains – these systems are used for learning. Often, user satisfaction comes from being able to use the systems in a familiar way, without having to undergo extra training. It is perhaps the case that an element of ‘learning to adapt’ needs to be seen in the VLEs to help improve digital skills and allow students to get the most out of their experience, instead of an ‘adapt for learning’ philosophy where optimum content may not be delivered in an effective and efficient way.

There is much to consider as the review progresses over the next few weeks.

Presenting Challenges Presents Challenges

Following a meeting with a group of other interns within the Iliad at Southampton University, where we discussed a range of different presentation tools, it’s time for another reflection on how to present the outcome of this review.

It’s not easy to make an effective presentation, despite the range of tools available. The software isn’t everything, and the challenge of engaging an audience remains. When presenting the challenges overcome for a particular project, or detailing the targets for the next one, the presentation of information to an audience is key.

What’s Out There?

The interactive session, delivered by Fiona Harvey (@FionaJHarvey) covers all sorts of ways that presentations, discussions, and announcements can be made far more interesting through the use of software. Starting with some pretty basic tools, and then covering increasingly complex and capable pieces of software, and supplemented with demonstrations, seven different presentation methods were covered.

• ThingLink – a resource for making images interactive. Hotspots are added to any old background image, which when hovered over, display links and text to add further context. It’s a great way of adding extra detail to an image without covering parts of it up, and a quick and easy way of labelling a picture without delving into complex editing software.
• Sway – a new Microsoft Office app which tells a story. It’s a bit like PowerPoint, but it’s not slide based. Instead, images flash across the screen, accompanied by text, embedded tweets, videos, and interactive charts. Being part of the new Office suite, it’s cloud based and can be shared simply by copying a link, but it can also be embedded within pages.
• Adobe Slate – the adobe offering to compete with Sway. Based as an IoS app, it allows a gallery to be accompanied by captions, comments, and animations to make the transition smoother. It can be used as the background to an on-stage presentation, but is far more effective at demonstrating things to small groups on a mobile device.
• Emaze – purpose-build presentation software. It’s slide based, but shows the slides in a totally different way to PowerPoint. Instead of sliding through a screen, they are displayed on walls in a gallery to be viewed as the audience walks through, or passed down by the Hands of God. Something novel, and fresh, but with all of the content formatting tools necessary to present information.
• Prezi – everyone’s favourite alternative to PowerPoint. The classic open canvas, with slides of all sizes and orientations swept out by the flying camera, is ideal for infographics and presentations with a bit of structure. ‘Seeing the bigger picture’ comes to mind, which is probably exactly what it was concieved for.
• HaikuDeck – a tool for creating dynamic, animated presentations very quickly. It has a resource of stock images, which accompany any text added to the slides. Aside from helping you spot the unfortunate double-entendres, this gives the presentation a professional backdrop. If only the animations, transitions, and themes gave the same feel.
• VideoScribe – this draws the presentation on-screen in real time. Like all of those marketing campaigns where the on-scree text is written out by a hand as it goes, images and text are coloured in to produce a video to accompany this presentation. It’s slow to present the content, but does make it memorable. A resource of images makes the presentation very quick to put together. It is designed to tell a story, so the open canvas has a flow to it – something not obvious at first but very subtle and powerfull if used correctly.
• PowToon – another video creator… but this time it’s free. Stock animations, pictures, and characters accompany customised text to get the point across with added emphasis. In addition, music accompanies the video, generating an immersive presentation experience. The best stuff is available in the paid version, but it is easy enough to get started for free.

Making Effective Presentations

It’s not all about the software, unfortunately. The content is still key, and it still has to be interesting and engaging otherwise no amount of furious animated drawing is going to convince an audience. In some cases the software can paper over cracks, but in others it is makes them glaringly obvious.

The presentation software also needs to be used appropriately. In a formal setting, it needs to be formal. In an upbeat setting, the music can’t be from the Titanic. And so it goes on – choosing the right tool is vital.

This means there is no clear best option. When a presentation has been concieved, the information collected, and the structure decided upon, the best tool for the job can be chosen. The trouble with the software available is that it tends to force the structure of the presentation too much, getting in the way of a clear, well presented delivery. If the presentation is designed to have distinct sections with different themes, but they merge together, there is a lack of clarity in the content being presented, which makes the presentation less effective than it should be.

Once the structure has been determined, there is almost certainly something available which can accentuate the structure, bring it out, and make the content the focus, while maintaining interest and keeping the audience engaged. This is the key to a good presentation. In summary, make sure the tool isn’t driving the presentation.

What’s Changed?

A few years ago, even animating the text entry on a PowerPoint made it look unprofessional. Viewers would tut quietly as a title came in letter by letter – but that’s exactly the effect generated in many of the above options.

Nowadays, PowerPoint is seen as the old-age approach. In the days of Web 2.0, software as a service is a popular, and growing, concept. The explosion of available software has also provided many different alternatives, and in a generation where standing out from the crowd is so important, PowerPoint has had its day. To an extent, anyway.

There are some times where the data just has to be presented, and PowerPoint is still number one for interacting with other office products, which makes it invaluable for linking data to spreadsheets and showing statistics. However, increasingly, making something seem a bit different, new, and otherwise unusual is a great way to make it memorable.

The animations, transitions, and new themes available in these different presentation media covers that exact specification. New, different, and a little bit quirky – all designed to grab an audience.

Impress.js: a html presentation tool.

But if PowerPoint got boring, so might these. There will be a time when everyone has seen a PowToon, everyone has made a Sway, and they are no longer new, or different. Perhaps things will take another step forward, maybe to HTML based presentations like impress.js. Or perhaps PowerPoint will come to the fore again, seeming new and different because nobody has seen one in the last five years.

It’s a tricky one to stay on top of, keeping up to date and relevant, choosing the right tool for the job, and ensuring that something new, fresh, and previously unseen comes in to everything. It’s well worth it though, because presenting information is the interface through which people know you, and know your brand, and your business. Getting the information across is critical to ensuring the success of whatever is being presented.

Active Suspension Modelling

My previous post discussed the potential for implementing an active suspension system in a Formula Student car. Modelling and development has now taken place to prove that the system can work properly, and does provide an improvement over a passive system.

Which Type?

Of the five types of active system discussed previously, only two provided adequate redundancy in the case of failure. These two consist of an actuator in parallel with the spring, and an actuator in series with the spring. Both perform essentially the same task, the only difference being that the parallel system has full authority over position and therefore secondary authority over spring rate, and the series system has full authority over spring rate and thus secondary authority over the position.

The two possible layouts for the active suspension system

The two systems can be customised to provide exactly the same range of functionality when it comes to actually managing the suspension. The differences come in layout, packaging, and failure modes.

The series system requires a rocker at both ends of the spring, with the pull rod at one rocker and the actuator at the other end. The actuator is permanently carrying the full load of the wheel, which could be up to 1000N, as it is acted on directly by the spring. If it fails to a locked position, the suspension continues to work as if it was passive, but if it fails open, the sprung mass will collapse and could drag along the ground.

The parallel system is the opposite – if it fails open, the system will continue to work as if it was passive. A passive system also has the spring and actuator connected to the same rocker at the end of the pull rod, which allows improved packaging. The actuator and spring can both be located outside of the chassis so as not to encroach on driver and steering space at the front, and exhaust, battery, and engine mounting points at the rear.

As a result of the benefits in packaging and reduced impact in the result of a failure, which is more likely to be a failure to an open position.

Implementation

The main ways of powering actuators are pneumatics and hydraulics. However, electromechanical options have recently become more efficient and could provide an alternative. Choosing the actuation medium required a careful study of the weight and cost of systems involving electronics and pneumatics. A hydraulic system was ruled out due to the power loss caused by driving a hydraulic pump from the engine.

It was established that a pneumatic system is marginally lighter, at 3.5kg rather than 4kg, because despite requiring eight solenoid valves, the electromechanical actuators are much heavier. They are also locked unless powered, requiring them to be installed in a series configuration. This leaves the pneumatic system as the only viable way of powering the actuators.

The additional complexity of a pneumatic system is something that will provide challenges during the design, manufacturing, and installation stages, so it is helpful to have clear layout diagrams to show how the system will be installed.

The additional weight is somewhat of a concern – 3.5kg is more than 1% of the car’s total weight, and will have an impact on the handling, acceleration, and braking. The system will have to work effectively and reliably in order to be justified.

Modelling

Now that the system type and layout has been prescribed, modelling can take place. The first step was to create the components in SolidWorks, and build an assembly which accurately models how the components interact. This means ensuring that bearings are correctly mated, and the actuator and spring are installed with the correct spring stiffness and available force. The rocker motion ratio is also chosen based on the required wheel rate and spring rate.

The active suspension design, modelled in SolidWorks

SolidWorks provides Motion Studies – these allow forces to be applied to the components to observe how they respond under load. This is of particular use to the active suspension system: a load can be applied to the pull rod and the actuator, and a spring modelled where the spring/damper is installed. The study can then be run to investigate how the suspension moves over time, and work out what effect the actuator has.

To test a variety of different frequency inputs, the pull rod is set to provide a constant static load, in addition to loads at 7Hz, 0.8Hz, and a ramp. This provides a load pattern as shown. The actuator is configured to respond to these loads in a range of different ways in different tests – more on that in a later post.

The function describing variation of pull rod loading with time, including a graph of how it varies

When all of the force inputs have been defined, the spring parameters have been specified, and the initial position of the system is configured, the study can be run. Here, the study has been configured to track the forces in the pull rod (bottom graph) and the actuator (middle graph). It also shows the displacement of the spring (top graph).

The actuator is switched off half way through, to allow a direct comparison between the behaviour with and without the active component. This is the control in the experiment. Calculations are completed once every 0.025s, or at 40Hz, to try to accurately represent the behaviour of the system.

 

 

 

 
 
 
 As a result of the models, it is clear to see the benefit that active suspension provides – if it is correctly controlled. The top two graphs show a reduced level of overall suspension travel, although there are some spikes on the left-hand one. The lower two, however, barely reduce the travel at all. There are some methods of controlling the actuator here which are not suitable for the car, as they in some cases increase the amplitude of the oscillations. The third and fourth control methods are the most effective at keeping the mean position of the spring constant, thus allowing the spring to deal with bumps while maintaining the level car due to driver inputs.

For now, it is sufficient to prove that the active system works in theory. It responds properly to the inputs and does not tend to cause any spikes that could cause a loss of control. It maintains a stable platform, but leaves the coil spring to deal with high frequency inputs. Having proved that the concept works in theory, the next step is to take it to something which could work in practice. That means designing the system, laying it out, sourcing components, and building the control software. It’s an exciting summer ahead!

Block layout diagram of a pneumatic system (click for high resolution).