Author Archives: EricMustee

HASS V22 Beta 3

Download it here: http://www.ericmustee.com/uploads/HASS-V22-beta3.zip

This is a bug fix/change release:

  • Fixed a bug where agents would not move when dropping of pieces.
  • Intersections of trails now get the maximum value of their neighbors.
    • Intersections can only occur when a pheromone has three or more neighbors. Neighbors only exist orthogonally.
  • The x and y position for each pheromone is now computed correctly internally.

HASS V22 Beta 2

The runnable jar / source is available here:

http://www.ericmustee.com/uploads/hass-v22-beta2.zip

The changes are mostly internal:

  • With non-random trail leaving enabled (it is by default), agents will no longer leave trails for longer than they were holding their pieces.
  • Instead of having n different images for each n-sized puzzle, there is one image for each puzzle. Piece images are created from the image processor. This cut down on file size (~4MB to < 500 kb) and makes importing the project much easier.
  • The program attempts to load a “masterInput.json” file in the current directory and on the desktop automatically, so it is no longer necessary to use the command line to load input files. If no file is available, the default image/agent selection screen appears. The masterInput.json file is available in the zip above.

Bug fixes

  • Agents no longer wonder off screen while leaving trails due to the reverse movement array being initialized with the wrong size.

 

Slowing Down Java’s hashCode() for Strings

Java’s hashCode method for Strings has something very slightly concerning about it. Let’s look at the code for the hashCode() method for Strings:

public int hashCode() {
        int h = hash;
        if (h == 0) { // Let's call this Path A
            int off = offset; 
            char val[] = value;
            int len = count;
			
            for (int i = 0; i &lt; len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        // If the above code doesn't execute, we will call this Path B
        return h;
    }

There is something that bothers me about the way hashes are initially computed. Let’s say you have a large String of letters, and you want to hash it. You get a certain integer back after it is computed (Path A is taken), and all is fine and dandy. The next time you ask for the hash code, the value returned is the previously computed hash code, so we do not have to go through the computations a second time, as the hash is most likely going to not be zero (Hence path B is taken the second time, and the third, etc…). What happens if the number computed by the hash is zero? This is something that rarely happens, but it is possible for many strings to have a hashing function that evaluates to zero. In fact, it is even possible to take any arbitrary string, add seven characters (usually letters and numbers or symbols) to the end, and make the hashCode method evaluate to zero. Let’s take the string:

Bobby Likes Apples

The hashCode for the above is -1446827919. Let’s see if we can make it’s hashing function evaluate to zero. Consider the string:

Bobby Likes ApplesNAS3d1Q

This above string’s hashing function actually evaluates to zero. Try it out on your computer if you want, just print “Bobby Likes ApplesNAS3d1Q”.hashCode(). That means for any time the hashing function is called on the string “Bobby Likes ApplesNAS3d1Q”, the hash must be recomputed instead of returning the one already saved. This may not seem like a big deal, but the hashing function is supposed to be very quick. For large strings that evaluate to zero, this can actually make a gigantic difference in performance. As a test, I took the Wikipedia article on Hash Functions, and saved the page source to my computer. Then, I read it in as a string, and computed it’s hash function 10,000 times, and took the average time that it took to compute the hashcode. Here is my methodology below:

       File file = new File(&quot;HashFunction.htm&quot;);
        String input = &quot;&quot;;
        BufferedReader reader = null;
        try
        {
            reader = new BufferedReader(new FileReader(file));
        }
        catch (FileNotFoundException e)
        {
            e.printStackTrace();
        }
                
        StringBuilder builder = new StringBuilder();
        try
        {
            while ((s = reader.readLine()) != null)
            {
                builder.append(s+&quot;\n&quot;);
            }
        }
        catch (IOException e)
        {
            // You done messed up
            e.printStackTrace();
        }
        String article = builder.toString();

        // Find the average time this takes to hash
        long[] times = new long[10000];
        long beginTime = 0;
        
        for (int i = 0; i &lt; times.length;i++)
        {
            beginTime = System.nanoTime();
            article.hashCode();
            times[i]=System.nanoTime()-beginTime;
        }
        
        long sumOfTimes = 0;
        for (int i = 0; i &lt; times.length;i++)
        {
            sumOfTimes+=times[i];
        }
        
        float averageTime= (float)sumOfTimes/times.length;
        
        System.out.println(averageTime + &quot;ns&quot;);
        

On average, it took 567.7788ns to retrieve the hash for the (rather large) file loaded in using the BufferedReader. This is very quick Now, consider the way hashcode’s are computed for strings. Ultimately, the hashcode is computed as a large sum of overflowing integers as seen above when Path A is taken. We can get very precise control over the string’s hash value by manipulating the last seven characters of the string. Let’s see how the String, “Bobby Likes ApplesNAS3d1Q” was computed exactly anyway.

    // There may be more efficient ways of doing this, but 
    // this is pretty quick anyway.
    private int precomputedHashCode = 0;
   
    public int hashCode(char[] s, int n)
    {
        int sum = precomputedHashCode;
        
        for (int i = s.length-n; i &lt; s.length;i++)
        {
            int j = (int)s[i];
            for (int k = i; k &lt; s.length-1;k++)
            {
                j*=31;
            }
            
            sum+=j;
        }
        
        
        return sum;
    }
        
    // Returns a character array of the string with added letters to make the 
    // hashing function evaluate to zero.
    public char[] getNextNValuesToMakeHashCodeZero(String s, int n)
    {
        char startValue='M';
        
        char[] evaluation = new char[n+s.length()];
        boolean didEvaluation = false;
        for (int i = 0; i &lt; evaluation.length;i++)
        {
            if (i &lt; evaluation.length-n)
            {
                evaluation[i] = s.charAt(i);
            }
            else
            {
                if (!didEvaluation)
                {
                    didEvaluation = true;
                    precomputedHashCode = new String(evaluation).hashCode();
                }
                evaluation[i] = startValue;                
            }
        }
        
        for (int i = evaluation.length-n; i &lt; evaluation.length; i++)
        {
    
            boolean positive = (hashCode(evaluation,n)&gt;0);
            
            if (positive)
            {
                makeHashCodeNegativeAt(evaluation, i, n);
            }
            else
            {
                makeHashCodePositiveAt(evaluation, i, n);
                
            }
            
        }
        
        return evaluation;
    }
    
    
    // Increases the character at i until the hashcode is negative or zero. 
    public void makeHashCodeNegativeAt(char[] s, int i, int n)
    {
        while (hashCode(s,n) &gt; 0)
        {
            s[i]--;
        }
    }

    // Increases the character at i until the hashcode is positive or zero. 
    public void makeHashCodePositiveAt(char[] s, int i, int n)
    {

        while (hashCode(s,n) &lt; 0)
        {
            s[i]++;
        }
    }

What we do is if the hash code is negative, we increase the character at i until the hash code becomes positive or zero. If the hash code is positive, we decrease the character at i until the hash code is negative. Consider the following equation:

31n-1c0 + 31n-2c1 + ... + 314cn-5 + 313cn-4 + 312cn-3 + 311cn-2 + 310cn-1

The above is the hashing function expressed mathematically. However, since it overflows, all we have to do is effectively make the number divisible by (the maximum integer value * 2 + 2), or 4294967296. Doing that is easy since the manipulating the last 7 c values gets us the precision we need to effectively make the value equal to zero without having to introduce any strange characters. Also, since the value is a sum, we can pre-compute the hash code for the first n-7 values, and simply manipulate the characters in the last 7 values. The algorithm kind of reminds me of opening a combination lock: we manipulate each character until the hash code changes its sign or becomes zero. Each character we manipulate gets us more precision and thus closer to the hash code being zero. Now, let’s take the saved Wikipedia article, run the process on it, and see how long it takes to hash. We can take the article variable we bench marked before, and simply re-assign it.

article = new String(h.getNextNValuesToMakeHashCodeZero(article, 7));

According to my computer, the time it now took to get the hash code for the string was 158755.78ns. This is over 250 times slower! By adding just seven ordinary characters to the end of the string (they were “ODP5`/]” by the way), we made the average compute time much slower.

How can this be fixed? We can get much better performance in these bizarre cases by simply adding a boolean that represents whether the value has been hashed yet or not, rather than checking if the internal hash is zero. This code is run so frequently, it surprises me that there are even two separate variables (h and hash) in the hashCode() method to begin with. By replacing one of the integers (h) with a boolean hasBeenHashed, we can save a lot of time in these bizarre circumstances.

A Silly Idea About Time

Many of us set our clocks forward so that we are on time. This makes us think that we are going to be late, but end up pleasantly surprised when we get to wherever we are going to on time. Or so it goes until you get used to the fact that your clock is five minutes fast. In the end, you can accurately predict the time.

In order to solve this problem, I came up with a silly idea: what if you couldn’t accurately tell the time? What if you could only have a rough idea of what time is? Eventually, I ended up creating a clock that randomizes the time based on your specifications.The key here is that the clock is semi-accurate. If you were to randomize all the times that could be generated by the clock, the mean would be the current time. The distribution of times is flat between two bounds, meaning that each time within the distribution is equally likely to be chosen. The project is available for your viewing pleasure at: http://www.ericmustee.com/Clock

Below is a random clock running at about 6:18 PM. It is allowed to have a deviation of up 2 minutes from the actual time:

It's a feature not a bug

This clock is NOT broken!

There are a few advantages of this randomized clock I can think of over a fast regular clock: it forces you to prepare for the worst. This is a clock you simply cannot get used to. Say you have lived with this clock for a month. If you have access to no other clocks, you would have to pretend that the time is always fast, otherwise you could miss out on some opportunity. However, you may occasionally be pleasantly surprised when you find you not only have arrived on time, but you have arrived early! This is what makes a clock like this neat: if you pretend a randomized clock is always fast, you will at worst never be late, and you will sometimes be early. Following this type of clock in this way is a bit of a commitment however.

Here are some additional features I implemented:

Lots of different options for a clock here

An Options Page

You can choose lots of things here:

  • How often the clock randomizes
  • The maximum time between now and the randomly generated time
  • Analog/Digital/Both
  • The movement of the seconds hand can be smooth/granular
    The FPS recorder was limited to 20FPS, so it's even SMOOTHER in real life. You should go view the actual clock at http://www.ericmustee.com/Clock An extremely cinematic experience
  • Any color of your choice!
Colorful Clocks! I really like these colors and shapes!

Different Colors

In order to do this, I took it upon myself to look into the HTML5 canvas and cookies. I’ve been wanting to play with these for a while, and I enjoyed them. I quickly hacked together the clock/settings page in two afternoons, and I am pretty impressed with the simplicity and flexibility behind the canvas element.

There are some small issues with the clock: rendering issues occur if the aspect ratio is set too high, the seconds hand blends in with the background too much if you select red as a color, and some themes do not have a high enough contrast between the clock/text and the background. A lot of this project feels held together with duck tape and paperclips. However these issues are things that I can think of fixes for. If I had unlimited time, I would go about fixing everything, but I have things like topology homework. Again, you can view the clock at http://www.ericmustee.com/Clock

Is this a better solution than just setting your clock faster? Who knows, it might be. If you are strict about following it, it probably is better. For what I gather,this is either a terrible idea or a great idea based on the type of person that uses it. In any case, it’s better than the broken clock this is going to replace in my living room, as this clock is likely to be close to correct more than twice a day.

HASS V22 Beta

There are some very cool new features added to HASS revision 22. I am considering this a beta release because the features have not been fully tested. All of the changes added can be disabled by default, to remain compatible with older tests/models. The changes are enabled by default and can be disabled by adding some lines to an existing input file. The source / executable may be found here: http://www.ericmustee.com/uploads/hass-v22-beta.zip

Here are the list of changes (with screenshots). The source/executable can be found here, along with a new input file.

  • Fancy Edge Shapes

    fancy_edge_shapes

    • There are 10 different edge shapes currently supported for the 10 different theoretical shapes
    • For simplicities sake, only two are currently implemented (curvy and triangular edge shapes).
    • Done dynamically: To update edge shapes, simply place new shape images in jar.
    • Holes are punched onto existing shapes in cookie-cutter fashion
    • Tabs are added by taking a copy of the next existing piece
    • Works even for wrapped puzzles
    • Disable with “fancyEdgeShapes”: false in input file.
  • Pheromone Trails are made based on the path taken, and are not created randomly

    backwards_a

    • A circular array is used for keeping track of the last n movements, where n is a natural number specified in the input file as “pheromoneTrailLength”
    • The old style random trails may be used by using “randomTrails”: true in the input file.
  • Frame rate slider
    • Can be used to slow simulation.
    • For extra cinematic effects, turn the FPS to 24 (if you dare…).
  • Changes on how long already existing trails get increased for
    • By default, trails now get reset to the initial time limit when an agent leaves a trail over an already existing trail.
      • This prevents a checkerboard pattern that was common after trails decayed.
    • The old behavior can be retrieved by using “resetTrailToInitial”: false in the input file.

Emergent: A Card Game By Daniel Palmer, Now With Networking Support?

Emergent is a card game created by my advisor, Dr. Daniel Palmer. It consists of players placing colored shapes on a board while maintaining certain constraints. The game is cooperative, meaning that you must work together as a team in order to win. It has been blogged about before by Dr. David King here, where he explains the game and his thoughts and feelings. In this post, I will talk about the work I put into digitizing the game.

In the game, there is a 4×4 grid, and there are 16 card players may place on the board, made from four shapes and four colors. Each card has three copies. A typical constraint may consist of “you cannot place any cards in that row,” or “you must place all green squares to the left of the center,” or “there are no yellow diamonds allowed.” Each player gets a set of constraints that they must maintain. The catch is that players may not tell other players their constraints. Because of this cut of communication, players propose two actions to the other players and a vote occurs. I have included screenshots of a work in progress digitized version I have created:

The Game's Beginning State

The Game’s Beginning State from Eric’s perspective

The Games Beginning State from User 2's perspective

The Games Beginning State from User 2’s perspective

There are two separate areas on the screen above: the card supply on the left, and the playing field on the right. Players move cards from the supply to the field when playing. Above, we have two players playing in separate sessions perhaps across separate devices. Eric has three constraints: all squares have to be to the right of the center, the number of diamonds has to equal the number of blue shapes on the board, and there cannot be ANY green spheres at all. User 2 has two constraints: all the blue squares must touch a red circle (and vice versa), and there cannot be any cards in the top row. In order to win, both 12 cards must be placed on the board and all user’s constraints must be satisfied. When pieces are removed, they are gone forever, so it is very possible and likely that players will lose. The card game (the non-digital implementation) seems very balanced so far, and takes a good amount of thought to complete. Because of the lack of communication, players form emergent behavior on how to place pieces not unlike how behaviors emerge in swarms. This is where the name gets its name from.

Throughout the past few weeks, I have been working on/off on digitizing the game to make it playable across the Internet. This is an interesting game to digitize because there are a lot of things that may happen in a game that are hard to keep track of. A digital version of the game would allow for more gameplay, and less setting and organizing all the pieces. The first stage will involve creating a simple graphical Java application that can connect to a central server and play a game with others. This stage is already well under progress. The next step may consist of game created with Unity that will allow players to play against each other on a variety of platforms, including mobile devices.

Currently, my digital version of the game is in a pretty rough state with placeholder graphics, no sound, etc…, but it is playable nonetheless. Much work has to be done before I would consider this version ready for a public beta. A lot of things have gone well so far: A working server browser has been implemented, games can be created with an arbitrary amount of players (but it is capped at 6 for now), and constraints can be randomly generated and sent to players. Taking turns works great. Players can only propose valid moves. A working server is up: games are all hosted on a cloud server, so player’s do not have to worry about opening ports to host a game, etc…

Now onto what has not been implemented, but has a high priority:

  • Many constraints (such as all card x must be to the left of card y, all diamonds must be in row 3, the list goes on, etc…)
  • A server-side winning condition
  • A way to go back to the main menu
  • Basic documentation/explanations on what to do when
  • Better Visuals
  • Security of the central server to prevent hacking the game board
  • And much more!

Like I said, the digital version of the game I am working on still needs more work, and there will be progress updates as a part of my blog. The card game is ready for prime time, and there should be a Kickstarter by Dr. Daniel Palmer sometime this year in which I will be supporting.