YALi: Technical stuff

As far as the sound and graphics go, there is nothing special about this applet. The marbles, holes and a few other things are imported, raytraced graphics, whereas the board is made with elementary fillPolygon and drawLine operations. This looks good without requiring much download time.

The tricky part was coming up with the computer's artificial intelligence. I considered a few different approaches -- from a complete implementation of the MIN-MAX algorithm to figuring out the optimal strategy and programming the computer with that. But eventually I had to settle for some "reasonably smart" rules of thumb:

  • It's usually best to advance with one marble at a time, rather than bringing a whole group across the board. This gives your opponent fewer opportunities to jump over you and gives you access to the edge marbles sooner when playing according to the "basic rules."
  • You should move the edge marbles as soon as the opportunity arises.
  • Reaching the opposite side of the board is a good thing. (Obviously.)
  • Jump over your opponent when you can.
  • Finally, (though this applies mainly to the computer) steer your marbles towards empty holes at the opposite side.

When I evaluate a possible move accordingly, I use a system of points. The total is the sum of:

  • The distance from the start side to the marble's new position. This will favor advancing with a single marble.
  • A big bonus for reaching the opposite side.
  • A smaller bonus if any of the human player's marbles are jumped over.
  • A few points if the move takes the marble closer to, or directly in line with, an empty hole on the opposite side.

All legal moves are evaluated and the best one gets chosen. If more than one candidate gets the highest score, a random selection determines the winner. And every once in a while (roughly 25% of the time), the computer just makes a random legal move. This is to make things more interesting. But if an edge marble can be moved, the computer always does that first (and picks the one that can be moved the longest distance).

A limitation of this strategy is that the computer only thinks one step ahead. It will make the computer an adequate but not very skilled opponent when playing according to the "advanced rules." With the "basic rules," however, the computer will be able to beat most human players quite easily (as my client soon found out).

I know from experience that there are a lot of people on the web who tend to overestimate their intelligence. After unsuccesfully challenging the computer to a "basic rules" game a few times, they will draw the incorrect conclusion that it's impossible to win. Some will send me a more or less elaborate "proof" of why this is so and claim that the game is flawed. When I insist that the computer really can be defeated, and that I have done so on several occasions, they will call me a liar and send me abusive e-mail. This happened a couple of times for Car Jam / Autocrazy and is one of the downsides of being a Java games programmer.

The only remedy is to present a complete solution on the web, but since that would spoil the fun for everyone else, I hope the following will be acceptable:

Remember that the program can only think one step ahead. This means that it won't be able to make short-term sacrifices that pay off later in the game. There exists a few situations where you can exploit this and get a slight advantage that enables you to win. This screen snapshot (where I played the silver side) may provide you with some clues as to how it is done.