Undaunted Normandy
Developer Blog #3
Some good news to start with - Undaunted Normandy Digital has an early access release date. It’ll be available for PC and Mac on the Steam store from Friday 28th July.
What does Early Access mean in this case? And let’s be very clear - this is early access and not the full release.
In the credit column, there will be fourteen scenarios available to play. Everything from the board game plus a couple of bonus scenarios that have been published since. You'll be able to play either against the AI, against a local opponent, or by email (asynchronous). There’s a tutorial to help new players (although this needs more work). Steam achievements are enabled. There are two versions of the AI available, including a stable standard AI, and a machine learning AI. Anyone who has been following the development of this game for the last while will be aware that I’ve had the ML AI in training for a long time now - nearly a year, and it’s taken over 20 million turns in that time. It's still running while I write this. However, the randomised nature of Undaunted Normandy is proving a challenge for it, and as a result it can take odd turns from time to time. Nevertheless I still think a fully self-taught ML AI is an exciting thing, so I’ve left it in the game, enabled just for the first scenario (you’ll find it under “Experimental AI” in the menu). Sometimes it beats me, sometimes it does something stupid. The standard AI works for all scenarios of course. Beyond that the game has been extensively tested on both platforms, and while there will almost certainly be a few bugs it’s pretty stable.
In the debit column, the PBEM solution hasn’t been tested with a significant number of players so in the early days it might struggle (or it might not). The graphics and audio still needs polish (although some will be glad to know that you can switch between board game and 3D visuals). As mentioned, the tutorial needs a bit of work. Campaign mode isn’t enabled yet - this will follow the mode in the board game.
As always the game will be supported during early access, into full release and beyond. This has never been intended to be a release and drop game. I would like to ask one thing: the life of an independent developer can be challenging at times, particularly from a time management point of view. For a number of reasons my available bandwidth has reduced in the last year - that’s one reason why the release date has slipped more than I’d hoped. Bearing this in mind I just ask for your patience if it takes a bit longer than I’d like to resolve any issue or implement any feature that you might request. But I can guarantee that I will do my very best to make the game as fun as possible.
Hopefully that gives you a good understanding of exactly what to expect from early access. However, if you have any questions please post them here or in the discussion board and I’ll do my best to answer them. I try and check the board every few days, although it’s not always possible.
Developer Blog #2
A decision based AI has already been written and tested. By and large the goal with it is to not do anything stupid. For example, if it’s standing on a victory location where capturing would win the game then it should do this. The AI is made up of lots of little rules like this to help it make the decision. In this sense it’s not too far from Undaunted Reinforcements. In fact I did consider basing the AI on the Undaunted Reinforcements one but too many of the game elements are changed by this expansion, and I also wanted an AI that played according to the basic game rules.
Moving on to the Machine Learning (ML) AI then. It uses a branch of ML called reinforcement learning. The idea is that it constantly plays against a version of itself that is just a little bit better or worse than the current iteration it’s testing. When it wins a game it gets a points reward, and through this it aims to achieve a version that achieve this as often as possible.
In order to allow the AI to understand how it archived the reward, it needs to understand the game state at each decision point. This means that you have to provide it with the information that it’s going to use in order to make this. If you’re playing Undaunted Normandy at home, you’ll look at your cards, look at the board, and make a decision about your next move. What you’re actually doing is considering a number of variables relating to the game state and then making your decision based on this information.
The ML AI solution tries to achieve the exact same thing. The key question is, “what is the minimum set of information I need to make a decision about my next move”. In ML parlance this is called collecting observations. And you want to use 1s and 0s wherever possible to simplify the computation required. The answer I arrived at for this question was the following: 5 indicators, one for each possible card (this is just the first scenario remember); the number of points needed for the AI player to win; the number of points needed for the opposition player to win; the number of AI riflemen cards in the deck (for pinning rules); the number of enemy riflemen cards in the deck (ditto); and for each tile on the board information relating to its x and y position, defence value, tile victory points, whether it’s scouted or controlled, and whether each of the four unit types in the scenario is in the tile.
That’s a total of 213 observations! Think about that the next time you’re taking a turn in Undaunted Normandy. It’s remarkable how much information the human brain can take in without realising it. Subsequent scenarios will be more complicated - more units, more tiles, etc. Oh, and throw the random numbers that are generated by combat into this equation.
The AI ML then starts up and running. At time of writing it’s currently made over 2.6 million decisions and counting. It plays one game of Undaunted Normandy every 20 seconds. If I had to guess I’d say that so far it’s played around 85,000 games (unfortunately it crashes occasionally when the AI doesn’t get a response, so I can’t leave it running constantly).
And after this it’s still taking some pretty stupid moves. There could be two reasons for this: either (a) it’s just a slow process and with that much information is just going to take time, or (b) the ML configuration isn’t quite right somewhere and needs tweaking. I suppose a third option could be that the random factor of combat is messing with things a bit as well. My hope is that this evens itself out over time.
In a typical data science ML environment (the type Netflix might use for their recommendation engine) a data scientist will build a model, test it, change it, test it, etc until it’s just right. But that is a more scalable working environment, so it’s easier to iterate. Unfortunately I can only have one version of the game running at one time on my dev laptop, so it’s not a scalable environment, so it just takes longer.
For now then I’m sticking with the current solution, and hopefully brute force will get the job done.
In the meantime of course the release date is getting nearer and nearer. I think what this means is that the game will go up in Early Access with the decision based AI available on all scenarios, the ML AI available as an experimental option for the first scenario (expect it to do some stupid things). And multiplayer of course. More on that next time.
That’s all for this time. If you’ve learnt something in all of this then my work here is done for now!
Developer Blog #1
One of the most important components in any strategy game is the AI strength. The graphics can be the most beautiful ever created but if the AI opponent plays badly then, outside of multiplayer, there’s very little challenge for the player.
The original plan was to make a decision engine solution. Each turn the AI would consider the board position and make a move according to a set of hard and fast rules defined for it. For example, if the opponent is on a tile where it could win, either move on to that tile or shoot at it. In the most part this works ok, and this is currently the fully implemented AI. You can find a video of me playing against the AI here (https://www.youtube.com/watch?v=CyIyBfLqQ0o) and you’ll see it makes fairly sensible decisions all of the time.
I’ll admit now that in online playtesting I’ve discovered that I’m not the strongest player of Undaunted Normandy. I’ve played a lot of games in every scenario, and I lose as many games as I win. Probably more. However, against the decision engine AI I’m winning most of the time, so although the engine plays a good game, it could still improve.
Having given this a lot of thought, and with a few false starts I’ve decided that the solution to this is potentially to use a machine learning (ML) AI solution. This means setting up a training environment where the AI plays against a closely matched version of itself, gradually improving as it progresses and learning from what it’s doing. The best analogy I read was that it’s a bit like a tennis player. If you play tennis against Roger Federer, then you’ll lose heavily and won’t have learnt anything. Similarly if you play tennis against a 5 year old child you’ll win easily but also won’t have learnt anything. The best way to improve is to play against someone just a bit better than you.
You then have to consider how you’re going to configure the ML environment. The best approach is to give the AI one point for winning, and one point for losing, and then let it just go and figure the rest out for itself. In order to encourage it to get a bit of a move on you deduct a very small fraction of a point each turn. You also need to be able to provide the ML solution with enough information about what is on the board at any one point in time in order to make a decision. You provide it with a list of valid orders for a card and then it’ll pick one and perform it.
Having set this up, the next step is to provide gradual training. All of this has taken place in Scenario one in the game (La Raye) since I still want to prove that it’ll work, and it’s the simplest scenario – two types of units, standard victory conditions.
In the first instance, I just filled up all the tiles with scouted markers and victory points. The AI learnt pretty quickly that it could win by picking up the victory points, but it gave it the right idea. The second step was then to remove the victory points so that they are in random points on the board (in more or less every other space). This means that the AI has to go looking for the victory tiles. The final step was to remove the scout markers that weren’t already defined at the scenario, so that the ML solution could learn how to move scouts.
I did then make one final step, which was to make the AI play the defined scenario over and over again. However, this caused it to focus entirely on the tile in the bottom left hand corner of the map. The reason for this is (I think) that in the first scenario this is the tile that most often decides who wins the game. However, it started to create quite inflexible behaviour, so I’ve gone back to the previous step to try and keep the AI as flexible as possible (which should benefit subsequent scenarios).
At this point the final challenge with the ML solution is to get it to play thousands of games. At the moment it’s running at 20x normal speed, and can play one game every 20-30 seconds. The eventual intention is that you the player will then be able to play against an opponent who has played thousands, or maybe even hundreds of thousands of games, and this will create a proper challenge.
The risk is that we spend weeks and weeks trying to get a ML solution working and it just doesn’t learn properly, but I think the reward is definitely worth it if it does in that the player will be properly challenged when playing in single player mode.