Wednesday, 23 September 2015

Rock Paper Scissors AI | Random Algorithm

Introduction

Hello and welcome to part two 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 first AI strategy we are going to be implementing is a random algorithm. This will be pseudo-random rather than truly random, but for a Rock Paper Scissors game, this doesn’t really matter. This algorithm will choose between playing rock, paper, or scissors at a roughly equivalent frequency. 

The idea behind designing a pseudo-random algorithm for our AI to begin with is two-fold. For starters, it’s one of the easiest algorithms to grasp- all we are going to do is select a random move to play. Secondly, it is theoretically impossible to beat an opponent that selects their moves randomly- the best scenario being a draw. This gives us a good fallback in case our newer algorithms do not perform very well. 

Formulating the Requirements

We already have a fairly intuitive grasp of what we need our random algorithm to do. We've formulated our basic requirements in the introduction above- that the algorithm needs to choose to play rock, paper, or scissors seemingly randomly. 

Formulating the Acceptance Criteria

Fair enough, but those requirements aren't particularly friendly for us to work with and know when we're finished. As stated in the introduction, we are going to use the Gherkin language to articulate our acceptance criteria of our requirements, so we can more easily know when we have met them correctly. 

Ok so the first scenario... fair enough. If we run it enough times, we should get all of the possible moves out. I can't imagine producing 100 moves and not getting paper at least once. In fact, if we didn't, there's probably something wrong with our algorithm. Or we've got really, really unlucky.

The second scenario makes sense from a business perspective- we want to make sure that our algorithm plays random moves, and if it is playing randomly then there should be a fairly even distribution of moves. However, a random algorithm is not always going to produce an even distribution of moves, which will cause our tests to randomly fail in turn. Randomly failing tests are the bane of any automated acceptance tests, so much so that they aren't worth having around. But what would the problems actually be?

Running a couple of quick simulations of what our test might be shows that when generating a random number between 1 and 3 in 1000 iterations, the number of times a particular number comes out can vary from between 280 to 380. Increasing the number of iterations to 1,000,000 gives us better numbers of between 331,000 and 335,000- but that test takes longer to run and doesn't necessarily guarantee we won't see random failures.

Refining the Acceptance Criteria

Like we said before, a test that fails for a reason other than the code being broken isn't a test worth having, so we're going to have to do something about the acceptance criteria to make them more palatable for testing.

What we've done here is up the number of iterations to the first acceptance criteria to 1000, as this adds very little overhead to our test and makes it a lot more likely to pass every time we run it.

We ran some simulations of what kind of tests we could write for the second acceptance criteria, and all of them failed at random. This led us to decide not to automate that set of acceptance criteria. That's not to say it's not important, just that we can't really write an automated test for it.

Implementing the Acceptance Criteria

So, let's get started with making those acceptance criteria executable. We are going to be using Cucumber to write and run our acceptance tests. Fortunately, we have already formulated our acceptance criteria in Gherkin format, so all we need to do is put it into a .feature file that Cucumber will understand, and write the implementation of the steps in Java code behind it. You can see this work completed below.

Very simple implementation of the requirements. We create our RandomAlgorithm, call it's generateMove() method 1000 times and add the results to a list, and make sure that all of the moves we pass in are contained within that list using the AssertJ library.

Passing the Acceptance Criteria

Now we need to make the tests pass, taking care to make sure that we also fulfil the Product Owner's requirements that we haven't captured in automated tests. We already have our Java class and it's API defined by our test- so now we just need to test drive the actual behaviour of our class out using TDD.

This implementation has passed our acceptance criteria- so we know it will produce all of the moves when run enough times. We have delegated the responsibility of ensuring the moves produced are random to the Random class in the Java language, which we are passing in to the constructor so we can change it in the future if we need to. Ideally we would wrap up the Random class in our own interface so we can change it more easily in the future and follow the Open Closed Principle more closely, but that is outside the scope of this post.

Conclusion

So, that's it. We've started with a general idea of what we want, fleshed it out into our acceptance criteria and looked at the implications of that, moulded it to make it executable and automated, and finally implemented the code, safe in the knowledge that they meet our requirements.

You can check out the entire project on GitHub.

Stay tuned for part 3, where we try to actually implement some strategy for our AI. 

Thursday, 17 September 2015

Rock Paper Scissors AI | Introduction

Welcome to part one of our series on AI strategies for the classic game of Rock Paper Scissors.

Part one is an introduction to the parts that will follow, laying out what content to expect and the layout of that content. It is also a nice placeholder to link to from the Rock Paper Scissors kata from where people can select the areas they are most interested in. 

Structure

We will present the algorithms in the following structure:
  •  High level description of the algorithm we will be employing.
  •  Gherkin format acceptance criteria describing the behaviour of the algorithm.
  •  Java implementation of algorithm that meets the acceptance criteria.

Other posts in this series


Wednesday, 2 September 2015

Connect Four Kata Run Through in Java | Part One

Hello and welcome to the first kata run through on the Agile Katas blog! In this post, I will be running through or performing the first story in the Connect Four Kata, using Java as my programming language of choice. If you want to follow along with the kata, you can find it over at Agile Katas Connect Four Kata.

Getting Started

First things first- I am using my project template that I use for all katas that I perform- this is a simple basic gradle project with a few choice dependencies included- namely Cucumber-Java, AssertJ, and JUnit. I don't tend to use anything else for simple katas, but may include other dependencies depending on the story and functionality I am working on. I am also using IntelliJ IDEA as my IDE of choice. 

The First Story

Because we are using BDD, our first test is the acceptance criteria of our first story. We create a feature file that includes this information, and we have some executable documentation so we know when our task is finished. For Connect Four, this will look something like this:

The Stepdefs that go along with this feature file will look like this to begin with:

The implementation of these Stepdefs will change considerably depending on how you decide to tackle the problem. You may want to do a little bit of upfront design at this point, choosing what solution you want to use from analysing the requirements at present and possibly in the future, or by what you want to practice with. I have decided to go with an approach that utilises a single class to begin with- the Grid. This means my filled-in Stepdefs file looks like the following:

The Grid class doesn't contain anything except a (possibly definitely fluid) API at this moment, and it looks like this:

Usually this is where I would start to really test drive the code out using TDD, but I'm going to try something new this time and only use the BDD to ensure the behaviour is as expected. The idea is that if you work entirely from the BDD, any changes you make to the implementation of the feature shouldn't cause the tests to break, maybe them less fragile and brittle. This should work for simple classes and simple cases, so this Connect Four kata should be a good test of how well it does here- and if we decide to scale the kata up into a bigger project, we'll be able to see how well pure behaviour driven development scales.

After a very quick implementation, I end up with the following Grid class:

This implementation isn't the best code- it's quick and dirty but it gets the job done. Part of this is because our first instinct should be to get the tests to go green- once we have met the behaviour we have delivered the value for our customer in the short-term, and have something that we can deliver now and improve upon later. This is easier to do when the quick and dirty work only takes 5 minutes like it did here. The other reason is because I have a fairly strong feeling that the user story we just implemented didn't have all of the information we needed for our real solution- so getting it to pass and moving on before trying to refactor it nicely is a good idea- the implementation is probably (definitely) going to change in the next story.

Conclusion

And that's effectively it for the first story. At this point we can go back and refactor any of the code that we're not happy with, safe in the knowledge that any changes we make are covered by our acceptance criteria tests- and as long as they stay green, we know our product owner will still be happy with the behaviour. I won't be performing any refactoring at this point, as I have a sneaky suspicion that this implementation won't stand up to future requirements, and refactoring effect will be better spent after implementing those. 

Stay tuned for part two, where we implement the second story and give the first lot of code a much-needed refactor.