2012/11/30

in memory of pds

These are busy times, the end of the world is coming closer quickly. Maybe I should go out on the streets with a big sign stating Repent sinners before it is too late ! Be saved, use NetKernel !

Actually the Mayans didn't say anything about the end of the world, but it would definitely be one of the more interesting publicity campaigns.

Right, no more philosophy this week. In his Tic-Tac-Toe series Peter Rodgers bumps into the problem that the available in memory implementation of the PDS accessor doesn't quite implement all the functionality that a PDS accessor should have. He then quickly skips to using the H2 backed implementation.

While that of course works (the H2 implementation) I noticed in my Connect Four implementation that things are not as snappy as they should be for a game. Especially if the board gets bigger, the game becomes database bound.

So, here is my implementation of the in memory PDS accessor. It uses the golden thread pattern for expiry. Enjoy !

// The usual suspects for an accessor
import org.netkernel.layer0.meta.impl.SourcedArgumentMetaImpl;
import org.netkernel.layer0.nkf.*;
import org.netkernel.module.standard.endpoint.StandardAccessorImpl;

// Processing
import org.netkernel.layer0.representation.IHDSNode;
import org.netkernel.layer0.representation.IHDSNodeList;
import org.netkernel.layer0.representation.IReadableBinaryStreamRepresentation;
import org.netkernel.layer0.representation.impl.HDSBuilder;
import org.netkernel.request.IRequestResponseFields;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class InMemoryPDSAccessor extends StandardAccessorImpl {
    private static ConcurrentHashMap<String, InMemoryResource> mResources;
   
    private static class InMemoryResource {
        private final Object mRepresentation;
        private final IRequestResponseFields mUserMetaData;

        @SuppressWarnings("rawtypes")
        public InMemoryResource(INKFResponseReadOnly aResponse) {      
            if (aResponse != null) {  
                mRepresentation = aResponse.getRepresentation();
                mUserMetaData = aResponse.getHeaders();
            }
            else {  
                mRepresentation = null;
                mUserMetaData = null;
            }          
        }
      
        public Object getRepresentation() {  
            return mRepresentation;
        }
      
        public IRequestResponseFields getUserMetaData(){
            return mUserMetaData;
        }
    }

    public static class PDSArguments {
        public String mInstance;
        public String mZone;
        public String mIdentifier;
      
        private PDSArguments(INKFRequestContext aContext) throws NKFException {
            // Verify instance
            if (aContext.getThisRequest().argumentExists("instance")) {
                mInstance = aContext.getThisRequest().getArgumentValue("instance");
                if (mInstance.equals("pbv:instance")) {
                    mInstance = aContext.source("arg:instance",String.class);
                }
            }
            else {
                throw new NKFException("request does not have the required - instance - argument");
            }

            // Verify zone          
            if (aContext.getThisRequest().argumentExists("zone")) {
                mZone = aContext.getThisRequest().getArgumentValue("zone");
                if (mZone.equals("pbv:zone")) {
                    mZone = aContext.source("arg:zone",String.class);
                }
            }
            else {
                throw new NKFException("request does not have the required - zone - argument");
            }
            if (mZone.equals("")) {
                throw new NKFException("request does not have a valid - zone - argument");
            }          
          
            // Verify identifier
            if (aContext.getThisRequest().argumentExists("pds")) {
                mIdentifier = aContext.getThisRequest().getArgumentValue("pds");
                if (mIdentifier.equals("pbv:pds")) {
                    mIdentifier = aContext.source("arg:pds",String.class);
                }
                if (! mIdentifier.startsWith("/")) {
                    mIdentifier = "/" + mIdentifier;
                }
            }
            else {
                throw new NKFException("request does not have the required - identifier - argument");
            }
            if (mIdentifier.equals("")) {
                throw new NKFException("request does not have a valid - identifier - argument");
            }
        }

        private PDSArguments(String aInstance, String aZone, String aIdentifier) {
            mInstance = aInstance;
            mZone = aZone;
            mIdentifier = aIdentifier;
        }
      
        public Boolean isSet() {
            return mIdentifier.endsWith("/");
        }
      
        public String getCombined() {
            return mInstance + ":" + mZone + ":" + mIdentifier;
        }
      
        public String getGoldenThread() {
            return "gt:pds:" + mInstance + ":" + mZone + ":" + mIdentifier;
        }
      
        public String getIdentifier() {
            return mIdentifier;
        }

        public String getZone() {
            return mZone;
        }      

        public String getInstance() {
            return mInstance;
        }

        public boolean equals(Object aObject) {
            boolean vResult=false;
          
            if (aObject instanceof PDSArguments) {
                PDSArguments vOther = (PDSArguments) aObject;
                vResult = (mIdentifier.equals(vOther.mIdentifier) && mZone.equals(vOther.mZone) && mInstance.equals(vOther.mInstance));
            }
            return vResult;          
        }
      
        public int hashCode() {
            return mInstance.hashCode() ^ mZone.hashCode() ^ mIdentifier.hashCode();
        }
    }

    public InMemoryPDSAccessor() {
        this.declareThreadSafe();
        this.declareSourceRepresentation(IReadableBinaryStreamRepresentation.class);
        this.declareSourceRepresentation(IHDSNode.class);
        this.declareInhibitCheckForBadExpirationOnMutableResource();
        this.declareArgument(new SourcedArgumentMetaImpl("instance",null,null,new Class[] {String.class}));
        this.declareArgument(new SourcedArgumentMetaImpl("zone",null,null,new Class[] {String.class}));
        this.declareArgument(new SourcedArgumentMetaImpl("pds",null,null,new Class[] {String.class}));
        mResources = new ConcurrentHashMap<String, InMemoryResource>();
    }

    public void onSource(INKFRequestContext aContext) throws Exception {
        // SOURCE requires three arguments, instance zone and pds
      
        PDSArguments aArguments = new PDSArguments(aContext);
      
        if (aArguments.isSet()) {
            HDSBuilder vSet = new HDSBuilder();
            vSet.pushNode("set");

            for(Map.Entry<String, InMemoryResource> vEntry: mResources.entrySet()) {
                if (vEntry.getKey().startsWith(aArguments.getCombined())) {
                    int i = vEntry.getKey().indexOf(aArguments.getIdentifier());
                    String vPDS = vEntry.getKey().substring(i);
                    vSet.addNode("identifier", "pds:" + vPDS);          
                    vSet.pushNode("pds");
                    vSet.addNode("instance", aArguments.getInstance());
                    vSet.addNode("zone", aArguments.getZone());
                    vSet.addNode("pds", vPDS);
                    vSet.popNode();
                }
            }

            vSet.popNode();
          
            INKFRequest subrequest = aContext.createRequest("active:attachGoldenThread");
            subrequest.addArgument("id", aArguments.getGoldenThread());      
            aContext.issueRequest(subrequest);
          
            aContext.createResponseFrom(vSet.getRoot());
        }
        else {
            InMemoryResource vResource = mResources.get(aArguments.getCombined());
          
            if (vResource != null) {
                INKFRequest subrequest = aContext.createRequest("active:attachGoldenThread");
                subrequest.addArgument("id", aArguments.getGoldenThread());      
                aContext.issueRequest(subrequest);

                INKFResponse vResponse = aContext.createResponseFrom(vResource.getRepresentation());
                if (vResource.getUserMetaData() != null) {
                    vResponse.setHeaders(vResource.getUserMetaData());
                }
            }
            else {
                // default response is null
            }          
        }
    }
   
    public void onExists(INKFRequestContext aContext) throws Exception {
        // SOURCE requires three arguments, instance zone and pds
      
        PDSArguments aArguments = new PDSArguments(aContext);

        INKFResponse vResponse;

        if (aArguments.isSet()) {
            Boolean vResult = false;
            for(Map.Entry<String, InMemoryResource> vEntry: mResources.entrySet()) {
                if (vEntry.getKey().startsWith(aArguments.getCombined())) {
                    vResult = true;
                }
            }
            vResponse = aContext.createResponseFrom(vResult);
            if (vResult) {              
                INKFRequest subrequest = aContext.createRequest("active:attachGoldenThread");
                subrequest.addArgument("id", aArguments.getGoldenThread());      
                aContext.issueRequest(subrequest);
            }
            else {
                vResponse.setExpiry(INKFResponse.EXPIRY_ALWAYS);                          
            }
        }
        else {
            if (mResources.containsKey(aArguments.getCombined())) {
              
                INKFRequest subrequest = aContext.createRequest("active:attachGoldenThread");
                subrequest.addArgument("id", aArguments.getGoldenThread());      
                aContext.issueRequest(subrequest);
              
                vResponse = aContext.createResponseFrom(true);          
            }
            else {
                vResponse = aContext.createResponseFrom(false);
                vResponse.setExpiry(INKFResponse.EXPIRY_ALWAYS);          
            }          
        }

    }
   
    public synchronized void onSink(INKFRequestContext aContext) throws Exception {
        // Important : the onSink is synchronized ... only one at a time
        // SINK requires three arguments, instance, zone and pds and will persist
        // the primary argument
      
        PDSArguments aArguments = new PDSArguments(aContext);

        if (aArguments.isSet()) {
            throw new NKFException("unable to SINK to a set");
        }

        INKFRequest subrequest = aContext.createRequest("active:cutGoldenThread");
        subrequest.addArgument("id", aArguments.getGoldenThread());      
        aContext.issueRequest(subrequest);

        @SuppressWarnings("rawtypes")
        INKFResponseReadOnly vPrimary = aContext.getThisRequest().getPrimaryAsResponse();
        InMemoryResource vResource = new InMemoryResource(vPrimary);
        mResources.put(aArguments.getCombined(), vResource);
    }
   
    public void onDelete(INKFRequestContext aContext) throws Exception {
        // SOURCE requires three arguments, instance zone and pds
      
        PDSArguments aArguments = new PDSArguments(aContext);

        if (aArguments.isSet()) {
            IHDSNode vSet = null;
          
            INKFRequest subrequest = aContext.createRequest("active:pds");
            subrequest.addArgument("instance", aArguments.getInstance());
            subrequest.addArgument("zone", aArguments.getZone());
            subrequest.addArgument("pds", aArguments.getIdentifier());
            subrequest.setVerb(INKFRequestReadOnly.VERB_SOURCE);
            subrequest.setRepresentationClass(IHDSNode.class);
          
            vSet = (IHDSNode)aContext.issueRequest(subrequest);
            IHDSNodeList vNodes = vSet.getNodes("/set/pds");
            for (IHDSNode vNode : vNodes) {
                subrequest = aContext.createRequest("active:pds");
                subrequest.addArgument("instance", aArguments.getInstance());
                subrequest.addArgument("zone", aArguments.getZone());
                subrequest.addArgumentByValue("pds", vNode.getFirstValue("pds"));
                subrequest.setVerb(INKFRequestReadOnly.VERB_DELETE);
                subrequest.setRepresentationClass(Boolean.class);
                aContext.issueRequest(subrequest);
            }
            subrequest = aContext.createRequest("active:cutGoldenThread");
            subrequest.addArgument("id", aArguments.getGoldenThread());      
            aContext.issueRequest(subrequest);
          
            INKFResponse vResponse = aContext.createResponseFrom((vNodes != null));
            vResponse.setExpiry(INKFResponse.EXPIRY_ALWAYS);                      
        }
        else {
            INKFRequest subrequest = aContext.createRequest("active:cutGoldenThread");
            subrequest.addArgument("id", aArguments.getGoldenThread());      
            aContext.issueRequest(subrequest);
          
            InMemoryResource vResource = mResources.remove(aArguments.getCombined());
          
            INKFResponse vResponse = aContext.createResponseFrom((vResource != null));
            vResponse.setExpiry(INKFResponse.EXPIRY_ALWAYS);          
        }
    }
}

 

2012/11/01

from tic-tac-toe to connect four

The only way to find out if something is merely noise or actual information is sit down, read it and try what it says. Yourself. They named me Tom for a reason.

So last weekend I sat down, started reading [part1] of the Tic-Tac-Toe (TTT) example in the 1060 Research newsletters and set myself the goal of using it to create a Connect Four game.


There are a couple of differences :

The board is bigger. Typically Connect Four is being played on a 6 (rows) x 7 (columns) board, but variations exist and I wanted to have as general a solution as I could get. This resulted in two resources :
res:/connectfour/rows
res:/connectfour/columns
These can be backed by anything (a literal, a fileset, a database implementation), but the point is that they return the dimensions of the board.

There are more diagonals in play. While having a general solution for rows and columns, Peter rather quickly glosses over the diagonals in the TTT-solution, just defining the two that count (one of which is actually an antidiagonal).

I decided to have a more general solution where a diagonal goes from top left downwards. The diagonal:0 starts in the top left corner. Diagonals above that one get a positive index (diagonal:1 and so on, counting to the right), diagonals underneath that one get a negative index (diagonal:-1 and so on, counting down).

Antidiagonals go from top right downwards. The antidiagonal:0 starts in the the top right corner.  Antidiagonals above that one get a positive index (antidiagonal:1 and so on, counting to the left), antidiagonals underneath that one get a negative index (antidiagonal:-1 and so on, counting down).  

A token drops down the column
. As you know, a token (I went with X and O again) is not put in a specific place, but drops down the column into the lowest available position.


The victory condition is four of the same token next to each other in a row, column, diagonal or antidiagonal
. That after all is the name of the game ...



All that resulted in a bit more code. Since the dimensions of the board are unknown, I couldn't just map a row, column, diagonal and antidiagonal to a cell{} resource. Here for example is my groovy code for the row :


import org.netkernel.layer0.nkf.*;

INKFRequestContext aContext = (INKFRequestContext)context;

int vNumberOfRows = aContext.source("res:/connectfour/rows", Integer.class);
int vNumberOfColumns = aContext.source("res:/connectfour/columns", Integer.class);

int vRow = Integer.parseInt(aContext.getThisRequest().getArgumentValue("x"));

String vIdentifier = "cells{";


if ( (vRow >=0) && (vRow < vNumberOfRows)) {

  for (int vColumn = 0; vColumn < vNumberOfColumns; vColumn++) {
    vIdentifier = vIdentifier + "c:" + vRow + ":" + vColumn + ",";
  }
}
else {

  throw new NKFException("argument - x - should be in the range [0 - " + (vNumberOfRows - 1) + "]");
}

vIdentifier = vIdentifier + "}";

INKFRequest subrequest = aContext.createRequest(vIdentifier);
subrequest.setVerb(INKFRequestReadOnly.VERB_SOURCE);

aContext.createResponseFrom(aContext.issueRequestForResponse(subrequest));


In case you are wondering why I take context and put it into aContext ... that works a lot easier in my editor.

Obviously, the SINK to a cell also requires a bit of code :

case INKFRequestReadOnly.VERB_SINK:
  int i;
  for(i = vNumberOfRows - 1; i >= 0; i--) {
    if (! (aContext.exists("pds:/connectfour/cell/" + i + "-" + vColumn) ) ) {
      aContext.sink("pds:/connectfour/cell/" + i + "-" + vColumn, aContext.sourcePrimary(String.class));

      aContext.sink("pds:/connectfour/lastmove", "c:" + i + ":" + vColumn + ":" + aContext.sourcePrimary(String.class));

      break;
    }
  }
  if (i < 0) {
    NKFException e = new NKFException("invalid move");
    aContext.createResponseFrom(e);
  }
  break;

This also shows that I keep track of the last move made, a very convenient resource, since in order to check if there's a win, I need to know where the token fell.


Now, it is very easy to stand on the shoulders of a giant and shout out how great you are ... while ignoring the giant (which then proceeds to punch you in the face). However, given the above variations ... it was plain sailing all the way. The TTT story was great information, it delivers the goods !

For those of you not on Facebook, the amount of very (!) popular games that are mere variations (!) on this theme (with a bit of graphical polish) is huge. Just looking [here], I note Bubble Safari, Bubble Witch Saga, Diamond Dash, Candy Crush Saga, Bejeweled Blitz, Bubble Island. Look at the numbers. Look again, you missed some zeroes the first time.

Now, I'm not a graphical wizard (know thy strenghts and weaknesses), but when showing my first cut of the game to a friend, she wanted graphical icons instead of the textual X's and O's. I also added a multigame layer so it becomes a hotseat game that you can play with your loved ones. You can reach the (early) Christmas edition online here : http://netkernelbook.org/connectfour/<youridentifier>/

Obviously you need to replace <youridentifier> with some number or word or whatever that only you know.


A couple of quid pro quos to end this blogentry :

* A real multiplayer version is coming up soon. I'm thinking about using websockets and you can see that lastmove-resource is going to be very handy.
* I noticed as well as you - when you try it - that it is dreamily slow, not blindingly fast. This is due to the persistance mechanism being in a database (remember Peter switched to database persistance) rather than in memory. For a TTT that's sufficient, for larger boards that works too slow. I'm working on a fix for that. [Here] you can have a look at the Visualizer trace for a first move (with cleared cache). It does add up.
* Note that I only have a small host out there, it is a showcase host, not a massive player host. If you are interested in your own copy, contact me and I'll send you the full source.