Friday, 16 October 2015

Rock Paper Scissors AI | Pattern Recognition Algorithm

Introduction

Hello and welcome to part three of our series on AI strategies for the classic game of Rock Paper Scissors. This post will walk through the high level requirements for the AI strategy, refine them into Gherkin format acceptance criteria, make those executable using Cucumber, and then implement the requirements using TDD in Java. At the end, we should have a fully implemented, fully tested AI strategy for use in our Rock Paper Scissors game.

The second AI strategy we are going to be implementing is a pattern recognition algorithm based on Markov chains. We will be implementing this in the simplest way we can for now- by storing a list of the moves played by our opponent and querying those. This algorithm will choose between playing rock, paper, or scissors depending on what it thinks the opponent is going to play, based on what the opponent has previously played.

We are moving on to using a pattern recognition algorithm at this point as we already have our random algorithm to start with and get a feel for what our opponents pattern is. It's also meatier than the pseudo-random algorithm, but can be started out more simply leading us to iterate on and improve it over time.

Formulating the Requirements

This will be a little bit more difficult than it was for the random algorithm. We know we want the strategy to work by looking at what moves our opponent has previously played, and then base our next move on what we think they're going to play next. Our algorithm needs to keep track of the state of the game, so we need to be able to feed it that data. Then it needs to use this history to decide it's next move, based on recognising patterns in the data it has collected. Ok, but what do we do if there is no history? We know we already have a strategy which employs a pseudo-random algorithm to choose moves, so we could just use that. But then the two strategies become conflated, and if you ever want to measure performance of using strategies into a kind of meta-strategy, then that won't work very well. Let's defer this decision until later. In the meantime, if we don't have enough history to make an accurate prediction then we'll just use good ol' rock, as nothing beats that.  

Formulating the Acceptance Criteria

As before, we are going to need to massage our requirements a little bit to get them into a format that we can use for automating the acceptance criteria. 

Hey look, we've jumped straight into acceptance criteria marked up ready for Cucumber to execute. The tiny additional syntax shouldn't make any difference when reading the requirements at this stage, and it saves us time converting it later.

You may notice that the acceptance criteria is quite high level- we just say that if it looks like the opponent is going to play a move, we will play the move that beats them. This serves two purposes- the first is that our requirements are readable and obvious to anyone without requiring any technical knowledge. It also hides the complexity away in the step definitions, so if "it looks like the opponent will play x" changes meaning, it only changes the implementation of the requirement rather than the requirement itself.

We also don't have the massive headache of testing for randomness for this algorithm- it should behave the same way every time for a given input, which is going to make testing much easier.

Understanding the Acceptance Criteria

So whilst the acceptance criteria might have clear requirements and be easy to test, that doesn't help us if we don't know what it actually means. We have a very wooly looks like the opponent will play a move which... well, it isn't really that descriptive. What does it mean for it to 'look like' the opponent is going to play a particular move? How do we know? 

Well, fortunately our product owner has done a little bit of prior reading and knows about Rock Paper Scissors AIs that already exist and how some of them work. She has stated that we probably want to look into Markov Chains and build up a model of moves the opponent has played and work out the probability that they will play a particular move on this turn. You can see this kind of thing in action and play against the AI on the New York Times Rock Paper Scissors page

Hopefully we have a good enough idea of what we're trying to build now. Looking at what the computer is thinking on the New York Times page showed a really nice way to iterate on the complexity of our algorithm- their computer checks the last 4 moves, then the last 3, then 2, and finally 1. We could build up our algorithm up the other way- start by checking single moves and then moving on from that. 

Refining the Acceptance  Criteria

Ok, let's think. We need to change our acceptance criteria so it is obvious we are building complexity. We're also going to do a restructure to our acceptance criteria to move an action onto our when step, which we really ought to have done earlier. This gives us a good separation of arrange, act, assert in our test, which makes it easier to reason about.

Oh, another thought. If our Product Owner is on board, we can structure the increasing complexity as 'difficulty' for the Rock Paper Scissors game that our algorithm is going to be put in. An AI that only takes into account a single move is going to be easier to beat than an AI that takes into account two moves, and so on. We can use this to hide our implementation in the feature file by wrapping it up in 'difficulty levels', and we can work on 'beginner' first. So, what does this look like?

Looks good to me.  By introducing the concept of difficulty levels, we have managed to split the story into chunks that deliver increased complexity over time, rather than a lot of complexity at once. Even if the Product Owner doesn't go on to use the different levels, the benefit from building up the complexity over time outweighs the slight increase in development overhead it will take to write the code. We have also taken this opportunity to move the action of the acceptance criteria to the when step, giving us a better flow for our tests.

Implementing the Acceptance Criteria

So let's jump in to implementing the acceptance criteria. We'll start by writing out the step definitions for what we think we would like our API to be. We know we need to feed the algorithm the move history, and it needs to tell us what move it wants to use next.

Bit more to talk about for the step definitions this time, as I've structured the code a bit differently from when we did our Random Algorithm. This time we create our algorithm with a difficulty enum that we pass in from our feature file, so we can build on the difficulty levels without writing new step definitions.

We then go on to feed our algorithm a pre-generated history of moves played by our opponent, so it has some data to work from. This currently resides in a test helper class called Moves, which is effectively just a wrapper around a map of moves by difficulty on to a list of moves acting as the history.

We get this list of moves back from the helper class and feed them into the algorithm one by one- as it would do if we were playing the game for real (with our current understanding of the requirements).

Finally we ask our algorithm to generate the next move it wants to play, and check that this move is the move that we expect it to play based on the history.

Passing the Acceptance Criteria

Now comes the fun part- making our acceptance criteria tests pass.

This implementation passes our acceptance criteria... but it's not quite right. This is before any refactoring has taken place, so it is a bit of a mess- fair enough. But the main problem is that the algorithm is incomplete and still passes our acceptance criteria. Clearly something is wrong here- and the issue lies in our test cases- they all tested the same thing just with different moves, and our naive implementation has passed them all at the same time. Revising the test cases for moves results in tests like this:

That should cover all of our bases- the naive implementation no longer passes the acceptance criteria, so we have to actually check frequency to get our algorithm to work properly- which we can go on to do now.

Alrighty. I believe that is what is called "a big mess". Yep, definitely not the prettiest or most understandable code ever written- and certainly not the most efficient. The important thing is if the algorithm is correct or not- it passes all of our acceptance criteria, which is everything we know about the requirements currently. There was something that came up when I was testing different scenarios over what happens when it's a tie- we don't have any acceptance criteria for that scenario, so... let's leave that as an exercise for the reader, along with making the algorithm more readable, more efficient, and more maintainable. Don't forget, we still need to implement difficulty so we can build this up into a fully fledged Rock Paper Scissors winning machine!

Conclusion

So, that's that. All done, coding over. I am starting to get concerned that the TDD showcased here isn't so much Red Green Refactor as it is Red Green... That'll Do. Going to have to rein that in a bit going forward, especially if we're going to be building on previous work moving forward.

As always, you can check out the entire project on GitHub.

Stay tuned for part 4, where we build on this simple pattern recognition algorithm and turn it into something more.