[1] Q_k = Q_k-1 + (x_k – A_k-1)(x_k – A_k) where x_k is the kth element in the set and A_k is the mean of the first kth numbers.

The standard deviation squared of the first n numbers of a set is Q_n / n.

From this, it is easy to compute the standard deviation for a growing set of numbers without having to read through all numbers in the set a second time.  Recomputing the mean requires only an addition of (x_k – A_k-1) / k to the prior mean of A_k-1 — so this does not require looking back through all the elements of the set.

Therefore recomputing Q does not require looking back through all the elements in the set since it only depends on x_k, Q_k-1, A_k, and A_k-1.  We’ve deduced that A_k can be derived from A_k-1 without having to look back through all elements of the set, so new values of Q can be computed likewise.

Now how would one rapidly calculate the standard deviation if the set was not growing, but rather was a moving window of fixed length?  This is useful in finance or science when we want to keep an up to date standard deviation for a set of constant size with numbers changing one at a time.  For example, in finance, when calculating Bollinger Bands, we want to always know the standard deviation in stock prices for the last 20 periods.  So the set of stock prices isn’t growing in our set, instead it is of constant size, removing the oldest stock price and replacing it with the latest one at every tick interval.  We can adapt formula [1] above for growing sets to meet our needs here by realizing that a moving window is a set that grows by one at one end, and shrinks by one at the other.

Without loss of generality, let’s assume the beginning of our window is element a of a given set (and we will be discarding the a-th element when the window moves by one), the second element is b, the last element of the window is c, and the element to be added is d.  We are moving from a window of data that encompasses elements a through c, to a window of data one over that encompasses elements b through d.  Our window length is constant, that is d – b = c – a.

So if our data set looks like … 1, 2, 3, 5, 8, 11, 13 … and our period is 4, the a-th element might have a value of 2, b-th is 3, c-th 8 and d-th 11.  We moved from a window looking at [2, 3, 5, 8] to [3, 5, 8, 11].

If we grow our set from b to c to b to d by adding the d-th element, the Q formula would look like the following:

[2] Q_bd = Q_bc + (x_d – A_bc)(x_d – A_bd)

Now this formula looks the same as growing a set from b to c to a to c by adding the a-th element:

[3] Q_ac = Q_bc + (x_a – A_bc)(x_a – A_ac)

Rearranging [3], we find out that shrinking a set, in this case, from a to c to b to c, is simply reducing Q by the product of terms on the RHS:

[4] Q_bc = Q_ac – (x_a – A_bc)(x_a – A_ac)

Substituting [4] into [2], we find out how to get Q (and consequently the standard deviation) for the new window b to d, from the Q (or standard deviation) of our old window a to c:

[5] Q_bd = Q_ac – (x_a – A_bc)(x_a – A_ac) + (x_d – A_bc)(x_d – A_bd)

We arrive at [5], a formula where we can compute new values of Q for a moving window (and we can easily calculate standard deviation from that) without having to go through a second pass of all numbers in the set.  The derivation is simple after realizing a moving window is simply a set that grows and shrinks by one element.

Here’s my list so far and I’ll update it as it grows:

Stereo_Chart
NathDan0615
Cursive_Tiger
BCCFMPTN
hunter_gunter

As the title states, if you use setcookie() with $expire set and $domain not set, then IE may simply let the cookie expire, ignoring the value you put in $expire. Furthermore, IE may request the page a second time, as if it didn’t understand the cookie set directive and decided to start all over. I couldn’t reproduce this in Firefox, Chrome, Safari, or any other browser, and oddly enough, I could not reproduce this using inPrivate browsing in IE. In other words, all of the examples below work in other browsers as you would expect them to. IE is the lone failure on the setcookie example #2 below.

PHP’s setcookie() syntax:

bool setcookie ( string $name [, string $value
  [, int $expire = 0 [, string $path [, string $domain
  [, bool $secure = false [, bool $httponly = false ]]]]]] )

1. Cookie successfully stored in IE, but expires at the end of the browser session:

setcookie(session_name(), session_id(), 0, '/');

2. The following blows away the cookie in IE:

setcookie(session_name(), session_id(), time() + 60 * 60 * 24, '/');

3. To successfully store the cookie in IE and have an expiry date, we must supply the $domain to setcookie():

setcookie(session_name(), session_id(),
  time() + 60 * 60 * 24, '/', '.chrislo.ca');

Some solutions on the net suggested that the time needed to be bigger in example #2 due to difference in GMT-ness of the time provided, but no matter how large the expiry time is set, the cookie still gets blown away in IE. Appending the domain magically fixed it.

The dynamics in Big 2 make programming AI for it an interesting problem.  The usual “game tree” approach when solving games like Chess or Reversi can still somewhat be applied.  However, like programming optimal AI for backgammon, there is an element of the unknown to be included.  We know the cards we hold in our hand, but how might they be distributed amongst the other concealed hands?

There are many other factors that human players have to their advantage.  They can spot and exploit players’ weaknesses and habits, bluff, and come to logical conclusions putting those two weapons together.

Emulating this behaviour and analyzing a fairly large “game tree” makes designing a fast, yet effective AI for Big 2 a challenge.  For AI that is controlled by the server (for obvious reasons it is server-side and not client-side), we have to be careful too to not take up many cycles per AI decision.  The assumption is that multiple computer players will be running at once, so for a multiplayer online gaming site, CPU cycles for AI should be minimal.

So instead of a game tree where we guess what cards will be played (and where they lie) and determine the optimal play by looking ahead, the approach taken is one giant heuristic: let’s calculate the expected value of a play simply from the cards we see and the cards we did not see up until the play.  Ultimately the goal of Big 2 is to get rid of all your cards, so we simplify the calculation by estimating how many cards will be shedded by playing a certain hand.

The process is simple: when it’s the computers turn, what are all the possible plays we have?  If a single was played, we can play another single, or pass.  If the computer is leading, then anything is possible, but passing.  Whichever the case, we have a small finite set of moves.  Now for each move, how will our hand look like after?  What will our possible plays be?  To answer this problem, we treat it as if the computer is leading a hand, and determine the set of all plays regardless if we are approached with a single, double, triple or poker hand.  Now, given the cards that are concealed in everyone else’s hand (and we know the exact set of cards, since the computer easily tracks what cards have already been played, we just don’t know how these cards are distributed — we could guess and assign probabilities, but for purposes of efficiency, we opt not to) let’s calculate how many cards we expect to shed by the end of the game.  If one of our plays in our “future” hand contains a poker hand, how likely is it going to beat all the other possible poker hands out there?  If it beats all the other possible poker hands (or a high percentage of them), how likely are we even going to be seeing a poker hand in play?  That factor is nil if the remaining players have 5 or less cards each.

Anyway, just by answering those questions above you have a relatively good gauge on expected value, and interestingly enough figuring out these probabilities is fast, by applying some good finite mathematics formulae.  One thing that human players do well is to have a game plan to run out their cards, waiting for a deuce to be played to promote one of their deuces, giving them an unbeatable exit plan.  To emulate this on the AI side, we simply do a small probability assignment ourselves: when we know a certain line of play has hands that can be unbeaten (or close to unbeaten), we can boost the probability to 1 (or close to 1) for a weaker hand that had no chance of being played unless the computer leads it itself.

So with the original probabilities calculated and the “fudging” of probabilities to emulate creating a “game plan” with a certain line of play, we have a rather decent AI for Big 2 that can give even the most seasoned players a challenge.  Although the computer still does funny stuff from time to time, it makes up for its shortcomings by doing pinpoint probability calculations quickly, and also has the inhuman ability to figure out exactly what cards are left, to accurately determine the strength of its hand.

So how does it play?  You be the judge!  I can barely scrape of my 25% share of 1st place finishes against the computer.  Not bad for a computer that reacts less than 250ms per move.

“Background image must be the same dimensions as the canvas.”

In case you are looking for a workaround for Processing.js background function that forces you to scale your background image, try this trick to make your browser do the scaling for you.

Set the CSS background for the canvas element to your image, and use “cover” or “contain” to stretch your background to fit the canvas:

<canvas style="background: url(<!-- your background image path -->);
  background-size: cover"></canvas>

In your JS, you can set Processing’s background opacity to zero alpha (transparent), or simply use clearRect without the help from Processing:

background(0, 0);
// OR
document.getElementById('canvas').getContext('2d')
  .clearRect(/* x */, /* y */, /* w */, /* h */);

Of course you can dynamically set the CSS of the canvas in your script whenever you feel like changing your background image.

The solution, which may be difficult to find on their documentation, or even elsewhere on the Internet, is to call FB.init at your leisure. Thus, if one of your AJAX served pages has a login button, it should make the call to FB.init itself. Combining a code snippet for determining if the remote script has been fully loaded with this approach provides a slightly more robust solution that won’t throw a JS error:

var stFBId = 'facebook-jssdk';
var fnFBInit =
  function()
  {
    FB.init({
      appId      : /* YOUR APP ID */,
      status     : true,
      cookie     : true,
      xfbml      : true,
      oauth      : true,
    });
    FB.Event.subscribe('auth.login', function(response) {
      window.location = /* URL after login */;
    });
    FB.Event.subscribe('auth.logout', function(response) {
      window.location = /* URL after logout */;
    });
  };
var fInitReady = false;

(function ()
{
  function loadScript(stUrl, fnCallback)
  {
    var script = document.createElement("script");
    script.type = "text/javascript";

    if (script.readyState)
    {
      script.onreadystatechange = function()
      {
        if (script.readyState == "loaded"
            || script.readyState == "complete")
        {
          script.onreadystatechange = null;
          fnCallback();
        }
      };
    }
    else
    {
      script.onload = function()
      {
        fnCallback();
      };
    }

    script.src = stUrl;
    script.id = stFBId;
    script.async = true;
    document.getElementsByTagName('head')[0].appendChild(script);
  }

  if (!(document.getElementById(stFBId)))
  {
    loadScript('//connect.facebook.net/en_US/all.js',
    function()
    {
      fInitReady = true;
      fnFBInit();
    });
  }
})();

Finally, in any code that is served asynchronously that includes the FB login divs, you need to simply include the call to FB.init:

<div id="fb-root"></div>
<div class="login-button">Log in with Facebook</div>
<script>
if (fInitReady)
  fnFBInit();
</script>

var fonts = {};

processing.setup = function()
{
  var fontList = processing.PFont.list();

  if (jQuery.inArray('sans-serif', fontList) >= 0)
  {
    fonts['sans-serif'] =
      {'12': pr.createFont('sans-serif', 12, true)};
  }
  else
  {
    // Error
  }
}

// Somewhere else in your code ...
processing.textFont(fonts['sans-serif']['12']);
processing.text("Hello world", 10, 10);

http://giveupandusetables.com/

Why?  At some point in time I had the basics working (in all browsers!), but then I tried to add another div centered in the fluid width column, and that became the new seemingly impossible task.  I can only conclude that no clean CSS can evolve from solving this.  Tables will always look right across all browsers (IE6 included), and will be much easier to manage to get the columns right.  It makes centering the div correctly in the fluid column trivial.  Sad how after several hours, I just ended up with this:

HTML:

<table id=container>
  <tr>
    <td id=sidebar>
    </td>
    <td id=content>
    </td>
  </tr>
</table>

CSS:

#container
{
  width: 70%;
  margin-top: 0;
  margin-left: auto;
  margin-right: auto;
  margin-bottom: 0;
  padding: 0;
  border-top: 0;
  border-left: 1px solid #000;
  border-right: 1px solid #000;
  border-bottom: 0;
}

#container td
{
  vertical-align: top;
  padding: 0;
  margin: 0;
}

#sidebar
{
  width: 180px;
  border-right: 1px solid #ddd;
}

Suppose you set up a remote Mercurial repository, cloned it locally via SSH to your machine and then wished to push your changes to the remote repo.

The commands you ran may look something like this:

hg clone ssh://remoteusername@remoteaddr//dir/to/repo/
[... make some changes ...]
hg pull
hg update
[... make some changes ...]
hg commit [...]
hg push [ssh://remoteusername@remoteaddr//dir/to/repo/]

On the push, if you see:

remote: abort: could not lock repository /dir/to/repo/: Permission denied

you’ll want to check that “remoteusername” has write permissions to not just the “.hg” directory in /dir/to/repo/, but also every file and directory in it.  If not, you’ll want to add to the owner group or change the owner of the .hg directory and its contents recursively to “remoteusername” (e.g. using “chown -R”).  For obvious reasons, you don’t want to make the directory and its contents globally writable (e.g. don’t “chmod 777″).

I got into this bind by initializing the remote repository under sudo such that the owner was root, and not the username I was using for SSH.

An Argument for Pressing Enter Rather Than Backspace

In Boggle Bash, there is no penalty for entering an invalid word.  If in your spree of typing you made a typo at the very beginning of a word, I would recommend NOT backspacing to correct the error if you have already typed most of the word.  Hit Enter to enter what you have anyway, and start over.  Who knows, the word you accidentally entered may actually be a legitimate one!

Note: Optimally you’d want to do this if the number of keystrokes to hit Enter and retype the letters up to your typo is less than the number of times you’d have to hit backspace (although one could argue the number can be slightly more since it is generally faster to hit Enter and other keys than hitting backspace the same number of times in succession; also, since the errant word may actually be a legitimate one, you don’t want to backspace a word that would have scored).

An Argument to Keep Typing Rather Than Backspace

Suppose the word you were thinking of doesn’t actually connect on the board.  In the middle of typing the word, Boggle Bash will give you an audio clue that the path does not exist upon entering the disjoint letter.  Again, I would suggest not to get rattled and start backspacing, but to simply follow through with the word you wanted to enter, and just hit Enter (again your errant word might actually score!).

If you want to keep it simple, I would suggest the following general guideline: never press backspace more than twice in a row.  Either hit Enter or keep typing anyway.

Keeping a Mental Queue

As illustrated in the previous post about typing, it is faster to simply think of words than typing those words.  Use the time it takes you to type to continue analyzing the board for words.  You will want to look ahead, building a mental queue of words you want to enter, and thus make typing a background task.  There is a limit on how big of a queue you can manage (depending on your short term memory), but any time you can focus less on typing and more on identifying words, clusters and high scoring point regions, the better.  This concept will become clearer when clusters and suffixes are discussed in future posts.

Notes on Other Input Methods When You Can`t Use the Keyboard

If you’re playing a version of Boggle where keyboard input is not allowed (e.g. the actual board game, or Zynga Scramble on the iPhone/iPad), I do have a few suggestions to offer based on my experience.

Writing down words in the actual board game is by far the slowest input method.  You will almost think many multiple words per minute more than you can write.   At some point in time early in the round you will want to give the entire board a quick analysis to identify the point-rich regions and clusters.  Identify some easy words at the beginning of the round, and while you are writing those words down, do the scan of the entire board and start keeping a mental queue.  Use some of the tips already described in this post: if a word doesn’t exist or is invalid, don’t erase letters, either stop writing the word or continue writing what you wanted, and move on.

Note that in Boggle Bash, scanning the entire board early in the round is less of a necessity.  If you manage to type 80+ words per minute, usually the time it takes to enter those first few words will not buy you enough time to scan the entire board.  It is usually sufficient to simply gravitate towards the obvious suffixes and general higher scoring regions, but not necessarily the highest scoring regions.  Usually there will be sufficient time to traverse the board and naturally find the highest scoring region.

On a further note, if you are playing a version where you cannot duplicate a word already entered by another player, it actually becomes more important to do the scan in the early part of the round.  Yahoo! Games Word Racer is one such variation of the game.  I would suggest here NOT starting in the upper-left corner: start typing small clusters in another region, and use that time to do a quick scan of the entire board.  Immediately attack the suffixes and higher scoring regions.  There are many other suggestions I have for variants such as Word Racer, but they are out of scope for this guide.

For touch devices such as IPad or IPhones, word entry should be done with a dragging motion between letters and not a touch-typing motion.  In the case of Zynga Scramble, a dragging motion automatically enters the word once your finger leaves the screen, whereas if you were selecting one letter at a time, you have to perform one more “stroke” to enter the word (it also takes longer to repeatedly having to lift and press your finger for each letter).  The finger-drag method can actually be just as fast as typing (I would estimate my speed around 60 words per minute), so essentially most of what has been discussed in this guide applies equally for touch devices.

TL;DR

Don’t use backspace to correct typos at the beginning of words.

Don’t worry if the word you think of does not even connect on the board.  Just type it in anyway.