Tuesday, November 22, 2011

Creating a Basic Isometric Map

Last year Christian Weber wrote a helpful introductory article showing how to use CSS to layout tiles for an isometric map. However, the screen shot and demo looked a little odd; note the black V below where you can see "underneath" a tile.

The problems were partly caused by placing tiles adjacent to each other when they didn't have matching sides (i.e. a side that is all grass should butt up against an all grass side of another tile).  In addition, the CSS styles for the tiles had the wrong offsets for identifying the positions of the sprites.  The code in the article compensated for the style errors with some "corrections", which of course made it more confusing.

I've posted a corrected version here.  It has a table indicating the type of each tile side, allowing for the generation of a random map were each tile's neighbors are appropriate, such that there are no gaps.  For example:

Sunday, May 8, 2011

Writing a Windows Service in Java


I've got a couple of Java programs that I want to leave running permanently on my laptop, so I set about creating a Windows Service. I investigated several of the alternatives (Java Service Wrapper, Yet Another Java Service Wrapper, etc.), but having recently discovered Java Native Access (JNA), I decided to see if I could produce a fairly lightweight solution.

JNA (and libffi on which it depends) provides a means to dynamically create a bridge between Java and native libraries, a feature I've been wanting for years. I'd used JNI in the past, but I find it rather brittle. I've been pleasantly surprised to find that even when I made various mistakes with JNA, the JVM didn't crash; instead, JNA threw relatively meaningful exceptions, such as when it was unable to bridge the gap between a call from Windows to a Java method I wrote to accept that call (i.e. the argument types I used weren't appropriate). For example, the Windows Service API requires the service to implement a ServiceMain function which will be called by Windows:
VOID WINAPI ServiceMain(
  __in DWORD dwArgc,
  __in LPTSTR *lpszArgv
);
That lpszArgv is a pointer to an array of pointers to strings that will be passed to the ServiceMain function. I wanted to define a type, ReceiveStringArray, extending Pointer, as the type of lpszArgv in Java. Unfortunately, JNA could not bridge the gap from the native arguments to ReceiveStringArray, so I had to fallback to using JNA's Pointer as its type, and fortunately Pointer has a method, getStringArray, that handles exactly the translation needed here.
interface SERVICE_MAIN_FUNCTION extends StdCallCallback {
  /**
   * ServiceMain is the main method of the service. It should return only
   * once the service is stopped.
   * 
   * @param dwArgc
   * @param argv A pointer to an array (of length dwArgc)
   *             of pointers to strings.
   */
  void ServiceMain(int dwArgc, Pointer argv);
}
It may be that I was missing some appropriate constructor in ReceiveStringArray, or that a JNA TypeMapper was needed to handle initializing a ReceiveStringArray in this situation.

Another interesting challenge I had was that the first of my callback functions, ServiceMain, was being called at the expected time, but it was also being called when I expected a different callback function to be called instead. I'm not certain, but I think this is because JNA doesn't really care about the name of the method in the interface; there must be a single method, and that is the one that will be called. I had created two interfaces, but only a single class implementing them both. I suspected that I needed to have a separate class (or instance?) to receive each type of callback.

StartServiceCtrlDispatcher
A typical Windows Service is basically just a program that runs in the background, with no direct interaction with the user, with a few extra required interactions with Windows. When the program is started it must call StartServiceCtrlDispatcher, passing in a table of services to be started (typically just one). The dispatcher starts another thread to run ServiceMain, then it dispatches various Windows events to the service (e.g. when Windows is shutting down), and returns once the service stops.
import com.sun.jna.Native;
import com.sun.jna.Structure;
import com.sun.jna.platform.win32.Advapi32;
import com.sun.jna.win32.W32APIOptions;

public interface ExtendedAdvapi32 extends Advapi32 {
  ExtendedAdvapi32 INSTANCE = (ExtendedAdvapi32) Native.loadLibrary(
      "Advapi32", ExtendedAdvapi32.class, W32APIOptions.UNICODE_OPTIONS);
  class SERVICE_TABLE_ENTRY extends Structure {
    public String serviceName;
    public SERVICE_MAIN_FUNCTION serviceProc;
  }
  boolean StartServiceCtrlDispatcher(SERVICE_TABLE_ENTRY[] lpServiceTable);
}
The API doesn't include a length parameter to tell the dispatcher how many services are implemented by the program. Instead, the last entry in the table must have NULL pointers. Therefore, while the program doesn't need (at this point) the name of the service it is implementing, the field must not be NULL. Instead, set it to an empty string. For example:
ExtendedAdvapi32.SERVICE_TABLE_ENTRY entry =
    new ExtendedAdvapi32.SERVICE_TABLE_ENTRY();
entry.serviceName = "";
entry.serviceProc = someServiceMainFunction;
ExtendedAdvapi32.SERVICE_TABLE_ENTRY[] serviceTable =
    (SERVICE_TABLE_ENTRY[]) entry.toArray(2);
boolean result =
    ExtendedAdvapi32.INSTANCE.StartServiceCtrlDispatcher(serviceTable);

ServiceMain
The ServiceMain callback function is invoked on another thread from the main thread, and shouldn't return until the service stops (usually when Windows is shutting down, but it can also be stopped and started via a control panel). The function is passed an array of strings (as an argc and argv, just like a C program's main). The first string in the array is the name of the service. The following elements of the array are the "Start Parameters". These can be set in the service's Properties dialog box:
ServiceMain needs to call RegisterServiceCtrlHandlerEx to provide the service control dispatcher with a function to be invoked when Windows notifies the service of events (e.g. when Windows is shutting down, a user logs in or out, or there is a change in connected hardware).
public interface ExtendedAdvapi32 extends Advapi32 {
  interface HandlerEx extends StdCallCallback {
    int serviceControlHandler(int serviceControlCode, int eventType,
                              Pointer eventData, Pointer context);
  }
  class SERVICE_STATUS_HANDLE extends HANDLE {
    public SERVICE_STATUS_HANDLE() { }
    public SERVICE_STATUS_HANDLE(Pointer p) { super(p); }
  }
  SERVICE_STATUS_HANDLE RegisterServiceCtrlHandlerEx(
      String serviceName, HandlerEx handler, Object context);
}
Next, ServiceMain must call SetServiceStatus to inform Windows that the service running, and the types of event notifications the service wants to receive.
public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_WIN32_OWN_PROCESS = 0x00000010;
  class SERVICE_STATUS extends Structure {
    public int serviceType = SERVICE_WIN32_OWN_PROCESS;
    public int currentState = 0;
    public int controlsAccepted = 0;
    public int win32ExitCode = W32Errors.NO_ERROR;
    public int serviceSpecificExitCode = 0;
    public int checkPoint = 0;
    public int waitHint = 0;
  }
  boolean SetServiceStatus(SERVICE_STATUS_HANDLE serviceStatusHandle,
                           SERVICE_STATUS serviceStatus);
}
For example:
public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_RUNNING = 0x00000004;
  static final int SERVICE_ACCEPT_SHUTDOWN = 0x00000004;
  static final int SERVICE_ACCEPT_STOP = 0x00000001;
}

SERVICE_STATUS serviceStatus = new SERVICE_STATUS();
serviceStatus.currentState = ExtendedAdvapi32.SERVICE_RUNNING;
serviceStatus.controlsAccepted = (
    ExtendedAdvapi32.SERVICE_ACCEPT_STOP |
    ExtendedAdvapi32.SERVICE_ACCEPT_SHUTDOWN);
ExtendedAdvapi32.INSTANCE.SetServiceStatus(serviceStatusHandle,
                                           serviceStatus);
At this point the service can do its job, but it must also have some way to be notified that it is time to stop (e.g. via a flag shared between the ServiceMain thread and the service control handler). When ServiceMain learns that it needs to stop, it must tell Windows that it has stopped before returning.
public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_STOPPED = 0x00000001;
}

SERVICE_STATUS serviceStatus = new SERVICE_STATUS();
serviceStatus.currentState = ExtendedAdvapi32.SERVICE_STOPPED;
serviceStatus.controlsAccepted = 0; // Accept no more notifications.
ExtendedAdvapi32.INSTANCE.SetServiceStatus(serviceStatusHandle,
                                           serviceStatus);

Service Control Handler (HandlerEx)
The service control dispatcher calls the service's control handler when the requested events occur. To support just shutdown and stop events, this suffices:
public interface ExtendedAdvapi32 extends Advapi32 {
  static final int SERVICE_CONTROL_SHUTDOWN = 0x00000005;
  static final int SERVICE_CONTROL_STOP = 0x00000001;

  // Must return NO_ERROR for this, not ERROR_CALL_NOT_IMPLEMENTED.
  static final int SERVICE_CONTROL_INTERROGATE = 0x00000004;    
}

public int serviceControlHandler(int serviceControlCode, int eventType,
                                   Pointer eventData, Pointer context) {
  switch (serviceControlCode) {
  case ExtendedAdvapi32.SERVICE_CONTROL_INTERROGATE:
    return W32Errors.NO_ERROR;
  case ExtendedAdvapi32.SERVICE_CONTROL_SHUTDOWN:
  case ExtendedAdvapi32.SERVICE_CONTROL_STOP:
    // TODO Signal ServiceMain to stop.
    return W32Errors.NO_ERROR;
  default:
    return W32Errors.ERROR_CALL_NOT_IMPLEMENTED;
  }
}

Encapsulating the Windows API
To avoid polluting the 'pure' Java with all of the above, I defined the following simple interface that my services would implement (which I can use on other operating systems):
public interface ISimpleService {
  int run(String[] args);
  void stop();
}
The return value from run could (in a slightly more complicated solution) be used to set the SERVICE_STATUS.serviceSpecificExitCode field.

These two classes are used to invoke the methods of ISimpleService:
class ServiceControlHandler implements HandlerEx {
  private final ISimpleService service;
  public ServiceControlHandler(ISimpleService service) {
    this.service = service;
  }
  public int serviceControlHandler(int serviceControlCode, int eventType,
                                   Pointer eventData, Pointer context) {
    switch (serviceControlCode) {
    case ExtendedAdvapi32.SERVICE_CONTROL_INTERROGATE:
      return W32Errors.NO_ERROR;
    case ExtendedAdvapi32.SERVICE_CONTROL_STOP:
      service.stop();
      return W32Errors.NO_ERROR;
    default:
      return W32Errors.ERROR_CALL_NOT_IMPLEMENTED;
    }
  }
}

class SimpleServiceMain implements SERVICE_MAIN_FUNCTION {
  private final ISimpleService simpleService;
  private final SimpleServiceControlHandler handler;
  private SERVICE_STATUS_HANDLE serviceStatusHandle;
  public SimpleServiceMain(ISimpleService simpleService,
                           SimpleServiceControlHandler handler) {
    this.simpleService = simpleService;
    this.handler = handler;
  }
  public void ServiceMain(int argc, Pointer argv) {
    if (argc < 1 || argv == null) {
      // Missing the service name.
      return;
    }
    try {
      String[] args = argv.getStringArray(0, argc, true);
      String serviceName = args[0];
      String[] startParameters = Arrays.copyOfRange(args, 1, args.length);
      serviceStatusHandle =
          ExtendedAdvapi32.INSTANCE.RegisterServiceCtrlHandlerEx(
              serviceName, handler, null);
      setServiceStatus(ExtendedAdvapi32.SERVICE_RUNNING,
          ExtendedAdvapi32.SERVICE_ACCEPT_STOP |
          ExtendedAdvapi32.SERVICE_ACCEPT_SHUTDOWN);
      simpleService.run(startParameters);
    } finally {
      setServiceStatus(ExtendedAdvapi32.SERVICE_STOPPED, 0);
    }
  }
  private void setServiceStatus(int currentState, int controlsAccepted) {
    SERVICE_STATUS serviceStatus = new SERVICE_STATUS();
    serviceStatus.currentState = currentState;
    serviceStatus.controlsAccepted = controlsAccepted;
    ExtendedAdvapi32.INSTANCE.SetServiceStatus(
        serviceStatusHandle, serviceStatus);
  }
}
And a function to create instances and start the service control dispatcher:
public static void runSimpleService(ISimpleService service) {
  SimpleServiceControlHandler handler =
      new SimpleServiceControlHandler(service);
  SimpleServiceMain serviceMain =
      new SimpleServiceMain(service, handler);
  SERVICE_TABLE_ENTRY entry = new SERVICE_TABLE_ENTRY();
  entry.serviceName = "";
  entry.serviceProc = serviceMain;
  SERVICE_TABLE_ENTRY[] serviceTable =
      (SERVICE_TABLE_ENTRY[]) entry.toArray(2);
  ExtendedAdvapi32.INSTANCE.StartServiceCtrlDispatcher(serviceTable);
}

Example Service
Here is a trivial service that just waits to be stopped.
public class WindowsServiceHandlerExample implements ISimpleService {
  private final CountDownLatch latch = new CountDownLatch(1);
  public int run(String[] args) {
    try {
      latch.await();
    } catch (InterruptedException e) {
    }
    return 0;
  }
  public void stop() {
    latch.countDown();
  }
  public static void main(String[] args) {
    WindowsServiceUtil.runSimpleService(new WindowsServiceHandlerExample());
  }
}

Saturday, February 26, 2011

Distributing Work

During November and December of last year I developed my checkers program to the point where I could run all three of the experiments conducted by Fogel and Chellapilla.  The longest ran for 5 days on my 2 processor laptop, which indicates that it'll take months to run some of the experiments I have in mind.

Since I'm doing this exercise for fun, and I like building "systems", I decided to make a system for distributing work (games to be played) to other machines in the house.  I've developed a somewhat complicated Java web app (using embedded Jetty) that manages a jar repository and runs (in subprocesses) Java programs whose descriptions are uploaded.  The description consists of jar names and jar hashes (to avoid running the wrong version of a jar as I'm developing), a main class name, and command line.  The Java program is provided with a work area in the file system, to which the remote client can upload any necessary files prior to starting the program, and from which the remote client can download any files after the program is done, including files containing the output of the stdout and stderr streams.

I say "somewhat complicated" because I didn't make the decision to use embedded Jetty until late in the process, and if I'd made it earlier, I would have used more of Jetty's facilities to handle the file management.

To simplify creating the description of a Java program, I created a mechanism for walking the current process's classpath, creating jars for unpacked entries (e.g. the bin folders of my Eclipse projects), and uploading them to the various servers.

Next up I'm working on how to transfer units of work from the main program to the workers, and how to get the responses back.  My current plan is to have the main program run an embedded web server (Jetty) with a servlet that a worker will contact to get a unit of work (e.g. two checkers players to compete), and will then re-contact with the result of the unit of work (e.g. the game outcome).

This mechanism is certainly sufficient to the task, but feels a bit awkward.  I think I'd like some variant of a ThreadPoolExecutor that supports distributed threads, but I've not located nor invented such a beast.  Sigh.

More later.

Wednesday, December 29, 2010

Yes, Virginia, Testing is Important!

In my zeal to optimize my checkers playing program, I included a number of optimizations in the search algorithm: minimax with alpha-beta pruning, plus a memory of previous partial search trees to assist in ordering of future searches, and to skip evaluations when the results are known.  Too many optimizations, as it happens.

I wrote quite a few JUnit tests for the basic checkers board manipulation code, but wasn't sure how to go about testing the search algorithm. I wrote some very basic tests that the pruning was happening as expected, but left it at that.

I then wrote a system for evolving the neural networks, and repeated the evolution experiments described by Fogel and Chellapilla. Again, I wasn't quite sure how to evaluate the results, as I'm not yet ready to play hundreds of games online using the best evolved network as my evaluation function.

So, I studied the last generation's networks and the games they played, and noticed that they'd all played the same first move... and the same first reply... and the same next reply! The first three moves were all the same.  Wow! Did they all stumble upon the best opening moves?  Or perhaps all of the surviving networks were descended from a relatively recent network that made that choice?

I decided to confirm that initial generation of networks was much more random in its play.  Unfortunately, upon reviewing their games, I found they too played the same first three moves.  Sigh.  Back to the drawing board.

To track this down, I tried shuffling the legal move choices presented to the search algorithm, but that made no difference.  Next, I implemented minimax and compared its choices to those of my enhanced alpha-beta search. As you might expect, they didn't agree.  So, I implemented a basic alpha-beta search, which did agree with minimax.  In the course of debugging, I found several mistakes in the over optimized alpha-beta implementation, and I don't think I've found them all.  Fortunately, testing will help me figure out when I've got it wrong, and hopefully the next 1000+ generations of evolution will be more fruitful.

Saturday, December 4, 2010

Evaluating a Checker Board with a Feed Forward Neural Network

With two-player zero-sum games such as checkers and chess, it is common to build computer players based on the idea of searching the game tree to select moves using some variant of  the minimax search algorithm and an evaluation function.  The evaluation function takes a game board as input and returns a numeric score as output, where the score is highest when the board is a win for the player, and the score is lowest when the board is a loss for the player.  For checkers, an extremely simple example of an evaluation function just adds up the number of pieces the player has, and subtracts the number of pieces the opponent has.

When using a neural network to evaluate a checkers board, we need some representation of the checkers board and the pieces on it.  Fogel and Chellapilla chose to map the board to an array of 32 floating point numbers, where each entry had one of five values:

  • +K   Player's King
  • +1    Player's Man
  • 0      Empty
  • -1     Opponent's Man
  • -K    Opponent's King

K was an evolvable value, initialized to 2.0.

In addition to the above, in their second and third experiments, they computed a value directly from the inputs (i.e. without weights): they summed the 32 floating point inputs, to come up with a value that reflects the piece differential between the two players.

We can imagine other mappings.  For example, we might have several binary inputs per square, such as:

  • 3 bits: black, white, king; at most one of black or white would be set, and king is only set if one of the other two is set.
  • 4 bits: empty, black, white, king; at most one of empty, black or white would be set, and king is only set if black or white is set.
  • 4 bits: black king, black, white, white king; at most one would be set at a time.
  • 5 bits: black king, black, empty, white, white king; exactly one would be set at a time.

Fogel and Chellapilla chose a search depth of 4 ply (2 moves by each player), but extended the depth whenever a  move by a player was "forced".  Unfortunately I found their description of how this was handled a bit vague:
In addition, when forced moves were involved, the search depth was extended (let f be the number of forced moves) because in these situations the player has no real decision to make. The ply depth was extended by steps of two, up to the smallest even number that was greater than or equal to the number of forced moves f that occurred along that branch. If the extended ply search produced more forced moves then the ply was once again increased in a similar fashion. Furthermore, if the final board position was left in an "active" state, where the player has a forced jump, the depth was once again incremented by two ply. Maintaining an even depth along each branch of the search tree ensured that the boards were evaluated after the opponent had an opportunity to respond to the player's move.
It wasn't clear to me whether this test is performed only on the moves of the player, or also on the moves of the opponent.  Furthermore, it wasn't clear what the definition of "forced move" was.  Did it mean that the player to move had only jumps to choose among (i.e. possibly more than one); or did it mean that the player to move had only a single move that was possible, whether it was a simple move or a jump; or did it mean that the player to move had only a single jump available.

My best guess is that whenever the player, and not the opponent, had only jumps available (whether they had a choice of jumps or not), the search depth on that branch of the game tree was increased by 2 ply.

UPDATE 2010-12-09: Dr. Fogel was kind enough to respond to my questions about forced jumps, and he recalls that this meant the player whose choice it was had only a single move, and thus had no real choice.  This applied for either player in the game tree, and it didn't matter whether the move was a simple move or was a jump.

Wednesday, December 1, 2010

Blondie24 Reconsidered

I discovered David Fogel's "Blondie24: Playing at the Edge of AI" in 2006 while killing time at the library waiting for my daughter.  It is a very engaging story of his effort, with colleague Kumar Chellapilla, to evolve an American Checkers (English Draughts) "player", with no human expertise provided, and then to evaluate that player by competing online against (presumably) people on zone.com (now zone.msn.com).

Dr. Fogel covers the history of AI in playing chess and checkers, and provides background on evolutionary algorithms and artificial neural networks.  He then covers the three network topologies they used, and the training algorithm, the key feature of which is that they created a random of population of players (really, evaluation functions), and had those players, and their offspring, compete against each other in tens of thousands of checkers games across hundreds of generations, keeping and evolving the most successful players..

One of the challenges they faced was limited computing resources; I think they were doing this work around the year 2000, and that the machine they had available to (mostly) dedicate to this task was a PC with a 400MHz Pentium processor.  For their final network topology, in which their were more than 5000 weights to be adjusted, it took 6 months to run through 800 generations.  As a result, they were not able to explore the many lines of investigation that spring to mind.

I'm interested in following some of those lines, and I have the luxury of 10 more years of CPU development.  To provide a baseline, I've been working to reproduce their work, based on the information in Dr. Fogel's book, and the several papers they published together on the topic.  I'll be writing about my efforts in posts to follow this.

Sunday, December 27, 2009

Android Emulator -- Please Wait

I'm trying out the Android Development Tools (Eclipse-based), and have been very frustrated at the fact that the Hello World application wouldn't run. The emulator just sat there display the word Android (not the logo) for several minutes until I gave up:



I searched for suggestions, and it turned out that the problem was simply that I was being impatient. The first time you run the emulator with a specific Android Virtual Device (avd), it sets up a bunch of image files, and this is apparently rather time consuming.  After a while, you see this screen (SDK 1.6) with the animated Android logo:



And finally, it reaches the home screen (or your application, depending on how you launched the emulator):



So, apparently patience IS a virtue. :-)