Node.js vs Vert.x (Part 1)

Now for a change of pace. Recently at work, we’ve been trying to figure out what platform to build an application that will handle serving realtime data to customers. We want the system to be fast, scalable and able to handle hundreds, maybe thousands or even tens of thousands of requests per second.

I did a bit of prototyping in both node and vert.x to see how they performed under pressure. To do this, I built a cute webapp that makes a bunch of requests on basic web servers written in both node.js and vert.x to see how fast they could respond and how they would handle under a heavy load of requests. Here’s a picture of the ui made for the webapp (build in angular.js).

Node webapp
Node webapp

I created a form that allows for various inputs. In it, one can specify several variables including the following:

The variables:

  • Iterations – number of http requests to make
  • Block Size – How often a result is computed (reports start time for request, end time, average time per call (ms) and total time (ms) )
  • Range – How many results to display on screen – the graph tracks this
  • Polling – Toggle On/Off (this will start polling requests as fast as node.js can handle them. These are serial in nature).
  • Show Graph – toggle graphing on/off (off will provide better javascript performance)

Thanks to angular-seed for the fast prototyping and angular-google-chart for charting.

Benchmarking Parameters: Each request is a simple get request made to the respective webserver, which then writes a header and a “Hello” response. The requests are made through angular’s $http method. When a successful response is received, the callback function calls another $http request, until the number of successful responses received equals the number of iterations specified. I measure the time it takes from the time the request is made until the number of requests received per block is complete.

Time Keeping: I try to avoid all delays that could be attributable to javascript rendering (e.g. the timestamp is taken when the first request in the block is made. Then the timestamp is recorded when the # of responses in a block is received. I send both these parameters to a javascript function, which is responsible for rendering the results to the display. I also added a function to enable polling requests to be made, which makes $http requests as fast as responses can be received in order to add stress to the server’s load. This is enabled with the “polling” button.

Here’s a snippet of the webserver source code.

In Node.js:

StaticServlet.prototype.handleRequest = function(req, res) {
  var self = this;



  var path = ('./' + req.url.pathname).replace('//','/').replace(/%(..)/g, function(match, hex){
    return String.fromCharCode(parseInt(hex, 16));
  });

  console.log(path);
  if (path == './show') {

      res.writeHead(200, {'content-type': 'text/html'});
      res.write("Hello: ");
      res.end();

  } else if (path == './version') {
    res.writeHead(200, {'content-type': 'text/html'});
      res.write("Node.js version: " + 'v0.10.26');
      res.end();
    
  } else {
    var parts = path.split('/');
    if (parts[parts.length-1].charAt(0) === '.')
      return self.sendForbidden_(req, res, path);
    else {
      fs.stat(path, function(err, stat) {
        if (err)
          return self.sendMissing_(req, res, path);
        if (stat.isDirectory())
          return self.sendDirectory_(req, res, path);
        return self.sendFile_(req, res, path);
      });
    }
  }
}

In Vert.x:


server.requestHandler(function(req) {
var file = '';

  if (req.path() == '/show') {
  	  req.response.chunked(true);
  	  req.response.putHeader('content-type','text/html');
      req.response.write("Hello: ");
      req.response.end();
  } else if (req.path() == '/version') {
  	  req.response.chunked(true);
  	  req.response.putHeader('content-type','text/html');
      req.response.write('Vertx version: ' + '2.0.2-final (built 2013-10-08 10:55:59');
      req.response.end();
  } else if (req.path() == '/') {
    file = 'index.html';
    req.response.sendFile('app/' + file);   
  } else if (req.path().indexOf('..') == -1) {
    file = req.path();
    req.response.sendFile('app/' + file);   
  }
  

See? Dead simple. Of course there are lots of flaws with this methodology (e.g. the webservers are only serving static data, are writing short responses, are not optimized, etc.). It wasn’t my intention to come to a hard conclusion with this. I just wanted a data point and to experiment with both platforms. It turns out they (at least in this test) came very close to one another in terms of performance. Both servers were running on my machine, which specs are listed below.

System Specs: Macbook Pro, mid-2012, 2.3ghz with 16gb ram and a 512gb ssd. Both webservers are running locally on my machine with a bunch of other apps open.

And here are some preliminary results:

Here’s the node.js webserver, with polling turned on:

Node while polling, 1000 requests, 50 request block size
Node while polling, 1000 requests, 50 request block size

Here’s the vert.x webserver, with polling turned on:

Vert.x while polling, 1000 requests, 50 request block size
Vert.x while polling, 1000 requests, 50 request block size

You can see that they’re very close. Next I tried stressing both servers a bit through running several concurrent queries and several “instances” of the web app. In a later post, I’ll put up some more detailed results with trying to stress both webservers out. The response time definitely slows down as more are being made.

Conclusions: Both webservers are surprisingly close in terms of response/processing/overhead time. My CPU usage goes a bit higher on the vert.x server, but I do have several other applications running. I also haven’t tested running multiple instances of the same verticle yet in vert.x, or trying to fork processes in node.js. Both webservers are as barebones as they get. So in other words, I can’t make any hard conclusions yet, except to say that both servers are

  • Able to handle high loads of requests per second (probably on the order of 500 – 1000
  • Out of the box, both servers run roughly equivalently

These results seemed a little bit surprising to me, given that on the web vert.x seems to have faster results. One factor that may contribute to this is the lack of realism in server response. It’s probably not the case that so many requests would be coming in simultaneously (or there would be multiple server instances to handle such requests), and the response size is very small. Since both servers are basically just writing to a stream, as long as the I/O is written with performance in mind, this may be roughly as fast as a my CPU can handle writing responses. Another hypothesis is perhaps that vert.x really shines in handling multiple instances. I’ll have to experiment and report my results.

Postscript: In case you want to try it out for yourself, I’ve made the source code available on my github @ https://github.com/rocketegg/Code-Projects/tree/master/ServerPerformance I know this test has been done with much more sophistication and by a lot of people out there, but hopefully you can play around with this webapp, have fun and learn something.

GWT/GXT Theming Part 2 – Adding Custom Appearance Classes on top of Sencha Themebuilder

Likely one of the first things you’ll encounter if using the themebuilder is how to create a custom style for something the themebuilder doesn’t support. In my adventures trying to build on top of Sencha’s themebuilder, it became apparent to me that they intended the tool to be used in a standalone fashion. That is, one runs the themer.sh or themer.bat file to generate the theme.jar file and you plug and play it in conjunction with GWT.

However, because the theme file is applied uniformly across your application, what happens if you don’t want buttons in one place to look like buttons in another? This came up when building our webapp, where we wanted our top-level nav to have one color and appearance on hover and other buttons within the application to have another color. As it turns out, there’s no way to specify this in the .theme file.

  • One set of buttons (rendered by the themebuilder)
  • Screen Shot 2014-02-27 at 2.25.46 PM

  • Another set of buttons (custom appearance)
  • Screen Shot 2014-02-27 at 2.29.29 PM

  • Yet another set of buttons (customer appearance)
  • Screen Shot 2014-02-27 at 2.30.20 PM

    So how did I do this? In fact, there isn’t an easy way currently. I had to go digging through the compiled appearance classes made by the themebuilder.jar file in search of an answer. Here’s an example of what the themebuilder spits out for a button made with your custom .theme file.

    Step 1: Create an custom appearance class for your button/widget that extends Sencha’s appearance class

    So the first step I found to creating custom styling on top of the themebuilder was to create my own appearance class. However, I didn’t want to start from scratch because Sencha already provides a good basis (e.g. by applying the fonts, default colors, creating sliced image files, etc). It’s true that a lot of these things go out of the window when creating your own appearance class and you can lose multi-browser support, but in our case, it was better than keeping all the buttons looking exactly the same.

    Here’s example of a custom appearance class for the dark grey buttons you see above.

    /**
     * HeaderButtonAppearance extends a theme appearance created by Sencha's
     * themebuilder.jar file.  It uses the gifs and base css created by Sencha's
     * themebuilder then adds additional css styling and modifies the rendering
     * logic to display header buttons.  
     */
    public class HeaderButtonAppearance<M> extends ButtonCellDefaultAppearance<M> {
    
      	final HeaderButtonStyle customStyle;
    	
    	/**
    	 * These are "resources" that comprise a ButtonCellAppearance
    	 * This interface describes the resources used by this button appearance.  This is not 
    	 * Sencha-specific.  I had originally tried extending the Css3ButtonResources class that 
             * the themebuilder spits out, but it required keeping the entire .css class in my package as well.
    	 */
      	public interface HeaderButtonResources extends ClientBundle {
      		@Source("HeaderButtonCell.css")
      		HeaderButtonStyle style();
      	}
      	
            //These methods are my new styles.
      	public interface HeaderButtonStyle extends CssResource {
      		String headerButton();
      		
      		String outerButton();
      	}
      	
      	public HeaderButtonAppearance() {
      		HeaderButtonResources headerResources = GWT.create(HeaderButtonResources.class);
      		customStyle = headerResources.style();
      		StyleInjectorHelper.ensureInjected(headerResources.style(), true);
      	}
      	
      	@Override
        public void render(ButtonCell<M> cell, Context context, M value, SafeHtmlBuilder sb) {
      	    Css3ButtonResources resources = GWT.create(Css3ButtonResources.class);
      	    Css3ButtonStyle style = resources.style();
                //Additional rendering stuff here, use style.____() to access the custom themebuilder styles
                //Sencha by default uses a two nested divs to render a button.  You may have to extract the precise
                //.class file from the theme.jar file to see how the html is constructed.
    
       }
    }
    
      There are a few quirks regarding this appearance class to be aware of:

    • In the *ButtonStyle interface, the string method maps to a css class name in the *ButtonResources interface css file.
    • The .css file that is used for the mapping must be in the same package as the appearance class
    • In order to use the styles made available through the compiled css and appearance classes built by the themebuilder, you have to instantiate a ClientBundle and access the css classes through the Css3ButtonStyle interface.
    • Because the default rendering of the button renders the themebuilder’s classes (e.g. for buttons, there are two nested divs, where the outer has .button {} applied and the inner has .buttonInner {} applied, I had to rewrite the render method myself. In my replacement, I swapped out the .button and .buttonInner classes for my own css classes. I maintain everything else.
    • I think there has to be a better way to do this. For example, I experimented with injecting html (an innermost div) into the cell which accepts only my css. That way, I could avoid having to @Override the render class and modify the html on the backend. However, it didn’t end up working very well because even with injecting my own css, I could not overwrite the styling applied to the parent divs. Ultimately, I think one could write a utility to go in and scrape out the other classes applied by the themebuilder, but this seemed like it would be a real hassle.

    Step 2: Define the .css classes in a file in the same package for your custom appearance

    Here’s an example of what my .css class looked like.

    .outerButton {
      border: none;
      background-color: #3892D3;
      background: transparent;
      padding: 4px;
      cursor: pointer;
      outline: none;
      padding-right:30px;
    }
    
    .headerButton {
      	padding: 0px;
      	text-align: left;
    	font-family: Arial, Helvetica, sans-serif;  /* actual font is not arial */
    	font-size: 17px;
    }
    
    .headerButton:hover {
    	color: white;
    }
    

    If you look at my HeaderButtonStyle class, you’ll notice that the css class names map directly to the functions in the interface. GWT takes care of the actual mapping of values. These are the classes that I can use to style my widget and are accessible via my instance of the HeaderButtonStyle. Here’s an example of how I render the HeaderStyleButton:

    
    @Override
        public void render(ButtonCell<M> cell, Context context, M value, SafeHtmlBuilder sb) {
                //The default style CSS Resource in case I need to access styles built by the themebuilder
    
      	    Css3ButtonResources resources = GWT.create(Css3ButtonResources.class);
      	    Css3ButtonStyle style = resources.style();
    
                //Begin actual construction of the button widget
      		
      	    String constantHtml = cell.getHTML();
      	    boolean hasConstantHtml = constantHtml != null && constantHtml.length() != 0;
    
      	    boolean isBoolean = value != null && value instanceof Boolean;
    
      	    String text = hasConstantHtml ? cell.getText() : (value != null && !isBoolean)
      	        ? SafeHtmlUtils.htmlEscape(value.toString()) : "";
    
      	    String scaleClass = "";
      	    String iconClass = "";
      	    String additionalCssClasses = customStyle.headerButton();
    
                //Size-dependent styling
      	    ButtonScale scale = cell.getScale();
    
      	    switch (scale) {
      	      case SMALL:
      	        scaleClass = style.small();
      	        break;
    
      	      case MEDIUM:
      	        scaleClass = style.medium();
      	        break;
    
      	      case LARGE:
      	        scaleClass = style.large();
      	        break;
      	    }
    
                //Outer button class, you could add anything else you want here
      	    String buttonClass = customStyle.outerButton();
    
      	    boolean hasText = text != null && !text.equals("");
      	    if (!hasText) {
      	      buttonClass += " " + style.noText();
      	    }
     
                //The css classes applied to the inner div
                String innerClass = "";
      	    innerClass += " " + scaleClass;
      	    innerClass += " " + additionalCssClasses;
    
      	    SafeHtmlBuilder builder = new SafeHtmlBuilder();
    
      	    builder.appendHtmlConstant("<div class='" + buttonClass + "'>");
      	    builder.appendHtmlConstant("<div class='" + innerClass + "'>");
    
      	    builder.appendHtmlConstant(text);
      	    builder.appendHtmlConstant("</div></div>");
      	    sb.append(builder.toSafeHtml());
      	  }
    
    

    Step 3: Instantiate your widget using your custom appearance.

    TextButton button = new TextButton(new TextButtonCell(
            			new HeaderButtonAppearance<String>()), "Text for Button");
    

    You can see that when I instantiate a button, I pass in an appearance class instantiated with the type of value that the button receives (a string in this case). If you look at the prebuilt java classes (e.g. Css3ButtonCellAppearance) from the themebuilder, you’ll notice that the default constructor with no parameters will instantiate a cell with the default appearance. That’s why it’s necessary to use the constructor where you pass in the actual custom appearance class.

    Custom styling and appearance classes on top of Sencha themebuilder GXT 3.1 (Part 1 – Using the Themebuilder)

    I must find somewhere for my collected knowledge on the “joy” of using Sencha themebuilder. At my company, we’re currently working on building a custom style for our web application. Somewhere in the past, the decision was made to use Sencha GXT for their custom widgets and styling on top of GWT. Like most frameworks, things went smoothly as long as we were using the functionality out of the box. However, when we tried venturing outside, we were quickly reprimanded by the limitations of the framework.

    In our scenario, we needed to brand our application differently than one of the built-in Sencha themes. Fortunately for us, or so we thought, Sencha created a nice tool in the knick-of-time called the “themebuilder” (currently in beta as of 2/25/2014). The themebuilder alleviates some pains of styling if you stay strictly within the guardrails, but quickly becomes inadequate if you need to do styling on top of it.

    Part A: About the themebuilder and running it.

      Running it is easy (just make sure you are using java version 1.7+). On a mac:

    • You run ./themer.sh with certain command line options. The themer script reads in a custom Sencha file (*.theme) which it then uses to compile and build a set of appearance classes which GWT accepts. Here’s an example of the command I used:
    • ./themer.sh ../examples/mytheme/mytheme.theme
    • As of the beta 2/25/2014, the running the themer will by default override the .jar file.

    • The .theme file is a huge pain to work with. It’s Sencha’s own proprietary format. It’s currently not well documented, which makes it very difficult to know how certain values within the .theme file map to Sencha widgets and how these get mapped on top of GWT and then what eventually gets spat out in your browser. Here’s a snippet:
      theme {
        /* First, create a name for your theme, and define a package to place it in */
        name = "myCustomTheme"
        basePackage = "com.example"
      
        /* Next, configure these basic defaults, to be used throughout the file */
        text = util.fontStyle("Arial, Helvetica, sans-serif", "12px", "#000000", "normal")
        textWhite = util.fontStyle("Arial, Helvetica, sans-serif", "12px", "#eeeeee", "normal")
      
        borderRadius = 6
      
        bgColor = "#ffffff"
        headerBgColor = "#666666"
        menuHoverColor = "#e7e7e7"
        menuSelectColor = "#b7daff"
        headerBgColorLight = "#f9f9f9"
      
        iconColor = "#777777"
        ...
      }
      

      You can see that the file is not quite json, java, or css. It’s some mishmash of everything, but it allows you to define variables and reference them later on in the .theme. This is Sencha’s claim for the themebuilders utility. By simply changing a few values (e.g. the background color, font color, font text, etc.), you can change the entire look and feel of your web application. That is all fine and dandy, but what is not described is what things you actually can and can’t change. For example, here’s a list of things I found that the themebuilder is not capable of:

      • Styling a widget in one instance different from another
      • Adding custom fonts
      • Styling nested widgets differently from non-nested widget (e.g. a button in one panel looking different than a button in another)
      • Support for icons libraries like font-awesome or glyphicon
      • Styling text within a toolbar (the LabelToolItem widget)
      • Styling the body content various content panels widgets (ContentPanel, FramedPanel, AccordionPanelAppearance, Window, Dialog)
      • Stylizing a button when its menu is open vs. closed

      In the next series of posts, I’ll be showing you how I solved each of these issues. Stay tuned for more.

      A general tip: When modifying the .theme file, I used sublime text and had the syntax set to “Javascript.” This enabled some basic coloring and recognition of comments and strings. The coloring was very helpful.

      Part B: Applying the custom theme on top of your GWT project
      This part is more specific to GWT users, but may be helpful to some. I’m currently working in a build environment using Java 1.7, Eclipse Version: Kepler Service Release 1, Build id: 20130919-0819, GWT plugin version 1.8.9 to Eclipse, and maven. Assuming that you’re already configured and up and running with GXT and GWT, you should have an App.gwt.xml file that looks something like this:

      <?xml version="1.0" encoding="UTF-8"?>
      <!DOCTYPE module PUBLIC "-//Google Inc.//DTD Google Web Toolkit 2.5.1//EN"
        "http://google-web-toolkit.googlecode.com/svn/tags/2.5.1/distro-source/core/src/gwt-module.dtd">
      
      <module rename-to='mymodule'>
      ...
      	<!-- GXT Theme -->
       	<inherits name='com.example.Theme' /> 
      ...
      </module>
      

      The key line is the GXT Theme line where GWT applies a theme on top of all of its widgets. This theme name should follow the convention set forth in your .theme file.

        name = "myCustomTheme"
        basePackage = "com.example"
      

      After you build your theme.jar file using the custom .theme file (I used the skeleton.theme file included which has all the values in it), you need to add the jar to your buildpath (or to maven as a dependency). I found that the fastest workflow for me was to modify the .theme file, use an html tool that Sencha includes to approximate the styles, and have my buildpath point directly to the .jar file where it’s created by the themebuilder. For more on this html tool (which helps speed up theme creation), see this post.

      Edit: The new beta themebuilder (released by Sencha on 2/25/2014) spits out some instructions on how to do this, along with the context name of your theme.jar file.

      Here’s a sample:

      The customTheme theme has finished generating.
      Copy the jar (/path/to/theme/customTheme.jar) into your project and copy the following line into your gwt.xml file:
      
          <inherits name="com.example.Theme" />
      

      Then, I run GWT Server through my eclipse in debug mode, which picks up the changes to the theme. Because GWT is trying to rapidly render and compile all of the javascript files and apply the custom theme, it tends to operate very slowly.

      Hopefully if everything went according to play, you should see a different style on top of your application. In the next posts, I’ll start getting into customizing the theme and some workarounds for its deficiencies.

    Adding css sprites in GWT on top of GXT 3.1

    I’m a GWT/GXT beginner, so I typically end up having to look up how to do every little thing online in terms of styling/theming. However, after looking online for how to add css sprites to my application on top of GWT/GXT, I couldn’t find a good guide explaining how to do this. So I investigated and tinkered on my own and thought I would share what I discovered. There are a few necessary components:

    Step 1: Define your ClientBundle

    //My resource interface 
    public interface MyResources extends ClientBundle {
    	
        //@Source("mysprites.png")
        @ImageOptions(repeatStyle = RepeatStyle.None)
        ImageResource my_sprites();
        
        @Source("mysprites.css")
        MyCssResource resource();
        
        interface MyCssResource extends CssResource { 
        	String myLogo();
        	
        	String anotherSprite();
        }
    	
    }
    

    Here’s what my sprite image looks like: example

    First, it’s necessary to define an interface that extends the GWT ClientBundle. This interface becomes the entry point to injecting the proper CSS sprite into your web application.

    In the source above, you can see that I have a .png (this has to be in the same package as the interface), which is your sprite image. The way sprites are loaded are through a css class, which is defined in the CssResource which is also a part of the interface. You use the @Source annotations to define what the names of your files are.

    Here’s an example of what the css file should look like: You’ll notice that the gwt-image maps onto the name of the ImageResource method that is your css sprite. The height and width css properties correspond to the chunk of the image to use as your sprite. Background-position corresponds to where to start in the image (pixels from top, pixels from left).

    /* mysprites.css */
    @sprite .myLogo {
      gwt-image: "my_sprites";
      width: 86px;
      height: 36px;
      background-position: 0 0;
    }
    
    @sprite .anotherSprite {
      gwt-image: "my_sprites";
      width: 86px;
      height: 36px;
      background-position: 36 0;
    }
    

    Next, you define the interface of your CssResource, whose methods (String methodName();) get mapped to css classes defined in your css file.

    Step 2: Get an instance of your ClientBundle using GWT.create

    //My widget class
    private static MyResources myresource = GWT.create(MyResources.class);
    

    This is the instance that you will use to add sprites to your widget. I was doing this for a while, but noticed that after trying to call the methods made available through my CssResource interface, the css class was not being injected into my application. However, I did find that my sprite image was correctly injected. After some more online research, I found that you need to call this in order to ensure that the css class is actually injected. Add this line after you instantiate the class in order to actually put your css classes in your application

    //My widget class
    myresource.resource().ensureInjected();
    

    Here, myresource is the GWT object created for the entire resources class. resources() is the CSSResource which has the method ensureInjected(); Finally, you need to actually add a widget that contains the correctly styling in order to render the sprite correctly. Since CSS sprites are just classes, I used a blank GWT HTML widget, which just gets rendered as a blank div in your application.

    Step 3: Add the sprite to your application

    //My widget class
    HTML logo = new HTML();		
    logo.addStyleName(myresource.resource().myLogo());
    mybanner.add(logo, new HorizontalLayoutData(-1, -1, new Margins(0, 5, 5, 5)));
    

    Finally, in your application if you inspect the element, you can see that the CSS class got rendered into the application and attached to the HTML widget

    .

    /* Inspected Javascript */
    .GKTGO20BA3B-MyResources-MyCssResource-myLogo {
    height: 492px;
    width: 68px;
    overflow: hidden;
    background: url("data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAEQAAAHsCAYAAABrKwuFAAAPFUlE…Als9kMoqN9zlNMpAqDBOKWCBBGJ4BCICgySCoQhAEzbD+D1IzkMByojJyAAAAAElFTkSuQmCC") -0px -0px no-repeat;
    width: 68px;
    height: 36px;
    background-position: 0 0;
    }
    

    The end result:

    Screen Shot 2014-02-26 at 12.24.31 PM
    Let me know if you have any comments or questions.

    Tic Tac Toe

    So recently, I was given a coding assignment to create a Tic-Tac-Toe game, following some parameters. I was given full design freedom, but was tasked with emphasizing good coding structure/organization, algorithm use, and simplicity. There were also three types of strategies to design, including a player who tries to always win, one who always tries to tie, and one who plays randomly. It was a good assignment to test to see how far I’ve developed in these past several months. In retrospect, I think I did a respectable job. I ended up using lots of design patterns I hadn’t used before. It’s hard to say whether I’ve surpassed where I was when I left for law school, but taking my programming seriously has definitely elevated me quickly compared with where I was just a few months ago. In any case, here is a summary of the project with code available on my github (https://github.com/rocketegg/Projects/tree/gh-pages/Tic-Tac-Toe):

    TIC-TAC-TOE prompt

    1. A short description of how you approached the problem including design tradeoffs and future improvements.

    I approached the problem from more of a design angle than for sheer performance. Tic-tac-toe is a simple game, so even though many checking run in O(n^2) and take linear memory, this shouldn’t impede performance from a practical sense. It makes the source code more readable as well. I refrained from programming in a way that would box one in to a simple 3×3 grid. For example, the checks for whether the tic-tac-toe game has a winner could theoretically all be run in constant time since there are at most 8 winning configurations.

    Thus, it was my decision to focus more on extensibility so that any part of the program can be improved (as in the real world, based on time and requirement constraints). For example, players can easily be created by implementing the “Player.java” class. Each player has an associated chooseMove() method to implement, which returns a move based on a type of strategy. Following the strategy design pattern, strategies are also easily created and extensible as well. Thus, the win strategy is comprised on several substrategies (not all broken out into classes for simplicity sake) of deciding if there is a winning move to take, a losing move to block, choosing the optimal move, etc.

    In this way, future improvements could easily be made by adding strategies and employing them as part of the broader Win/Tie/Random strategies. One rule I did not have time to implement was a rule based on creation of a “fork” or a situation in which two possible winning scenarios are created so that the opponent is guaranteed a loss. Alongside that strategy would be the counterpart strategy of blocking a fork from forming.

    2. Working java code with instructions on how to run it.

    To run the java code, simply download and build the code and execute the application. The main class instantiates a menu which should be self-explanatory. I focused less on making this menu pretty, however doing so would not be difficult (just time-consuming).

    3. A description of the algorithm used including the strengths and weaknesses.

    As stated above, the algorithms are simple for the sake of readability. They could be improved in numerous ways. For instance, comparing win states for rows/columns could be done in constant time by doing 8 comparisons each based on a particular win configuration. Alternatively, one could create a string to represent a game board: e.g. “XXO|OXO|OXO” could represent the positions in snaking order. Then arithmetic based on a character array could be done to save memory and computation time. Finally (but not comprehensively), one could implement the algorithm using a depth-first-search algorithm. One thought I had was to implement the algorithm using DFS which would search for each possible win scenario given a board configuration. There wouldn’t be too many since board states in tic-tac-toe are often “forced” by needing to block an opponent’s winning position. A stack would be kept given the moves for the particular win scenario currently being followed by the DFS algorithm. When an opponent moves, the algorithm would recompute the win scenarios and choose another one to follow. I implemented a similar algorithm in my code (also available in my github at https://github.com/rocketegg/Practice/tree/master/src/solver) to solve the “peg jumping” game that is common in many bars.

    UPDATE: I’ve since implemented the minimax algorithm as a strategy for solving Tic-Tac-Toe. It was an interesting task, but very hard to debug. The logic is complex (especially with alpha-beta pruning), but it’s extensibility is fantastic. One hiccup I encountered when developing the algorithm was the scoring mechanism. Using just a default -1, 0, and 1 for “O” wins, “Tie game” or “X” wins turned out to be a bad decision (or one that rendered teh minimax strategy nearly useless) because the computer would evaluate a losing strategy that could eventually win (e.g. where the opponent could just immediately win) with the same weight as an immediate win (both have a 1 max value). This turns out to be a common problem with minimax algorithms in general. Thus, I had to tweak the scoring mechanism to take account of the depth of the recursive call. In any case, here is the minimax strategy :

    private BestMove chooseMinimaxMove(TicTacToeBoard board, String side) {
                   int bestScore;
                    GridCell bestMove = null;
                    String otherSide = side.equals("X") ? "O" : "X";
                    if ((bestScore = TicTacToeBoardExaminer.getScore(board, side, depth)) != TicTacToeBoardExaminer.NO_WINNER_YET) {
                            return new BestMove(null, bestScore);
                    }
                    ArrayList<GridCell> possibleMoves = TicTacToeBoardExaminer.getAllOpenMoves(board, side);
                    
                    if (side.equals("X"))        { //Player's turn
                            bestScore = -11;
                    } else {        //Opponent's turn
                            bestScore = 11;
                    }
    
                    BestMove b = null;
                    for (GridCell move : possibleMoves) {
                            board.update(move);
                            GridCell undoMove = new GridCell(move.getRow(), move.getCol(), true, " ");
                            b = chooseMinimaxMove(board, otherSide, depth+1);
                            board.update(undoMove);
                            if (side.equals("X")) {        //player turn
                                    if (b.getScore() > bestScore) {
                                            bestScore = b.getScore();
                                            bestMove = move;
                                    }
                            } else if (side.equals("O")){        //opponent turn
                                    if (b.getScore() < bestScore) {
                                            bestScore = b.getScore();
                                            bestMove = move;
                                    }
                            }
                            
                            //Simple Pruning
                            if (bestScore == TicTacToeBoardExaminer.maxWinScore(side)) {
                                    return new BestMove(bestMove, bestScore);
                            }
                    }
                    return new BestMove(bestMove, bestScore);
            }
            }
            
            /**
             * Just a wrapper class to hold a gridcell and a score
             * @author Gamer
             *
             */
            private class BestMove {
                    private GridCell move;
                    private int score;
                    
                    public BestMove(GridCell move, int score) {
                            this.move = move;
                            this.score = score;
                    }
                    
                    public GridCell getMove() {
                            return move;
                    }
                    
                    public int getScore() {
                            return score;
                    }
            }
    

    Additionally, as part of the minimax strategy, it’s really important to have a good scoring strategy with well-defined limits. Here is what I implemented:

            /**
             * Returns a score (if possible) based on a board configuration and 
             * if you are the side
             * Depth n - means that 10 is the max score - if the game is over on the first move
             *   otherwise, if there is a winning board, subtract the depth because it potentially
             *   opens up to a loss
             * Scores:
             *                 10 - n: side has won, n is depth
             *            -10 + n: other side has won, where n is depth
             *      0: is tie
             *      100: No winner yet
             *  
             * @param board
             * @param side
             * @return
             */
            public static int getScore(TicTacToeBoard board, String side, int depth) {
                    if (sideHasWon(board, "X"))
                            return PLAYER_WIN - depth;
                    else if (sideHasWon(board, "O"))
                            return OPPONENT_WIN + depth;
                    else if (board.getAllOpenCells().size() == 0 && side.equals("X"))
                            return TIE;// - depth;
                    else if (board.getAllOpenCells().size() == 0 && side.equals("O"))
                            return TIE;// + depth;
                    else
                            return NO_WINNER_YET;
            }
    

    4. Any alternate approaches considered.

    See above.

    5. A test suite that measures that probability of each of the computer based opponents winning when pitted against one another.

    I don’t have a fully-fledged test suite, however from the game menu, one can test n-games based on differing players (read: strategies). For example, one can test the win strategy against the tie strategy (i.e. Champ vs Toby) n-number of times. The results for 1000 games range at roughly about 250 games won for Champ, 0 games won for Toby, and the rest tied. One could easily translate this into roughly a 25% win rate when pitted against Toby. When pitted against the random strategy, this win rate creeps to about 90% with a 9% tie rate and about a 1% loss rate. In computing each of these statistics, the player who starts the game is rotated back and forth.

    6. Anything else you think would be valuable.

    I have extensively documented my source code so that it is easier to read. The main classes that one should look at are the TicTacToeGame class which encapsulates an entire game and the Player and Strategy classes to see how the logic is implemented in the backend. I would be happy to answer any other questions about my approach.

    Fade In, Fade Out

    So I’ve been hacking around in javascript lately to build our company’s new web content delivery web application. To put it lightly, javascript feels REALLY hacky to me. When there are random syntax errors without contextual highlighting (shoutout to eclipse!), it makes it really hard to debug errors. I guess it isn’t all bad. The fact that the interpreter can pick up changes on the fly makes development quicker.

    However, where javascript is involved, there is also hacking my way through CSS. Integrating multiple libraries (e.g. Jquery, Jquery UI, bootstrap, etc) all together to work seamlessly has proven to be an exercise in patience. However, after about a week, I feel much more comfortable with things now. Here are a few of the tricks I’ve picked up.

    1. In getting animations to work, having a “Fade In, Fade Out” animation mechanism to display the user’s selected

    would cause the

    to appear repeat the animation twice. This is because the JQuery selector I was using would select multiple and call the callback function multiple times. See here:

    $(".toggleableMADiv").fadeOut({
    			done: function() {
    			$(spanName).delay(200).fadeIn(200, function() {});
    			},
    			duration: 200
    		});
    

    To remedy this, there’s a JQuery answer using $.when(…).done() which can effectively handle multiple callbacks. Here’s the updated solution:

    		$.when($(".toggleableMADiv").fadeOut(200)).done(
    			function() {
    				$(spanName).delay(200).fadeIn(200, function() {});
    			});
    

    2. Next, I noticed that the animations would sometimes “bump” the entire screen over by around 10 pixels, whenever the y-axis scrollbar was loaded or disappeared. Apparently, there’s no good fix for this except to make the scrollbars always appear. This can be remedied through CSS:

    html {
    	overflow-y: scroll;
    }
    

    There are probably a ton of other things I’ve had to look on stackoverflow in order to solve. This is the element of javascript that I dislike … or maybe it just takes a while to get used to, to be in the “know.” I have to admit though, there are several really cool libraries in javascript that are freely available and so easy to add to one’s code. I’m looking at you datatables!

    Until next time, happy hacking.

    Hog Wild!

    So one mini-project I’ve been working on recently is a project for berkeley’s cs61a class. The goal of this project is to implement the game of hog, which is described below:

    In Hog, two players alternate turns trying to reach 100 points first. On each turn, the current player chooses some number of dice to roll, up to 10. Her turn score is the sum of the dice outcomes, unless any of the dice come up a 1, in which case the score for her turn is only 1 point (the Pig out rule).

    To spice up the game, we will play with some special rules:

    Free bacon. If a player chooses to roll zero dice, she scores one more than the largest digit in her opponent’s score. For example, if Player 1 has 42 points, Player 0 gains 1 + max(4, 2) = 5 points by rolling zero dice. If Player 1 has 48 points, Player 0 gains 1 + max(4, 8) = 9 points.
    Hog wild. If the sum of both players’ total scores is a multiple of seven (e.g., 14, 21, 35), then the current player rolls four-sided dice instead of the usual six-sided dice.
    Swine swap. If at the end of a turn one of the player’s total score is exactly double the other’s, then the players swap total scores. Example 1: Player 0 has 20 points and Player 1 has 5; it is Player 1’s turn. She scores 5 more, bringing her total to 10. The players swap scores: Player 0 now has 10 points and Player 1 has 20. It is now Player 0’s turn. Example 2: Player 0 has 90 points and Player 1 has 50; it is Player 0’s turn. She scores 10 more, bringing her total to 100. The players swap scores, and Player 1 wins the game 100 to 50.

    Most of the project is just implementing the guts of the game. The berkeley TAs were nice enough to implement the rest of the plumbing, including the test apparatus and gui. The last question, however, provided the most interesting question, and was definitely the most fun to work on and think about.

    Essentially, the last question asks you to implement a strategy to try to beat another strategy that rolls 5 every time. To get full credit for the problem, your strategy needs to beat the always_roll(5) strategy 59% of the time or better. I’m at 60.5% currently, and still looking for ways to improve.

    Essentially I did four things:

  • 1. First, I wrote a recursive algorithm to figure out all the possibilities of rolls and their respective point values

  • I then put these into a python dictionary keyed to the total value of the roll (based on hog rules), and figured out the number of combinations that would pertain to the value. I then converted these into percentages so I could reference them later on. See my algorithm below, completely unoptimized! I couldn’t even run all combinations for rolling 10 dice because my computer started to overheat and sizzle. In any case, I just needed a quick and dirty answer:

    # this function tries to roll a ____, based on the best way to do it
    def compute_probabilities(num_rolls, dice=six_sided):
        #compute possibilities
        k = 1
        global possibilities
        def f(dice, k):
            if (dice == six_sided):
                return pow(6,k)
            return pow(4,k)
    
        while (k <= num_rolls):
            print("Rolling {} dice possibilities.".format(k))
            possibilities = list()
            get_possibilities("", k, dice)
            convert_possibilities_to_matrix(possibilities, f(dice, k))
            k += 1
        
    possibilities = list()
    def get_possibilities(total, num_rolls, dice):
        i = 1
        global possibilities
        if (num_rolls == 0):
            return total
    
        if (dice == six_sided):
            sides = 6
        else:
            sides = 4
        while (i <= sides):
            mystr = get_possibilities(str(total) + str(i), num_rolls-1, dice)
            if (not mystr == None):
                possibilities.append(mystr)
            i += 1
    

  • 2. Second, armed with this knowledge and the expected value of rolling 1 through 10 dice (an earlier question for the project), I was able to establish a framework for representing the best choice.

  • I basically stored the expected values of rolling 1 through 10 in a list. Whichever index contained the highest expected value represented the move I wanted to take. Under this framework, I was simply able to modify the values in the list whenever I came across a more optimal solution.

  • 3. Third, I wrote several functions to adjust the values based on the context of the game. I’ve listed them below.
  •         #adjust based on swine swap 
            def adjust_swine_swap(score, opponent_score, eplist):
                if (score > opponent_score or opponent_score % 2 == 1):    #never want to swine swap if our score is bigger
                    return eplist   
    
                ineed = (opponent_score / 2) - score #what i need to trigger swine swap
                if (ineed <= 0): #if i would need a neg, not possible
                    return eplist
    
                ineed = int(ineed)
                difference = opponent_score - (score + ineed) #the benefit
    
                if ineed == getBaconScore(opponent_score):  #roll zero, a sure thing
                    eplist[0] = max(eplist[0], difference) 
    
                if ineed == 1:  #roll 1
                    eplist[10] = max(eplist[10], difference * percentages.get(ineed)) 
    
                if ((ineed >= 2 and ineed <= 6 and dice == six_sided) or 
                    (ineed >= 2 and ineed <= 4 and dice == four_sided)): 
                    eplist[1] = max(eplist[1], difference * percentages.get(ineed))
    
                return eplist
    

    adjust_swine_swap modifies the expected values of rolling dice based on whether there is a beneficial swine_swap. I started out with the known case of rolling zero dice, which results in a guaranteed swine_swap. I then recognized that this process could be repeated for when swine_swap could be triggered with a roll resulting in a value of 1. 1 is pretty common in “hog” since the player is able to roll up to 10 dice. Hence, not rolling a 1 (with a six-sided dice) would simply be 1 – (5/6)^10. Likewise, for a four-sided dice, it would be 1 – (3/4)^10. I didn’t need to prove this, but if you look at the results generated from step 1, it’s cool that it’s verified. I also noticed from the percentiles that the best chance of rolling a 2 through 6 or a 2 through 4 was with one dice. Thus, I didn’t really need to calculate the percentiles for all possible combinations of 1 through 10 dice, since they just get worse with more than one die.

            #adjust based on trying to force a four dice
            def adjust_try_four(score, opponent_score, eplist):
                score_with_zero = score + getBaconScore(opponent_score)
                score_with_one = score + 1
    
                #if we can cause opponent to have to roll a four_sided dice, calc the benefit
                if ((score_with_zero + opponent_score) % 7 == 0):
                    eplist[0] = max(eplist[0], eplist[0] + 4.25)
    
                if ((score_with_one + opponent_score) % 7 == 0):
                    eplist[10] = max(eplist[10], eplist[10] + (4.25 * percentages.get(1)))
    
                return eplist
    

    adjust_try_four tries to do a similar thing by adjusting the values based on whether the current player can force the other player to use a four-sided dice (i.e., if the player’s score and the opponent’s score % 7 == 0). This doesn’t always result in a more optimal move than swine_swap, but again, the function only updates with the max expected value. I had to approximate the benefit of forcing the other player to roll with four-sided dice based on the findings from earlier. Because the other player always rolls a 5, the expected value of rolling a 6-sided dice versus a 4-sided dice is approximately 4.25 higher.

            #adjust based on almost guaranteed victory
            def take_guaranteed_victory(score, opponent_score, eplist):
                score_with_zero = score + (getBaconScore(opponent_score) * 2)
                #try more conservative approach
    
                if (score_with_zero >= GOAL_SCORE): #guaranteed victory by rolling a 0
                    if (not causes_swine_swap(score_with_zero, opponent_score)):
                        eplist[0] = 100 #set to arbitrary high # so always rolls this
                return eplist
    

    Lastly, take_guaranteed_victory will roll zero dice if there is an almost guaranteed victory (i.e. after rolling a zero, the player’s score is >= 100). I at first applied this function only in scenarios where there was an actual guaranteed victory. However, with some empirical testing, I was able to get a slightly better result after multiplying the roll zero dice score by two. I guess being conservative pays off near the end of a hog game.

    Anyway, I’m still looking for ways to improve the strategy. I really love this about programming. It’s the kind of problem that challenges oneself. There are bad and good answers, but the best answer is either unknown or elusive.

    Functioning Properly

    So as part of my grand plan to get back into coding, I’ve been helping out a friend with some assignments for school.  I thought at first that it would be easy, you know, basic algorithm type of work, object-oriented design, data structures, etc.  Much to my surprise, the homeworks have been really challenging.  Maybe my software foundation could be stronger, but it turns out that this intro-level programming class is teaching functional programming.  No wonder my friend was having so much trouble.  It would be frustratingly difficult to be taught this introduction to programming.  Maybe it speaks to my age, but object-oriented design and functions returning values just made more intuitive sense, or at least came to me more quickly.

    In summary, I’ve had to keep up with the readings and homework just to stay afloat.  I didn’t think I was that out of practice … In any case, this class is studying Python.  An interesting first choice.  Once I figured out why my friend was having so much trouble, I started to delve into the language myself.  And serendipitously, I’ve begun to understand why functional programming and the greater potential for abstraction is so powerful.  Take a look at this for instance:

    def accumulate(combiner, start, n, term):
        """Return the result of combining the first n terms in a sequence."""
        """ Combiner = a function
            term = a function
            start = base value to use to start the accumulation
            n = n terms to accumulate
        """
        k, result = 1, start
        while (k <= n):
            result = combiner(result, term(k))
            k = next(k)
        return result
    
    def summation_using_accumulate(n, term):
        """An implementation of summation using accumulate."""
        return accumulate(add, 0, n, term)
    
    def product_using_accumulate(n, term):
        """An implementation of product using accumulate."""
        return accumulate(mul, 1, n, term)
    

    This is pretty sick. You can define a universe of summation functions or product summation functions just by passing in type of function you want to execute. For example:

    def identity(x):
        """
        >>> summation_using_accumulate(5, identity)
        15
    
        >>> product_using_accumulate(4, identity)
        24
        """
        return x    
    
    

    By making either of these calls, you can add add the first n integers together, or multiply the first n integers together (i.e. factorial) and return the result. Really cool. I didn’t expect when I agreed to help out my friend that I would actually learn something new. I thought that at best, I would get a rough rehashing of my software fundamentals which would just help me remember some of the things I had forgotten. It turns out that I’m learning a new programming paradigm altogether. /mind blown.

    The Future is here

    OK, so at my job I’ve just learned about Java futures in the java.util.concurrency library.  They are pretty cool, but I’m new to them so I may be getting some things wrong.  I don’t need to instantiate huge numbers of threads anymore, but can simply use the Future object to handle it for me.  Future is an interface that contains methods to check if a computation is complete.  It kind of makes multithreading more simple.  Here’s a good tutorial: http://java.dzone.com/articles/javautilconcurrentfuture

    There’s a few things that are needed when working with Futures.

    1) ExecutorService or some kind of thread pooling

    I think futures still use threads, and the ExecutorService helps manage them.  So instantiate an ExecutorService (import java.util.concurrent.ExecutorService;) like this:

       private final ExecutorService pool = Executors.newSingleThreadExecutor();</pre>   

    2) An object of type runnable or callable that is submitted to the thread pool. This returns a Future.

    @Async
    private Future<String> getPreview(final ContentItem item) {
        return pool.submit(new Callable<String>() {
            @Override 
            public String call() {
                  return fbPreview.generateAndStorePreview(item);
            }    
        });
     }
    

    3) A Future object with a call of get(long timeout, TimeUnit unit)
    throws InterruptedException,
    ExecutionException,
    TimeoutException

    The get function, according to the javadoc states that it “Waits if necessary for at most the given time for the computation to complete, and then retrieves its result, if available.”

    Future<String> f = getPreview(item);
    
    try {
       String url = f.get(30000, TimeUnit.MILLISECONDS);
       System.out.println("Preview generated at " + url);
    } catch (TimeoutException te) {
       log.error("Facebook Preview generation for item: ? timed out. Continuing to error screen.", item.getId());
    } catch (ExecutionException ee) {
       log.error("Facebook Preview generation for item: ? erred in execution. Continuing to error screen.", item.getId()); 
    } catch (Exception e) {
       log.error("Facebook Preview generation for item: ? erred. Continuing to error screen.", item.getId());
    }
    
    

    So all in all, this is a way of doing some nifty threading without actually having to use threads and manage resources.