A View Inside My Head

Jason's Random Thoughts of Interest

NAVIGATION - SEARCH

Knave 21 (Blackjack): The Fairness of Random Cards

Blackjack is one of my favorite games in the casino.  I'm a casual player, and certainly not an advantage player by any means.  To help me drill basic strategy, especially for things like soft hands and splits, I decided to write a version of Blackjack for Windows 8 and make it a game that *I* would like to play.  Since I'm not a high-roller, I also wanted to simulate the bankroll that casual players might use in an actual casino: $500 buy in at a $10 minimum table.

Thus, Knave 21 (soon to be renamed Knave Blackjack) was born after a couple of hundred hours of work in the evenings and weekends (the version in the Windows Store represents the third rewrite, and a version currently in development has undergone major refactoring recently as I prepare to add more features in the near future).  It's been a labor of love, and I hope that the attention to detail reveals that.  I've received a lot of positive feedback, and, recently, some negative feedback as well (which prompted this blog post).

One thing that every card game author likely struggles with is how to randomize the card selection so that it's fair to the player.  Knave 21 has the concept of a shoe, which is 2-6 decks of cards that are shuffled together.  It penetrates much deeper than a real casino (the reshuffle automatically occurs when 12 cards remain in the shoe), but the randomness of the deck is very dependent on whatever pseudo-random number generator can be coded in JavaScript.

Instead of relying on JavaScript's Math.random() function, Knave 21 utilizes the Alea library by Johannes Baagøe to provide a better distribution of random numbers.  And, since the shoe is serialized and saved to roaming storage (so you can resume a game on another computer), I didn't want to pre-shuffle the shoe.  Instead, a random card is selected and removed from the shoe upon demand.  If someone were to view the roaming state data, they could see what cards were left in the shoe, but not what the next card would be.  

More importantly (and in response to some recent negative feedback), the game doesn't care what cards have been played or how much you are betting when determining the next card - it simply picks a random number and that's the card that is drawn.  

I'm very concerned about Knave 21's reputation, especially since I have paying customers now that the app is listed in the Windows Store.  In the interest of openness, the code for the shoe implementation follows.  Note the "nextCard" function for the RNG implementation.

Knave.Shoe = (function (Alea, undefined) {

    var shoe = function (decks) {
        this.cards = [];

        for (var d = 0; d < decks; d++) {
            for (var s = 0; s < 4; s++) {
                for (var r = 0; r < 13; r++) {
                    this.cards.push(new Knave.Card("A23456789TJQK".charAt(r), "HDCS".charAt(s), true));
                }
            }
        }
    };

    shoe.prototype = {
        nextCard: function (facedown) {
            var random = new Alea();
            var index = random.uint32() % this.cards.length;
            
            var c = this.cards.splice(index, 1);

            if (c.length === 0)
                return undefined;

            var ret = c[0];

            if (facedown !== undefined)
                ret.facedown(facedown);

            return ret;
        },
        remaining: function () {
            return this.cards.length;
        }
    }

    return shoe;
})(Alea);

 

Metro: Introducing the Local and Web Contexts

I recently recorded an episode of The Tablet Show with Carl Franklin and Richard Campbell (it will be published at the end of July 2012) where I rambled on about discussed different concepts that are needed to construct a Geospatial Metro-style application.  Since I seem to do more web development these days than anything else, I naturally approached this from a HTML/JavaScript developer's point of view.

The geospatial part is really irrelevant.  I included it because I could speak to the subject matter, and it permitted me to establish some constraints around the otherwise huge topic of writing a Metro-style application.  From the web developer's point of view, though, there are existing JavaScript-based APIs that the developer will be interested in using while writing the Metro application (i.e., jQuery and OpenLayers comes to mind).  

Now, when you write a Metro application using .NET or C++, there's a compilation step that takes place to compile the source code into an executable (EXE and/or DLL).  The executable and any dependencies are packaged into an application package (an .appx file), which is really just a renamed .zip file that contains the files, a manifest, and cryptographic information to ensure that the contents were not tampered with.  Aside from WinRT libraries, everything that is needed to run the application must be included in the package.

HTML/JavaScript Metro applications, by contrast, actually run as a web page inside of an Internet Explorer 10 process.  The source files are stored within the application package, much as they would be on a web server.  But, instead of downloading HTML, JavaScript, CSS, and images from a web server across a network, the resources are retrieved from the .appx file on the user's hard drive (much faster load times, and the application is still accessible when there is no network connectivity).

Metro-style applications built using HTML/JavaScript still have access to the Windows Runtime and can do just about anything that their compiled-counterparts can.  In order to allow such privileged access, however, certain common practices in the web world had to be explicitly prohibited.  Specifically, anything that attempts to inject HTML or script into the DOM of a Metro-style application will result in an exception (to prevent third-party script injection attacks).  More details can be found here: http://msdn.microsoft.com/en-us/library/windows/apps/hh465380.aspx

This safe HTML filtering causes a problem with a lot of existing JavaScript libraries.  So, how is a developer supposed to use such a library inside of a Metro application?  It turns out that in the case of Metro-style applications, Internet Explorer 10 will assume two different personalities: Local context and Web context.  

The application bootstraps into the Local context.  This mode is what you'll find most people talking about when they discuss building Metro-style applications using HTML/JavaScript because it has full access to WinJS (and WinRT). Local context URIs start with the "ms-appx" protocol, and the resources must exist in the .appx file.

The Web context is totally isolated from the Local context, and cannot access WinRT and a lot of other things that the Local context can.  As a result, code running in the Web context behaves pretty much like a normal web application today.  This means that developers can continue using those existing JavaScript libraries that don't work in the Local context!

Web context URIs start with the "ms-appx-web" protocol (if the resource exists in the .appx file), or the "http" protocol (if the resource is to be loaded from a web server).  Specific differences between Local and Web contexts is documented here: http://msdn.microsoft.com/en-us/library/windows/apps/hh465373.aspx

In practice, an IFRAME is used to introduce Web context content into a Metro application.  In this way, the outermost web page runs in the Local context, while the IFRAME's content runs in the Web context.  It's possible for the IFRAME to be styled to fill the entire screen, if needed (and the outermost web page becomes just a thin hosting shell).

A common scenario is that data in the Local context will need to be sent to the web context (and vice versa).  For instance, code running in the Local context may listen for events fired by the device's Compass sensor.  When a new directional heading is established, the Local context code will need to send the new data to the Web context code for further processing.

HTML5 defines a means to do this cross-document communication using the window.postMessage() function.  In the case of the new Compass reading, the Local context code would post a message to the IFRAME.  The Web context code would need to register an event listener for the window's "message" event.

The messages themselves are strings, and the developer is left with the task of implementing a data protocol.  JavaScript Object Notation (JSON) will often be used to serialize JavaScript object to a string representation for the purpose of transferring across the contexts (the sending side will use JSON.stringify() to serialize the object, while the receiving side will use JSON.parse() to deserialize it).

The hybrid Local-Web context architecture allows an existing HTML5/JavaScript web application to be converted into a Metro-style application without the need to modify third-party JavaScript libraries.  Though, even after such a conversion, there will still likely be some clean-up needed to make the existing application behave more like a Metro-style application, such as implementing the App Bar for commands, and taking advantage of the Search and Sharing contracts.  But, the reward for going through this effort is an application that can then be distributed or offered for sale on the Windows Store to an audience of millions of potential users.

Want to try these things out today before Windows 8 launches this Fall?  Release candidates are available for free:

Windows 8 Download: http://aka.ms/JenWin8

Visual Studio 2012 Download: http://aka.ms/JenVS2012

Migrating to BlogEngine.NET

I've been wanting to migrate this blog to a different blogging engine for a while now.  So, the other day, while recording an episode of The Tablet Show, Richard Campbell asked me "Did you know that your blog is down?"  

Well, it seems that a recent security patch broke something about SubText as I had it set up on my hosting provider. This became my opportunity to finally spend some time on this tired site!

Entity Framework Spatial: A Real World Example

Background

From the Wikipedia article, Leadership in Energy and Environmental Design (LEED) is described as “an internationally recognized green building certification system, providing third-party verification that a building or community was designed and built using strategies intended to improve performance in metrics such as energy savings, water efficiency, CO2 emissions reduction, improved indoor environmental quality, and stewardship of resources and sensitivity to their impacts.”

In my own words, LEED is a certification system that awards points for following certain environmentally-friendly practices when constructing a building. In the end, a building can be qualify for one of four different levels of certifications, based on the number of points: Certified, Silver, Gold, Platinum. There are often tax benefits associated with having a LEED certification, and many new government buildings (especially Federal) are required to be LEED certified.

Two points in particular (out of of 100, or so) from the LEED checklist are related to geospatial data. One point is awarded if at least 20% of the building materials (by cost) used in construction were manufactured within 500 miles of the job site. A second point is awarded if 10% of the raw materials of those building materials were extracted, harvested, or recovered within 500 miles of the job site.

As a window glass manufacturer, Tempuri Glass is often asked to provide data about its products that are being considered for use in construction. Tempuri Glass may have a certain advantage over its competitors if it can quickly show that its products would count towards these two points for any arbitrary job site.

Data

Tempuri is a simple organization, making only a single type of product (Soda Lime glass) that is then cut into different sizes per order. Therefore, regardless of how many different sized glass panes are produced by a given facility, the ingredients for that glass is the same. The formulas used will be different between facilities, though, since the raw ingredients will be sourced from different locations, and adjustments may need to be made to the ratios due to environmental factors (things like: elevation, temperature, humidity, etc).

So, for our data model, we just need to know where each facility is, and then the formula used to make the glass at that facility (including the ingredients of that formula and the location where they were harvested from).

a.EF_Diagram

Within the data store, the [Geocode] columns of the Facility and FormulaComponent tables use the SQL Server geography type. This is useful for the large-scale/real-world distance calculations that Tempuri Glass needs to perform, since the way that you calculate distance on an sphere or ellipsoid (like the Earth) is vastly different than on a flat map.

In the Entity Framework model (using the June 2011 CTP), the SQL Server geography types are mapped as the new System.Data.Spatial.DbGeography type. This makes the geospatial data a first class citizen of our data model, and not just a castable opaque BLOB, as was the case in the past.

Geospatial data can take on many forms, including Points, Line Strings, Polygons, and collections of these shapes. Even though it’s not apparent from the data model, our [Geocode] data will contain only Points (i.e., a single Latitude/Longitude pair). Likewise, a job site will be specified as a single Point, though there is no hard requirement for this because distance can still be calculated between a Polygon and a Point with no coding change required.

Facility Sample Data

FacilityID

FacilityName

City

State

Geocode

1

Greenfield, IA

Greenfield

IA

POINT (-94.4547843933106 41.3151755156904)

2

Spring Green, WI

Spring Green

WI

POINT (-90.053981 43.17431)

3

Tomah, WI

Tomah

WI

POINT (-90.477058 43.989319)

4

Fremont, IN

Fremont

IN

POINT (-84.9314403533936 41.7186070559443)

5

Fargo, ND

Fargo

ND

POINT (-96.8667125701904 46.8985894795683)

6

Waxahachie, TX

Waxahachie

TX

POINT (-96.8427014350891 32.4424403136322)

7

Hood River, OR

Hood River

OR

POINT (-121.51526927948 45.630620334868)

8

Vinton, VA

Vinton

VA

POINT (-79.863876 37.263329)

9

Casa Grande, AZ

Casa Grande

AZ

POINT (-111.78155422210693 32.882073958767954)

10

Mountain Top, PA

Mountain Top

PA

POINT (-75.896477 41.141327)

11

Winlock, WA

Winlock

WA

POINT (-122.926218509674 46.5449155194259)

12

Durant, OK

Durant

OK

POINT (-96.4133548736572 34.0001619910696)

13

Mooresville, NC

Mooresville

NC

POINT (-80.7865476608277 35.6316281732984)

 

FormulaComponent Sample Data

FormulaComponentID

Name

Percentage

SourceLocation

Geocode

14

Limestone

13

Genola, UT

POINT (-111.808204650879 40.0098667779887)

1

Silica Sand

75

Houck, AZ

POINT (-109.241695404053 35.2062151838369)

27

Soda Ash

12

Trona, CA

POINT (-117.311668395996 35.6955040738332)

15

Limestone

13

Genola, UT

POINT (-111.808204650879 40.0098667779887)

2

Silica Sand

75

Houck, AZ

POINT (-109.241695404053 35.2062151838369)

28

Soda Ash

12

Trona, CA

POINT (-117.311668395996 35.6955040738332)

16

Limestone

13

Chicago, IL

POINT (-87.6176834106445 41.5738476278005)

3

Silica Sand

75

Overton, NV

POINT (-114.4313621521 36.5146030619859)

29

Soda Ash

12

Green River, WY

POINT (-109.448783397675 41.5090754257687)

 

Spatial Querying Algorithm

Input: Job Site Latitude/Longitude

Steps:

A. Query for closest facility to Job Site within 500 miles:

  1. Calculate the distance between the job site and each facility.
  2. Filter the list of facilities to just those where distance < 500 miles.
  3. Order the list of facilities by distance in ascending order.
  4. The first element (if any) will be the closest facility, and also signifies that the product qualifies as being manufactured within 500 miles

B. If there is a facility within 500 miles, then sum the percentage of formula components that were sourced from within 500 miles of the Job Site:

  1. Calculate the distance between the job site and each of the facility’s formula components
  2. Filter the list of formula components to just those where distance < 500 miles
  3. Sum the Percentages

Output: Boolean of whether the product qualifies; Percentage of the product’s ingredients that qualifies.

Implementation

Before we can calculate distance using an instance method of the DbGeography type, we need to actually create an instance to represent the Job Site. DbGeography is immutable and does not have a constructor, so instead, a static method must be called to create a new object. There are a number of these factory methods available to create specific kinds of shapes (Point, Line String, Polygon, etc) given different kinds of input (text, byte arrays).

For simplicity, let’s use the .Parse() method, which accepts Well-Known Text (WKT) as input, and assumes a Spatial Reference ID of 4326 (the same coordinate system that GPS and internet mapping sites use).

Note: WKT uses a (Longitude, Latitude) ordering for points, which adheres to the same concept as (X, Y) ordering for Cartesian coordinates.

private static DbGeography CreatePoint(double latitude, double longitude)
{
return DbGeography.Parse(String.Format("POINT({1} {0})", latitude, longitude));
}



The first spatial query, written as a LINQ expression, finds the closest qualifying facility. Since SRID 4326 uses meters as the unit of measure, we need to convert 500 miles into meters within the predicate:

private Facility GetNearestFacilityToJobsite(DbGeography jobsite)
{
    var q1 = from f in context.Facilities
    let distance = f.Geocode.Distance(jobsite)
    where distance < 500 * 1609.344
    orderby distance
    select f;

return q1.FirstOrDefault();
}



Assuming that a facility was returned, a second LINQ expression can be used to find the sum of Percentage from qualifying Formula Components:

private decimal SumQualifyingPercentages(Facility nearestFacility, DbGeography jobsite)
{
var q2 = from fc in nearestFacility.Formula.FormulaComponents
where fc.Geocode.Distance(jobsite) < 500 * 1609.344
select fc;

return q2.Sum(c => c.Percentage.GetValueOrDefault(0));
}



Finally, putting all of the parts together (using a Tuple<> for the output):

private Tuple<bool, decimal> GetResults(double latitude, double longitude)
{
DbGeography jobsite = CreatePoint(latitude, longitude);
Facility nearestFacility = GetNearestFacilityToJobsite(jobsite);

if (nearestFacility != null)
{
return new Tuple<bool,decimal>(true, SumQualifyingPercentages(nearestFacility, jobsite));
}

return new Tuple<bool, decimal>(false, 0);
}

private void PerformQuery()
{
double latitude = 47.63752;
double longitude = -122.13343;

var results = GetResults(latitude, longitude);
}

Entity Framework Spatial: DbGeography and DbGeometry Members

DbGeography Static Property Return Type DbGeometry Static Property Return Type
DbGeography.DefaultSrid int DbGeometry.DefaultSrid int
       
DbGeography Static Method Return Type DbGeometry Static Method Return Type
DbGeography.FromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.FromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.FromGml(string geographyMarkup, int srid) DbGeography DbGeometry.FromGml(string geometryMarkup, int srid) DbGeometry
DbGeography.FromText(string geographyText, int srid) DbGeography DbGeometry.FromText(string geometryText, int srid) DbGeometry
DbGeography.GeographyCollectionFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.GeometryCollectionFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.GeographyCollectionFromText(string geographyText, int srid) DbGeography DbGeometry.GeometryCollectionFromText(string geometryText, int srid) DbGeometry
DbGeography.LineFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.LineFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.LineFromText(string geographyText, int srid) DbGeography DbGeometry.LineFromText(string geometryText, int srid) DbGeometry
DbGeography.MultilineFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.MultilineFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.MultilineFromText(string geographyText, int srid) DbGeography DbGeometry.MultilineFromText(string geometryText, int srid) DbGeometry
DbGeography.MultipointFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.MultipointFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.MultipointFromText(string geographyText, int srid) DbGeography DbGeometry.MultipointFromText(string geometryText, int srid) DbGeometry
DbGeography.MultipolygonFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.MultipolygonFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.MultipolygonFromText(string geographyText, int srid) DbGeography DbGeometry.MultipolygonFromText(string geometryText, int srid) DbGeometry
DbGeography.Parse(string geographyText) DbGeography DbGeometry.Parse(string geometryText) DbGeometry
DbGeography.PointFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.PointFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.PointFromText(string geographyText, int srid) DbGeography DbGeometry.PointFromText(string geometryText, int srid) DbGeometry
DbGeography.PolygonFromBinary(byte[] geographyBinary, int srid) DbGeography DbGeometry.PolygonFromBinary(byte[] geometryBinary, int srid) DbGeometry
DbGeography.PolygonFromText(string geographyText, int srid) DbGeography DbGeometry.PolygonFromText(string geometryText, int srid) DbGeometry
       
DbGeography Instance Property Return Type DbGeometry Instance Property Return Type
g.Area double? g.Area double?
    g.Boundary DbGeometry
    g.Centroid DbGeometry
    g.ConvexHull DbGeometry
g.Dimension int g.Dimension int
g.EndPoint DbGeography g.EndPoint DbGeometry
    g.Envelope DbGeometry
    g.ExteriorRing DbGeometry
g.GeometryType string g.GeometryType  
g.IsClosed bool? g.IsClosed bool?
g.IsEmpty bool g.IsEmpty bool
    g.IsRing bool?
    g.IsSimple bool
    g.IsValid bool
g.Latitude double?    
g.Length double? g.Length double?
g.Longitude double?    
g.M double? g.M double?
g.NumGeometries double? g.NumGeometries int?
    g.NumInteriorRing int?
g.NumPoints int? g.NumPoints int?
    g.PointOnSurface DbGeometry
g.ProviderValue object g.ProviderValue object
g.Srid int g.Srid int
g.StartPoint DbGeography g.StartPoint DbGeometry
g.WellKnownValue WellKnownValue DbGeographyWellKnownValue g.WellKnownValue DbGeometryWellKnownValue
g.WellKnownValue.Srid int g.WellKnownValue.Srid int
g.WellKnownValue.WellKnownBinary byte[] g.WellKnownValue.WellKnownBinary byte[]
g.WellKnownValue.WellKnownText string g.WellKnownValue.WellKnownText string
    g.X double?
    g.Y double?
g.Z double? g.Z double?
       
DbGeography Instance Method Return Type DbGeometry Instance Method Return Type
g.AsBinary() byte[] g.AsBinary() byte[]
g.AsGml() string g.AsGml() string
g.AsText() string g.AsText() string
g.Buffer(double distance) DbGeography g.Buffer(double distance) DbGeometry
    g.Contains(DbGeometry other) bool
    g.Crosses(DbGeometry other) bool
g.Difference(DbGeography other) DbGeography g.Difference(DbGeometry other) DbGeometry
g.Disjoint(DbGeography other) bool g.Disjoint(DbGeometry other) bool
g.Distance(DbGeography other) double g.DistanceDbGeometry other) double
g.GeometryN(int index) DbGeography DbGeography g.GeometryN(int index) DbGeometry
    g.InteriorRingN(int index) DbGeometry
g.Intersection(DbGeography other) DbGeography g.Intersection(DbGeometry other) DbGeometry
g.Intersects(DbGeography other) bool g.Intersects(DbGeometry other) bool
    g.Overlaps(DbGeometry other) bool
g.PointN(int index) DbGeography g.PointN(int index) DbGeometry
    g.Relate(DbGeometry other, string matrix) bool
g.SpatialEquals(DbGeography other) bool g.SpatialEquals(DbGeometry other) bool
g.SymmetricDifference(DbGeography other) DbGeography g.SymmetricDifference(DbGeometry other) DbGeometry
    g.Touches(DbGeometry other) bool
g.Union(DbGeography other) DbGeography g.Union(DbGeometry other) DbGeometry
    g.Within(DbGeometry other) bool