Jon Thysell

Father. Engineer. Retro games. Ukuleles. Nerd.

Category: Software

Introducing the AtariController Arduino library

After releasing my Arduino library to read Sega Controllers, I decided it might be fun to create a suite of such libraries for reading other retro controllers.

So today I’m introducing my new AtariController Arduino library on GitHub. This initial release only supports the classic Atari 2600 joystick, but I hope to add other controllers in the future.

The code is provided as a proper Arduino library, making it easy for Arduino enthusiasts to use in their own sketches. As with SegaController, I also include two examples, one which reports the button states via the serial port (good for testing) and one which sends Keyboard key presses (good for driving other software).

And of course, I’ve created some documentation of my own in the AtariController wiki at How To Read Atari Controllers.

Enjoy and happy hacking!

/jon

Introducing the SegaController Arduino library

A couple years ago I tried my hand at building an interface for reading Sega Genesis / Mega Drive controllers with an Arduino. I documented my first attempt with Reading Sega Genesis controllers with Arduino, and my updated version with Sega Genesis controllers and Arduino revisited.

That was three years ago, and I’ve gotten a lot of feedback about those projects. While they worked well enough for me, many people had problems getting my code to work. My research had led me to an implementation that relied heavily on having correct timing delays, and others found they had to constantly tweak those timings.

Of course, as any decent programmer will tell you, if your code relies on a bunch of seemingly random sleeps to work properly, you’re probably doing it wrong. And it turns out I was.

I recently found the Six Button Controller page on SegaRetro, where I gleaned some new vital pieces of information:

  1. The controller must be cycled through 8 different states.
  2. Reading the controller involves knowing the current state.
  3. If the state isn’t changed for 1.5 ms, the controller resets.

Using this information, I decided to take another crack at my Arduino code. And with a little bit of work (not all of the information on the SegaRetro page was accurate) I created a much more deterministic, stable, delay-free program. Taking it a step further, I refactored the code into a proper Arduino library, both to learn how to do that, and to make it much easier for Arduino enthusiasts to use in their own sketches.

So if you’re interested in reading Sega controllers in your Arduino projects, check out my new SegaController Arduino library on GitHub. Replacing the original sketches are two new examples, one which reports the button states via the serial port (good for testing) and one which sends Keyboard key presses (good for driving other software).

Also, since my research into how the controllers worked led me to mixed results (no one’s documentation had it 100% right) I’ve created some documentation on my own in the SegaController wiki at How To Read Sega Controllers.

Enjoy and happy hacking!

/jon

Chordious 2.0 is here

It’s been two years since I started work on Chordious 2.0, and today is the first official release.

Read more about it in the announcement blog post.

/jon

Creating an AI to play Hive with Mzinga, Part IV

Mzinga is my attempt at an open-source AI for the board game Hive. So far in this series of posts, I’ve given an overview of the project, a dive into Mzinga’s AI, and then a deeper dive into Mzinga’s board evaluation function. All together, I have quite the framework for executinga decent Hive AI, but the question remains: How do I make it better?

How do people get better at games? Study and competition. Trial and error. Strategies that win us games are remembered and repeated while plays that lose us games are remembered so that we don’t repeat them. But in a game with so many things to consider, where there is no “right” move each turn, you can’t just memorize the answer, you have to actually play.

What are the things to consider? The metrics I talked about in the last post, like how many moves are available and what pieces are surrounded or pinned. Mzinga looks at some ~90 different metrics. For each there is a corresponding weight, measuring how much each metric should impact the board’s score.

How an AI plays is largely determined by what their metric weights are. AIs with different weights will make different decisions on which move to play. Creating the best AI then, is an exercise in determining the best metric weights. Since we don’t know what are the best numbers, our best option is to:

  1. Create a bunch of AIs with different metric weights
  2. Have them play a ton of games against one another
  3. Pick the one that proves that it’s the best

To pick the best one, I need a way of rating each AI. So I followed in chess’s footsteps and adopted the Elo rating system. It does a few of things I like:

  1. Each player has only one number to keep track of, so it’s easy to see who’s the “best”
  2. A player’s rating is just an estimate of how strong the player is:
    1. It goes up and down as they win and lose and their rating is recalculated
    2. Points are taken form the loser and given to the winner, so there’s a finite amount of “rating points” to go around
    3. More games mean a more accurate estimate of their strength, so no one game can make or break a player’s rating
  3. When recalculated a player’s rating takes into consideration who was playing:
    1. A good player beating a bad player is not news, so the winner only takes a few points from the loser, ie. player’s can’t easily inflate their ratings by beating awful players
    2. A bad player beating a good player is an upset, so to reflect that the ratings were wrongly estimated, the winner get lots of points from the loser
    3. Two players with similar scores are expected to draw, so if one wins, it’s a medium amount of points transferred to separate their ratings a little more accurately

Now the Elo system isn’t perfect. The biggest being that it only shows the relative strength of the players involved – you need lots and lots of players participating for the ratings to mean anything. There are lots of criticisms and variants when talking about real people playing, but it’s fine for what we need it for.

So now we have a method for finding the best player in a population of AIs. Create a bunch of AIs, have them fight one another to improve the accuracy of their Elo rating, and pick the one with the highest rating. But like I said earlier, Elo ratings only show relative strength in a given population. What if I don’t have a good population? What if 99% of them are so awful that an AI with some basic strategy completely dominates? That’s no guarantee that the winning AI is actually all that good.

How do we improve a population of players so that we can be sure that we’re getting the best of the best?

It turns out we’re surrounded by an excellent model on how to make a population of something better and better: natural selection and evolution.

In the real world, living things need to fight to survive. The creatures that can’t compete die off, while those with the best traits survive long enough to pass on their traits to their offspring. Offspring inherit both a mix of their parents’ traits, but they’re more then the sum of their parts. New DNA comes into the population as new members join or mutations occur.

We can absolutely simulate evolution in our population of AIs. The life-cycle goes something like this:

  1. Create a bunch of different AIs with different weights (traits)
  2. Have them all fight each other to sort out a ranking of who’s the strongest
  3. Kill off the weakest AIs
  4. Have some of the remaining AIs mate and produce new AIs to join the population
  5. Repeat 1-4

Now the first three steps seem pretty straight forward, but AI mating? It’s actually not that hard to implement. For each metric weight, simply give the offspring the average value from each parent. To make sure that AI’s children aren’t all identical, add a little variance, or mutation, by tweaking the result a little bit.

For example, if parent A has a particular weight of 5, and parent B a weight of 3, rather than giving every child the weight of 4, give them each something random between 3.9 and 4.1. Just like in real life, we don’t necessarily know which traits were the most important in making sure that the parent survived, and we don’t get to pick which traits get passed on. So we pass on everything, good and bad, and let life (in this case lots of fighting) determine who’s better overall.

Now we can start a new generation and have them all start fighting again, so we can suss out everyone’s rankings in the presence of these (presumably better) offspring. Add in some new AIs every now and then to prevent too much inbreeding (where one AI’s traits, good and bad, start to dominate and everyone starts looking more and more like clones of one another) and we now have a true population of AIs, all fighting to be the best.

Now, how exactly am I doing all of this?

With the Mzinga Trainer.

It’s a simple, yet highly configurable little tool for creating, maintaining, and evolving a population of AIs. I started with several seeds of simple AI weights that I handcrafted, plus a slew of randomly generated ones. Then I set up different populations on different computers with different parameters, and have them fighting, dying, and mating with each other for over a week.

It has made Mzinga into one of my more interesting projects, as I’ve made improvements to the tool, I’ve spun up new populations, mixed existing ones, and run life-cycles with different parameters. Some run under really harsh conditions, where so many get killed that the re-population comes from the offspring of very few survivors. When I started noticing that one small population had become so inbred as to appear like a clones of one another, I added in some new blood, so to speak. Then I reduced the harshness to give different AIs, and ultimately different play styles and strategies, a chance to survive and procreate without getting mercilessly killed off.

It’s an ongoing process, and like life itself, something that takes a lot of time to happen.

The Mzinga Trainer tool is included with the install of Mzinga. Now, not only can you try your hand against the Mzinga AI I’ve created, but you can even try to make a better AI of your own. So come on and try out Mzinga today!

/jon

Creating an AI to play Hive with Mzinga, Part III

In the first post in this series, I introduced Mzinga, my attempt at an open-source AI for the board game Hive. Then in my last post, I gave a high-level overview of how the Mzinga AI works. Now I’d like to discuss Mzinga’s board evaluation function, which is at the core of the Mzinga AI.

As I said in the last post, the purpose of the board evaluation function is to determine, based on the current state of the board, which player is “ahead” in the game. The function returns a number from negative infinity to positive infinity, where negative infinity means the current player has lost, and positive infinity means the current player has won.

The first thing that needs to happen, is I need to collect some information about the state of the board. So I go through the board and calculate a variety of metrics – that is to say – I count a bunch of situations. For example, for each piece on the board, I count how many moves it can make, how many neighbors it has touching it, and flag  whether or not it’s “pinned” (can’t move because other pieces won’t allow it).

I also add those numbers up for each player – how many pieces does the player have in play vs. still in their hand, how many pieces do they have that are pinned, and how many total moves they have available.

I do all of this for both players, and it takes a while, relatively speaking. In chess you have the benefit of a set board size, and despite the enormous number of positions that the board could be in, it’s still in a square grid, which can benefit from some fancy programming (see Bitboards) to make it computer friendly and faster.

Hive, on the other hand, is played on a potentially infinite grid of hexes. A typical chess board might determine there are 25 valid moves for a player – in Hive I’ve seen upwards of 150.

Anyway, once I have calculated a board’s metrics, the next step is to determine what they mean. So I know Black has more pieces pinned than White, but White’s Queen Bee is starting to get surrounded, who is ahead? Black still has more pieces to play, but White has a Beetle working its way toward a key spot, who is ahead? How do I evaluate all of the different situations against each other?

The answer is to use a weighted score. Basically, I take each of the metrics and multiply the number by its matching weight. The weight can be any number, positive or negative, but every metric has it’s own matching weight, with bigger weights meaning that the matching metric has more impact on the final score.

So for example, if I think that having more available moves each turn is better for a player, then for the metric Player.ValidMoveCount, I might give a high positive value to Player.ValidMoveWeight. Since the object of the game is to surround the opponent’s Queen Bee, for the Opponent.QueenBee.NeighborCount metric I might also set the corresponding Opponent.QueenBee.NeighborWeight very high. And since I don’t want to leave my Queen Bee unprotected, for my own Player.QueenBee.NeighborCount metric, I would want to give a negative value to Player.QueenBee.NeighborWeight

My board evaluation function simply adds all of these products (metric x metric weight) together to get the board’s final score. With this kind of generic function, the question now becomes: What are the weights that make up the best AI player? The more accurately the board score actually describes how far ahead or behind a player is, the better the AI has a chance of making moves that keep it ahead until it wins.

So, what are the best weights? I don’t know. No one does. Even in a game like chess, with centuries of study, where players have a much better grasp of what pieces are the most important, and what positions are better than others, there’s still no perfect, definitive answer. Great sophisticated starting points, sure, not but not perfect.

Now for a young game like Hive, the starting point may be as simple as the “surround the enemy queen but also keep your queen from getting surrounded” with some simple guesses for those weights, and ignoring everything else on the board. And in fact, that’s where the Mzinga AI is at today. Smart enough to actually play the game toward winning, and much better than just randomly picking moves.

So how do we make it better? How do we get better weights?

Here is where the “real” fun begins, and that’s a topic for the next post. So stay tuned for Part IV, where I go more into detail about how I’m trying to improve the metric weights.

Try out Mzinga today!

/jon