155. Optimising the Threes game simulation (part 4 of Threes project)
Optimising is just a fancy word for making it run better and faster.
In my last post, I created a simulation that played out a few moves ahead, using random numbers to decide what tile was added on each move.
In this post, I want to make my simulation play as well as possible, and also figure out if there is a winning strategy for me to play against the real app.
Program Speed
Whenever you are working with simulations, you will want them to run faster, because you usually want to use more of them if you can.
My default simulation looks 3 moves ahead, and repeats it 50 times, to find which move I make next, will give me the best result after 3 moves.The reason I need to repeat it 50 times is that a random tile with value 1, 2 or 3, is added after each move, on a random square, so I need to repeat the moves many times, using random numbers to choose the new tiles, to get an average result.
So if all four directions (up, down, left, right) can be used for each move, then the number of moves I have to make in total is:
4 x 4 x 4 repeated 50 times = 4 x 4 x 4 x 50 = 3,200
If I want to look one extra move ahead, that will multiply the total number of moves by 4.
If instead, I want to double the number of times I repeat the three moves.
Probably, I would like to do both if possible, looking perhaps 5 moves ahead and repeating 200 times, which is 4 x 4 x 4 = 64x larger than my current settings . But my program is only just fast enough at the moment, so how do I make it run 64 times faster?
I probably can’t, so I need to work smarter instead.
How much simulation do you really need?
My experience in (random) simulation comes from finance, and I have two key guidelines from my work there:
Less is better
When doing any kind of modelling, you are trying to simplify the real world and get realistic answers with as little work as possible. Keeping things as small as simple as possible not only makes things run faster, but they are easier to understand and fix – as we programmers know well!
It is surprising, though, that many people don’t realise that a bit of thought before you start can save a lot of time. I have seen a week’s solid run time reduced to just a few seconds like this. In another case, I used to use a software program I had written, to advise senior executives on something, until I realised a simple formula gave much the same answer, so after that I just took pencil and paper with me!
Tune it
You should test all your inputs and assumptions, and use just enough simulations to give you a stable answer. What I mean by stable, is that whenever you run your complete simulation program, you should get pretty much the same final answer each time. In other words, your answer can be trusted not to jump around too much.
So if you can get stable (ie very similar) results with 50 repetitions, there is no need to do 200 repetitions, unless you like wasting your own time.
The same applies here. We want to do just enough simulation to give us the best move possible.
So…
I said above that it would be nice to look 5 moves ahead, but I am adding a random tile after each move, in a random position, so the further I look into the future, the more random it gets. So maybe 5 moves isn’t necessary because there is too much uncertainty for any firm prediction.
I altered my program so it simulated each move for 3, 4 and 5 moves ahead, stored the results, and then went to the next move. A complete game gave me a series of 80 moves, with the best move predicted based on 3, 4 and 5 moves. I could then examine these and see how often they matched up. If looking ahead 3 moves gives much the same answer as looking 5 moves ahead, then there’s no need to go beyond 3. And that’s what I found, 80-90% of the time.
I also tried using a larger number of simulations, 100 or 200 rather than 50, and again, 50 seems to be enough.
So my default does fine.
So is there a great strategy for Threes?
I tried this a couple of ways. I played a game and compared my choice of move with the program. It only agreed about half the time, and more than a quarter of the time, it moved in the completely opposite direction (ie if I was moving left or right, it would move up or down). I could see that some of the time, its moves were a bit neater, but I wondered if sometimes, it didn’t really matter because we’d get back to the same position a few moves later.
You can see the sort of moves the program makes by runnig it yourself, or just watching this video
So I did a more thorough test, playing several complete games myself, and then getting the program to play the same number of games, and comparing the results. I stopped after 6 games when it became obvious the program was scoring far higher than I was.
There probably is a great strategy for Threes, but it’s not obvious enough for me to outplay my own program. I think I move too impulsively, and I don’t think visually, so that even though you only need to look 2-3 moves ahead, it’s too hard for me.
So all that work to find out that I suck at Threes!
coolcodea 