Summary of DeepStack: Expert-Level AI in Heads-Up No-Limit Poker

Below is an excerpt of some of the research I have been doing for a Udacity Course I am taking on AI. It’s been a lot of fun digging into the merging of logic and machine learning. I’ll likely post a bit more details and perhaps a review once complete. But for now, here is a summary of some pretty cool research coming out of the University of Alberta.

Imperfect information games provide a significant challenge as compared to deterministic games. Since limited information is available to the agent, the agent must calculate a statistical best choice(s). Formally the statistical best response is accomplished by approximating the Nash equilibrium given the private information held by the opponent. DeepStack builds upon the traditional technique known as counterfactual regret minimization, which is a recursive algorithm which pre-computes the probability distributions. The issue with this method is that the computational requirements for Heads-Up No-Limit Poker (HUNL) approaches 10160 therefore approximates to game states would have to be made. A goal of DeepStack was to eliminate as much contextual information loss as possible.

When player a two-player zero sum game such as HUNLor goal is to maximize the expected utility against a best response strategy. Deep Stack calculates this through 3 elements. The first generates a representative picture of all currently available public information. Public information in the case would be the agents two cards in hand, the pot, and any visible cards dealt to the table. The second component is a depth limited search technique which uses a trained neural network to quickly evaluate values below a certain depth. By using the flexibility of neural networks to generate values, the depth needed to search can be greatly limited. Limited set of look-ahead branches. By limiting to a known set of optimal actions, the recursive traversal computational cost can be reduced.

The internal representation of all public information is regenerated each action by a process the authors call “Continual re-solving”. This is done with two values, obviously, the first required values are the public state. Secondly, a vector of counterfactual values of valid “what if’s” relevant to the opponent. The counterfactual values start with a default starting state for the first round. Afterwards the vector is updated by output of the recalculation.

In order to make re-solving practical, the depth of the search is limited to four actions. Values are calculated through a neural network the authors call “Deep Counterfactual Value Networks”. Given the complexity created by imperfect information, each vector must contain what amounts to a description of the poker game being played. Concretely, a representation of the probability distribution of the cards dealt to the private hand and a value of the current knowns.  The authors liken this output to “Intuition”. The network itself consists of seven hidden layers with 500 nodes each. Trained on 10 million randomly generated poker games for the turn and 1 million for the flop.

DeepStack has shown significant improvement over previous systems. Competing against various professional human players. Playing a total of 44,852 games. DeepStack won 492 mbb/g. Which the authors indicate as over 4 standard deviations away from zero. In comparison to previous algorithms such as Claudico(2015) which lost at a rate of 91 mbb/g. DeepStack shows a novel approach to relegating to neural networks strength in determining probability distribution over a wide range of outcomes. This system which demonstrates the possibilities in the future of AI in regards to solving problems with imperfect information.

Does it Function?

Thinking about Refactoring Functions

Photo by: Gaby Av

What are the ideal properties of a function and when should you refactor a functions? Or from another angle, when is the best time to refactor a function out, restructure within or just leave it? In the last week or so I’ve noticed an interesting pattern in functions written by some slightly novice developers. I got to thinking about how to best give constructive feedback. But something I found interesting about all of is that the structure of the functions, at least on the surface, seemed to meet all the traditional best practices of a function. They performed a single purpose, were created to avoid repetition, etc. But the code was awkward to work with and functions almost obfuscated rather than simplified. So what attributes made them difficult to work with and kinda smell of code rot? So I thought I would list out some further considerations when breaking a functions out.

Functional Mutation

What the heck is functional mutation? Well I did just make the word up but it seemed appropriate. Usually, this is a sneaky violation of “functions should perform a single purpose”. It happens when a function’s output varies unpredictable from what can been gathered from the function’s name and its inputs. This is usually caused when the code inside the functions varies output wildly due to non-intuitive conditions, at least as seen by the outside observer. It really pays to leave conditional logic which impacts the straightforwardness of a function in a higher level of code. If that just doesn’t seem reasonable then usually that’s an indication that it’s to rethink the structure to match the conditional lines.

Sequential Dependence

When a function can not perform its required task due to its dependence on another function it’s usually bad. There are exceptions to this one, especially when designed something that interface with an external system. But, it’s very important to ask whether the dependence can be removed by either restructuring the input parameters, restructuring functions, or both. The problem with sequential dependence when it comes to maintenance is that it hurts code readability, and locks it any changes to external dependencies. So ask yourself twice if there is a better way if you find a set of function like this.

Sometimes it’s better to not refactor a function out unless it stand on its own. But be sure to remember that the person that comes behind you, which is usually you 6 months from now who has totally forgotten everything, won’t know your ideology while they absorb it purpose. So do yourself, and them a favor by writing code which speaks to them rather than having to be strangle out.

An Argument for the Jack of All Trades

Is it true that a person who has chosen to remain good at everything rather than excellent at one thing has made themselves noncompetitive? Does the old adage “jack of all trades, master of none” still ring true today or has it really ever? This is something I have given quite a bit of thought to and have wondered if my desire to roam and explore topics has in fact put me at some disadvantage. I suspect in some regards it has, but why and should that be the case? Clearly I don’t believe completely believe that are this would be a rather short post.

Once upon a time, in an age which things where hand crafted. It took a great deal of time and effort to create even the simplest objects. A wooden chair would take days, cathedrals could take centuries. Their creators only hopes of making a sustainable living at their trade was to be quick at making repetitive hand shaped items. To learn was to apprentices along side someone who had dedicated there lives to the subject. Little was shared without it being spoken and shown since books where rare. But progress changed that and suddenly one could learn without being shown.

Things have obviously continued to change since then, knowledge has proliferated. Conversely so has the reduction of manual task. Machines perform the repetitive tasks for us leaving us time to think of new ways to improve things. This changes the emphasis on being good at a singular task but rather an ever expanding array of higher level tasks.

The present is driven by the consumption and application of new information and a few key areas of rarely changing knowledge. Once you learn the key areas you can pivot much easier than the past. Though specialization is by no means obsolete and never will be. But perhaps having a wider understanding is as important now as a narrow one. Pulling ideas from a big bucket with many tools will always yield more progress than a small bucket with narrowly focused ones.

Anyways, food for thought in a age where specialization has grown rather than shrunk. But maybe its not so bad being a jack of all trades.

Raspberry Pi Interrupts – An adventure with vector interrupt controllers

Today’s topic is about the Raspberry Pi Interrupt controller. I know what you’re thinking but its not as bad as it sounds promise. So, I’ve been goofing around with my ultra sweet Raspberry Pi and in doing so had this wonderful idea to just roll my own OS. You know average weekend project stuff, right? Anyways my work on RazOS has just begun and most likely will continue for some time. Though so far its been awesome, I have encountered many a roadblock along the way and thought I should share a few in hopes of saving someone else from the pain and suffering of sorting though Linux source as well as the little tidbits that are scattered about. That said, if you’re interested in OS coding I’m planning a series to come which should provided a bit more back-story. I should mention for those interested in learning something cool that this is should give you a bit of the detail you will need. So if you have no idea what a Vector Interrupt Controller is then stick with me I’ll bring you up to speed, if you do know then you may want to skip the whys and go to the core of the article down below.

What is a Vector Interrupt Controller

So Wikipedia‘s definition goes as follows “An interrupt vector is the memory address of an interrupt handler, or an index into an array called an interrupt vector table that contains the memory addresses of interrupt handlers.” Not particularly enlightening, good news is it is much simpler than its made to sound. To get started I think its best to quickly go over interrupts in general. The purpose of interrupts are simple, lets imagine for a moment you are a accountant. A pretty good one at that who can master even the most obscure of tax codes and spreadsheets. I know bear with me. Unfortunately your assistant is well.. not quite all there. When he has new information to give you or that spreadsheets you asked for instead of knocking on your office door he just stands there. I guess he is just hoping you will think to answer. Of course if you don’t quickly enough his ADD may get the best of him and just wonders off, so your forced to constantly get up and check the door to see if he is there. Now its pretty easy to see you wouldn’t get much done having to check the door all the time no matter how good you are. So whats the most simple fix to this?  Probably just to tell him to knock instead of standing there! That is exactly what an interrupt is, a knock.

Unfortunately our CPU is a bit dumber than our accountant so we have to be a little more straight forward with our decision making but the metaphor is still quite applicable. But the question lingers still, what is a vector interrupt controller? In short a vector interrupt controller is for when we have more than one door which is almost always the case.  In the case of the Raspberry Pi it can visualized with one buzzer and you have to look up which door it came from but we will come back to that in more concrete terms.

Raspberry Pi Interrupt Controller

To began lets look at this bit of code from a great example provided from David Welch.

.globl _start
ldr pc,reset_handler
ldr pc,undefined_handler
ldr pc,swi_handler
ldr pc,prefetch_handler
ldr pc,data_handler
ldr pc,unused_handler
ldr pc,irq_handler
ldr pc,fiq_handler

reset_handler: .word reset
undefined_handler: .word hang
swi_handler: .word hang
prefetch_handler: .word hang
data_handler: .word hang
unused_handler: .word hang
irq_handler: .word irq
fiq_handler: .word hang

mov r0,#0x8000
mov r1,#0x0000
ldmia r0!,{r2,r3,r4,r5,r6,r7,r8,r9}
stmia r1!,{r2,r3,r4,r5,r6,r7,r8,r9}
ldmia r0!,{r2,r3,r4,r5,r6,r7,r8,r9}
stmia r1!,{r2,r3,r4,r5,r6,r7,r8,r9}

;@ What gets called if a IRQ event happens

This is an example set of one possible way to initialize your vector table but I find it to be very straight forward for illustration purposes. This code’s job is to put the addresses of the subroutines which will be called automatically by the processors hardware should any of the events be triggered as well as enabled. By default the hardware assumes that the first eight words of memory are address to subroutines, but it can be changed to the last eight words should you wish it. You can find out how here, get familiar with it many arm specific questions can be answered with it. Since the Pi expects and runs your code at 0x8000 we must relocate the table to 0x0000, which is what the remainder of the code does for us.

Since we are only interested in interrupts today I’m going to ignore all but the IRQ calls, though it should be noted that FIQ is essentially the same with a few perks to speed up interrupt handling. You can find more on the subject in the ARM Manual.

Who knocks?

So the final part of our interrupt adventure comes in finding which door the knock has occurred. But before we get any knocks we have to enable IRQ, this is a two step procedure. First of which we must turn on the “master IRQ switch” so to speak which is located outside in a coproccessor. Once again code courtesy of David Welch. Note the mrs and msr calls.

.globl enable_irq
mrs r0,cpsr
bic r0,r0,#0x80
msr cpsr_c,r0
bx lr

Once we have enabled IRQ as a whole them we must enable the individual “Doors” which we wish to hear knocks from. From this point each sub component handles the the details, so you must refer to each individual component for the details of how it triggers an interrupt.  It is worth mentioning that most of the interrupts are not handled via the ARM processor unfortunately since technically it is the secondary processor in the Broadcom BCM2835, the undocumented Videocore GPU is the king on this chip. But the ARM does have access to all of the primary ones.

The subsystems can be found here. One big point to note about the peripherals document. Unless you have the MMU enabled and mapped as stated then almost all address in the guide must be translated from 0x7Ennnnnn to 0x20nnnnnn. For example the guide states that the interrupt begins at register is 0x7E00B000, NOPE! It is in fact at the physical address of 0x200B000, so keep this mind. Since this is running a bit long I’m going to end it here, a follow up to come.

Important Further Reading:

To Engineer: My Design Philosophy

I have a habit of calling myself an engineer. You could say well like an engineer that build my favorite clogged turnpike or that blender that lasted three days? Well yes and no, but rather than argue semantics lets first take a look at the origin of the word.

The word engineers roots go back to the roman word ingeniare(“to contrive, devise”) and ingenium (“cleverness”) per wikipedia. If your Spanish is up to par they should also seem a bit familiar to you. One thing interesting to note is that the English word engineer also shares an origin with the word engenders(“To arise from”). This particular framing of the word gives me particular pause for though as my job as a programmer requires a great deal of attention to that ethos.

Ethos? Yes I believe so. I believe that a more accurate definition of the word engineer, despite the modern context, is the title of someone who’s core mastery / profession is to contrive and create tangible, useful devices that move the world forward. An engineer derives these constructs through cleverness and intellect. Now I use the term devices loosely, this can range from the physical( a phone, turnpike, computer processor) to the metaphysical(Concepts, ideas, thoughts). Now it is important to included thought-space in our definition because physical derivation must first be derived through thought. This is perhaps the biggest departure from the traditional definition.

How its useful

By considering this we can also use the word engineering to define a philosophy. In its simplest form this philosophy is the philosophy of creating things through cleverness and creative use of known / discovered principles. As a software developer I have found that it is important to approach problems by providing myself a label that extends beyond the traditional word software developer of X. This acknowledgement that in fact I’m engineering a solution in a greater sense allows myself to act outside of the normal barriers the we impose on our minds. I instead have now become a problem solver, only limited by my means of my own imagination and astuteness to research and learning.

Further Reading

The Executioner: the JavaScript execution context and how to defeat it

JavaScript as the dynamic and versatile language it is provides us with several non intuitive points to be weary of while constructing our code. But before we dig too deep into the issues and their solutions lets review a few facets of the JavaScript’s interpreter.

Execution Context

[Note: also sometimes referred to as Activation Object, Scope Object, Variable Fairy]


Not as scary as it sounds, I assure you. To understand its purpose we need to merely break down its very name. Execution Context, it is the manager of the context of the code that is currently being executed. Quickly, lets take a look at what the execution contexts properties are.

var executionContextObject = {

  • VariableObject – Simply the list of variables/arguments which may be accessed in the function. More on this in a moment.
  • ScopeChain – All the execution context objects containing of all the parent functions.
  • This – the value associated with the current this

Variable Object Array

Lets take a moment to peel back the covers and understand how the variable object works. Now at the point this is happening the interpreter has reached a new function and is creating the execution context for us. These are the steps it will take while creating it.

  1. Look at the inputs||arguments of the function and make an arguments array out of them.
  2. Find each function and and save the pointer to it, if it finds a matching pointer overwrite it with the newest value. Stick results into the Variable Object array.
  3. Find each variable with a var and initialize it to its line assigned value (var me = ‘Ben’) or default which is the “undefined” value. Stick results into Variable Object array.

This array is what lets us do things like this.

var mySweetObject = {
color: "Red",
magicalAbility: "telekinesis"

//Normal way to access a property
var color = mySweetObject.color;
//Using the Variable Object Array
var magicalAbility = mySweetObject["magicalAbility"];

The Execution Stack

Now that we understand a bit of how the execution context looks lets take a look at the execution stack. The execution stacks job is to keep track of whats being executed as well as its associated execution context. We can think of it simply as a stack which items are placed on top as they are encountered or LIFO if you prefer that verbiage.

Created By David Shariff

[Image created by David Shariff]


You hear a lot about hoisting, but armed with the above you can tell all of your friends about how simple it is, properly asserting your intellectual superiority over them. Lets look at an example.

console.log(typeof funkyFunction ); // function pointer

var funkyFunction = function(){
return "awesome";

Wha, bit odd that myFunkyFunction seems to have a value as though it was declared before its var. But we know that the variable object array is created before the code is executed and therefore is the any inside the scope of this function are created before execution. (Side Note: this does not apply to variables applied to child function)

Scope Chain

Like mentioned before the scope chain is an array which contains all parent execution contexts. Its purpose is to store the location of all variables that the current function can access , this is to facilitate JavaScript’s external variable storage which is represented as lexical scoping.  Lexical scoping simply means functions are stuck with the variables of their parent functions even if called from another physical location.

Use local variables

Now considering the impact of all our variables being stored in physical order, also it is then given they must each be resolved every time a non local variable is utilized. This is a very good reason to be weary of the global scope since it must always be contained in the scope chain. So lighten up on those global declarations, it can save you on bigger JavaScript projects. I have seen scope variables easily reach over 100,000 in big projects, this meaning a serious impact on scan times when the interpreter must resolve variables. But of course use of local variables avoids this entirely, allowing the interpreter to remain in the variable object array.


Don’t forget that lack of a var keyword when declaring a variable always lands that variable into the global scope, this includes functions.
Thanks for reading!

Further Reading

SQL Voodoo Query: Merging a column in multiple rows into just one

[This is an old but regularly requested  post of mine from BIDN in 2011, updated due to my renowned grammar]

Today I wanted to quickly mention a technique to pivot a one to many data structure into a one column list of items. I know it has been mentioned before a bit differently in previous blogs before on BIDN.

The problem?

We have three tables


In the instructors table we have the instructors name, ID, and yada yada. InstructorClasses is our junction table and links all of the instructors to their list of classes and finally classes is our simple list of classes.  Now assuming we have a web page that needs to show them as below?

Instructor: Jim Bean

Classes: Rowing; Yoga; Bartending;

Now assuming you are unable to format in code or perhaps you are archiving data and needing to convert it during ETL. To get the expected results we can utilize the XML Path command in SQL Server to provide us a pivoted view of classes as demonstrated in the example below.

SELECT Left(Main.Categories,Len(Main.Categories)-1) as Classes, Instructors.FirstName + ' ' + Instructors.LastName as InstructorsName
FROM Instructors
left join (Select distinct ST2.InstructorID ,
(Select distinct Classes.ClassTitle + '; ' AS [text()]
From InstructorsClasses ST1
join dbo.Classes
on ST1.ClassID = Classes.ClassID
Where ST1.InstructorID = ST2.InstructorID
For XML PATH ('')
) [Categories]
From InstructorsClasses ST2) [Main]
on InstructorID = main.InstructorID

Skill Growth: Or how I learned to love the blog

So this being the first formal blog in some time as well as the very first for the site so I figured that my first topic should be on blogging itself. It has occurred to me on numerous occasions, in both recalling technical issues I have faced as well as clarifying my own thoughts, how really useful blogging is. Though it doesn’t help to have poor memory and terrible grammatical skills. But if trial by fire can’t cure early onset Alzheimer’s then I don’t know what can. So let’s get this ramble going.


To blog or not to blog?

If you are here then I’m pretty sure you have a solid handle on the concept of blogging, so I’m going to skip being a Webster dictionary knock off. That said, the Internet has provided an enormous soapbox for us to stand on so why not use it. On top of the fact that there’s a vast number of content hungry users which have been provided to us by the glorious proliferation of the internet. This has thus created a huge churning pool of knowledge consuming, LOL cats viewing (God only knows what else) group of individuals seeking quality content. All of which may find your ideas to be helpful to them. This gives us the unique opportunity to dive in and see what ideas you have that actually stick and refine them accordingly.

That being said blogging’s greatest potentials lay not only in the fact there are others out there that may find your content useful, but that you yourself may find the act of writing useful. The act of writing requires us form ideas which can easily be conveyed to others. A great deal of mental house cleaning is needed to preform this feat and as we solidify our ideas it allows them to become clearer. Ideas are then illuminated to our-self’s as well giving clearer authority and understanding of them.

What is your blogging tool, and what does it do?

Now hopefully you read the section header with an Austrian accent, if not I’m disappointed in you dear reader. But to the relevant conundrum. Although the majority of my previous blogs have been generally technical, I’m going to forgo replicating the majority of the Internet and provide you with one key tip. Though I will list out several useful links towards the end of the blog for expanded reading. Now as a blogger there really is only one tool that you need and its name is WordPress. Now I know a large segment of the Internet will disagree with me and that’s OK. But in reality it’s such an easy tool with many features that unless its your sole source of income and you have excessive spare time why distract yourself from the most important element, content content content.

But I do promise more to come soon! In the meantime I will be working to get the rest of the site ship-shape and bristol fashion.