No Pity for the Masses

Code can be found here: https://github.com/Jerdak/Connect-N

This is an implementation of MiniMax with alphaBeta pruning and iterative deepening. The AI uses a simple “number of possible chains” heuristic to estimate the value of the board at any given configuration. Connect-N. This code was written for a class so it contains debugging code and references to the course. I’ll clean it up when I have time.

An explanation will follow in the next day or 2.

Have you ever tried to unpack the C++ Boost library on a machine running McAfee at threat level “WE’RE ALL GOING TO BURN”?  No?  Me either, until last month. 16 hours later it unzipped. Then it was just a hop, skip, and a 20 hour wait for it to compile:

1. Work Laptop(A beefy developer rig w/ SSD): 36 hours
2. Home PC: 45 minutes… while concurrently running Skyrim and streaming Firefly on Netflix. I had enough to time to misbehave, find the source of the reavers, and broadcast that source to the universe.

Quick and dirty example of bit packing. This example treats each byte, of a 32-bit INT, as a unique value. This example ignores the last byte, the source of the code only needed to store 3 bytes worth of data.

The main bit packer:

public class BitPack {
	public BitPack(){
		_data = 0;
	}
	private System.Int32 _data;
 
	public System.Int32 Data { 
		get { return _data;}  
		set { _data = value; } 
	}
 
 
	/// <summary>
	/// low 8 bits [1-8]
	/// </summary>
	public System.Int32 Low { 
		get { return (_data & 0xFF); } 
		set {
			_data &= 0xFFFF00;	//clear
			_data |= value; 
		} 
	}
 
	/// <summary>
	/// mid 8 bits [9-16]
	/// </summary>
	public System.Int32 Mid { 
		get { return (_data >> 8 & 0xFF); } 
		set {
			_data &= 0xFF00FF;	//clear
			_data |= value<<8; 
		} 
	}	
 
	/// <summary>
	/// high 8 bits [17-24]
	/// </summary>
	public System.Int32 High { 
		get { return (_data >> 16 & 0xFF); } 
		set {
			_data &= 0x00FFFF;	//clear
			_data |= value<<16; 
		} 
	}
}

Example wrapper, a coordinate pack:

public class PosPack : BitPack {
	public PosPack(){}
	public PosPack(PosPack p){
		X = p.X;
		Y = p.Y;
	}
	public PosPack(System.Int32 x, System.Int32 y){
		X = x;
		Y = y;
	}
	/// <summary>
	/// x coordinate
	/// </summary>
	public System.Int32 X {
		get{return Low * XSign;}
		set {
			Low = System.Math.Abs(value);
			if(value < 0)XSign = 0;
			else XSign = 1;
		}
	}
 
	/// <summary>
	/// y coordinate
	/// </summary>
	public System.Int32 Y {
		get{return Mid * YSign;}
		set {
			Mid = System.Math.Abs(value);
			if(value < 0)YSign = 0;
			else YSign = 1;
		}
	}
 
	/// <summary>
	/// x sign
	/// </summary>
	private System.Int32 XSign{
		get{
			if ((High & 0xF) > 0) return 1;
			return -1;
		}
		set{
			//High stores 2 values, only overwrite lower 4 bits
			int tmp = High;
			tmp &= 0xF0;
			tmp |= value;
			High = tmp;
 
		}
	}
 
	/// <summary>
	/// y sign
	/// </summary>
	private System.Int32 YSign{
		get{
 
			if ((High >> 4 & 0xF) > 0) return 1;
			return -1;
		}
		set{
			//High stores 2 values, only overwrite upper 4 bits
			int tmp = High;
			tmp &= 0x0F;
			tmp |= (value << 4);
			High = tmp ;
		}
	}
}

And Usage

PosPack p = new PosPack(-12,13);
Console.Write("X Should be -12: " + p.X);
Console.Write("Y Should be 13: " + p.Y);

Bits [1-8] store the x coordinate, bits [9-16] store the y coordinate, and bits [17-24] store the sign. You might ask yourself why use 8 bits to store the sign? You wouldn’t, not in an efficient example. I discretized my example along 4 bit chunks to make it easier to understand. In reality I would only need 18 bits.

You might also ask why would anyone go to this much effort to store 2 ints? The answer is two-fold: Networking and hashing. We can now transmit just 1 integer that can be split in to 8 bit increments for serialization. If you’re using C# you can let the compiler handle serialization for you.

These past weeks have flown by. Finals, projects for work, gaming, and enjoying time with my wife have taken up any free time I might have had once.

Finals:

If site statistics are to be believed, my most popular posts are the ones where I post some bit of code or an equation. Never one to mess with trends I present you with the 2 point Gauss quadrature formula for integrating f(x)ln(1/x) on the interval [0,1]:

Solving numerically for our unknowns:
W1 = 0.2814605
W2 = 0.71854
Y1 = 0.602277
Y2 = 0.112009

There might be errors in my reconditioning. Not having received a copy of my final I can only guess that this was one of the correct answers. Our professor normally gave problems that could be analytically solved so it might be that my values for the unknowns could have been derived in a simpler fashion.

Projects for work:

I’m extremely excited about several projects for work, most that I can’t really talk about. I will say that I get to abuse Microsoft’s Kinect to do some very interesting data collection. Along a similar vein I’d be remiss if I didn’t mention the incredible work being done over at PointClouds.org

PointClouds.org are responsible for the point cloud library, a handy set of computer vision tools for interpreting range data in the form of point clouds. They have several canned modules for common point cloud manipulations like feature extraction and/or ICP (iterative closest point) mesh alignment.

Gaming:

Star Wars fandom runs deep in my veins.  My father, an epic scifi geek, introduced me to Star Wars at a young age.  Like millions of other geeks I was enthralled with this world of technology and mysticism.  Aging has done little to dull my love of episodes 4,5, and 6 though I now accept that Lucas shouldn’t be allowed to write scripts.

Bringing the discussion full circle we come to Star Wars: The Old Republic (TOR).  TOR is an online role playing game (MMO) released a few weeks back by Bioware/EA.  As a long time Bioware fan, and fanatical evangelist for the Knights of the Old Republic PC game, it was a safe bet that I would buy TOR.

Coming from an old-school background of Ultimate Online, Everquest, and Shadowbane I wasn’t sure if I would like the future that World of Warcraft had wrought.  WoW is chiseled in the MMO community as a sort of demigod.  Equal parts amazing balance, story, and artistic vision WoW has shaped a generation of gamers I’d not yet met.  Ever was I wary of a game that so codified the rules of conduct that restricted users to instances for conducting player vs. player (PvP) combat .  Not being a fan of the Warcraft mythos also kept me from going far in WoW.  And so I come at TOR with fresh eyes, a novice to the MMO world.  TOR responded admirably.  The story is fun, the skills are interesting, the loot looks nice, and players are friendly.  Time will tell if Bioware can retain their user base over the next year.  I for one will be playing for at least a few months.

The Wife

My wife, whom I love so very much, has always accepted gaming as a part of life.  And bless her for it.  To make sure she knows she is loved I took her on a date in to Boston for a New Year’s day celebration.  We enjoyed a delicious meal at Stepheni’s on Tremont and we spent several moments enjoying the oddly warm night air and the glowing ember of the cityscape off in the distance.  Orange clouds framed the night sky adding additional warmth to the evening.

So begins the New Year and I want to start by thanking my wife for 5+ years of wonderful companionship and 2+ years of wonderful marriage.  Without her, the topics above would be meaningless.

*Small edit: Her love does not, unfortunately, keep me from making silly grammatical errors. Changed ‘except’ to ‘accept’… I need to reread my word annoyance post.

Everyone likes a challenge and this is mine for 2012/2013. The dates are still up in the air as I assess my fitness level to see if I can shed enough weight to participate in an appreciable fashion in 2012. If I can’t participate this year I intended to sign up for 2013.

It would be great if others from MA would like to form a crew to help train and to compete together.