Category Archives: Tech

Building an AI (part 1)

Posted on by

Hi again,

After being in hiatus for quite some time I’ve gotten back to programming a bit. I guess there is an ebb and flow with everything.

Back in November I was looking into how I could be Building an AI with ASyncTask, but I never got to feed the thing some rules with regards to how to play the game. This I aim to remedy now. Since this could get pretty lengthy I’m planning a short series as I go though the process of building an AI for the dice game “10.000”.

 

Choosing a method for problem solving

Building an AI can be done in different ways. I haven’t explored the topic that much, but I could see going about problem solving in different ways; neural networks or some other kinds of fuzzy logic, search algorithms or a basic heuristic. I do however have some programming experience with heuristics and I believe that, since we’re talking about a limited problem space like this a heuristic can do the job just fine.

One of the issues at hand is whether or not we want to get the optimal solution i.e. winning as fast as possible. I can see an argument for building an AI that can do this, but I don’t think it would be very fun to play against. The probability built into the game somewhat remedies this, but the AI should strike a balance between being challenging to play against and still being beatable. Another plus for using a heuristic is that they can be made to give us an answer in short time consistently, thus giving the user a better experience.

 

A basic set of rules

When implementing the heuristic I need to come up with some rules that it will consist of. In principle I want the AI mimics the process of a human player asking himself a set of questions at every decision point during his turn and answering them based on a predefined logic (as humans we have the advantage of being able to adjust our evaluation during a game, whereas my AI will have a fixed set of rules).

Questions you could be asking yourself?

  • What is the probability of being able to make points with X dices?
  • What is the reward for rolling the dices?
  • What is the risk for rolling the dices?
  • Is it the last round and do I have the most points?

Joining these together my heuristic becomes:

Rule A) If my chance of success times the reward for rolling the dices is bigger than the chance of failure times the risk, then roll the dice. Otherwise bank the points (if able)

Rule B) If it is the last round and I haven’t got the most points, then keep rolling.

 

What remains to be done?

For now I’ve established a basic set of rules. To determine whether or not the AI should keep rolling I need to feed some numbers into rule A. These numbers I’ll try and calculate in my next post using statistical analysis.

 

That’s it for now 🙂

 

EDIT: To read part 2 go here.

Building an AI with ASyncTask

Posted on by

I’ve wanted to add an AI for the 10.000 game, since giving users a single player option seems like a necessity, if I want to retain them. I for one was getting a little bit tired of playing both sides, if I couldn’t find someone else to play against.

The game before implementing the AI
Up until now the game has been built around the assumption that only users generated input for the game. I didn’t really take any measures to incorporate alternative input methods that an AI could use.

Drawing the architecture of the app you’ll get:

UI –> Model

Needless to say I’ll put a little bit of thought into the architecture, before punching in any lines of code, since there’s no simple way to integrate it in the existing architecture. As the model stands now, it has a set of methods that you can use to manipulate it’s state with, giving me some flexibility.

Examples of this are:

public boolean canRoll()
public void performRoll()
public boolean performLock(int diceNo)

Caveat: Expanding the app with an AI
I could write an AI class, that could manipulate the model, using the available methods. However, if I did that;

  1. How would the AI know when to update and when not to?
  2. How would the UI know when to allow user input and when not to?

Using the Observer pattern (through the Java event model) enables me to publish events. With these events I can trigger the two classes and thus get them to do something, be it a calculation, a move etc. It doesn’t however limit them from performing actions, when any or every event is published. The Command pattern could probably be used in this regard, to give the model some uniform way of validating which actions are ok and which are not. That partly solves the problem, since it does not limit the AI would from performing a task and the UI would still enables user generated input.

The proposed changes so far
Updating the architecture with the AI gives me a diagram:

UI –> Model <– AI

It only states that the UI and AI should exist as separate objects and that they can independently make calls to the model. To ensure that only the allowed object can perform actions at a given time, the model needs to check who’s making the calls.

Caveat: Figuring out who invokes a method

The model could use Reflection to figure out who invoked a given method. Using Reflection does generate an overhead in resource consuption, compared to simpler solutions, and I’m not entirely convinced that it is secure. I base that assumption on this thread.

A simpler implementation would be to change all public method signatures to include a reference to the calling object as the first parameter. This must be filled out with a “this” reference, when any object tries to call a method, thus ensuring a check for legality of the performed call. The solution doesn’t gurantee a solution to the security issue 100%, since you could just pass a reference to another object, but I’ve decided there’s no need to bring out any bigger guns, when ther’s only a game of 10.000 at stake.

The aforementioned examples gets updated to:

public boolean canRoll(Object caller)
public boolean performRoll(Object caller)
public boolean performLock(Object caller, int diceNo)

Now we’re getting somewhere 🙂

Implementing the AI

Since the AI will be doing some computations and needs to be able to idle for a bit, so that the user the AI performed actions separately in the UI, it’s necessary to place this in a separate thread.

Caveat: AI and the UI thread
Implementing the AI (by extending the Thread class or implementing Runnable) doesn’t detach the AI from the UI. This means that when the AI goes into a wait state or does some computations, it’ll lock up the UI. This is a sure way of degrading the user experience and may even result in some ANRs. It should be obvious that you’ll want to avoid this.

The answer is using AsyncTask to detach the AI from the UI. The AsyncTask is part of Androids threading framework and solves the problem of locking your UI thread. An alternative could be using an IntentService, but with a litte careful programming I believe that an ASyncTask will solve my problem just fine.

One thing to be aware of though, is if your app gets reloaded, for instance if you rotate the screen, the AsyncTask will be killed. Program your solutions accordingly.

 

That pretty much wraps up my thoughts for how to expand the architecture in the 10.000 app. Be sure to check back for more information 🙂

Model building for 10.000

Posted on by

When I started working on the 10.000 game, I had some ideas and concepts I wanted to try out when building the model. I’d like to share some of my thoughts on the process and the product.

What is the objective of the model?
My goal with the model was to make a clear separation between the logic and state of the game and the user interface. The benefits I was hoping to achieve was first and foremost a division of the task at hand, by dividing the application into a user interface part and a model part. Secondly making it easier to swap UIs, by decoupling it from the model, in case I’d redesign the UI later on. Thirdly I wanted to encapsulate the variables that stored the state of the game, thereby making sure rules would be enforced and thus keeping the model in a valid state all the time.
A lot of this stems from the teachings and common programming practices like the MVC architectural pattern and I saw no reason why this solution couldn’t be applied to the task at hand.

What is the tradeoff?
All of these benefits comes at a cost of course. During the development of the game I kept track of how much time I spent on the different tasks. I’ve given a short list below of the time allocated to different tasks (this only covers the initial version).

  • Designing the solution: 24% (~16 hrs)
  • Graphics: 5% (~3 hrs)
  • Programming UI: 37% (~25 hrs)
  • Programming model: 28% (~19 hrs)
  • Testing and debugging: 4% (~2 hrs)
  • Publishing: 3% (2 hrs)

I can’t say for sure, but I guess that if I had merged the model and UI and didn’t care about the benefits that the seperation gives, I could probably have saved 10 hours divided evenly between designing and programming, which equates to something like a 15% reduction. This is of course my ad hoc estimate based on the size and complexity of the game and it’s rules. I don’t think you could use this as a generic rule 🙂

Encapsulation vs. performance
Another thing to consider is the fact that the encapsulation adds a layer of method calls that could be removed, if variables where directly accessed in the code. I read that internal getter/setter methods should be avoid, due to performance overhead. I’m guessing merging classes and then accessing variables directly would yield the same benefits.
I haven’t tried profiling the game, to see if there are any performance drops. The tests I’ve done on the UI haven’t had any issues so far, like an ANR for example.

What benefits did this give after release?
After the first release I’ve made some improvements to the game. These have been bundled in three new versions. All of these have been rather fast to develop and I contribute a lot of this to the initial investment in time spent on design and model programming. Again, if I where to venture a guess I’d say that the time I could have saved on the initial release I’ve gained in the latter releases.

So I think my bottom line is; Solid design and good programming practices saves time in the long run.
It has certainly saved me a lot of frustration 🙂

On the “Android Activity Lifecycle”

Posted on by

As I dig into the coding of the next app, I’ve inevitably run into the Android activity lifecycle. Initial thought: Wow, that’s nerdy 🙂

The lifecycle pyramid

The picture below shows the “lifecycle pyramid”. Simplified the app transitions through a series of different states, from left to right with the occasional backtracking. This of course depends on how the user interacts with it.

First impressions

What first struck me was the way the different states are reached and how chaotic it seems. Having read a little more from the Android Training classes, it quickly made a lot more sense to me. The app is started, it has a “running” state, it can be paused and eventually terminated.

In the above pyramid there are quite a few arrows between the different states, illustrating the method calls that are being made by the JVM, when each transition occurs. This got me thinking; “Why not try it out and see what and when everything is invoked?”. The guys at Google of course already thought of this and made an example of this, but I’m more of a hands-on guy sometimes.

onResume and onPause?

The lesson I’m trying pass on here is this; When you start up you activity a series of methods gets called per default (OnCreate, OnStart and OnResume) and then you’re good to go. What surprised me is at if you hit the menu button, gets interrupted by a call or even if you rotate the screen, your activity gets destroyed and rebuilt. Of course you can’t be totally sure that it gets destroy on every occations, but you should program as if it did.

You should therefore always save your state when your activity gets paused (onPause), ’cause it might get destroyed. When you return to your activity, you should restore the state in the onResume method. This way you ensure that nothing is lost if your activity loses focus or the screen gets rotated.