As much as I’m loathe to admit it, I’ve bitten off a bit more than I think I can chew with the AI-Coder project.

Why the sudden change of heart?

I’ve been doing my homework.

Over the last three weeks, I’ve given a lot of consideration to the four high-level design goals that I outlined a few days ago (fun, security, speed, and legality). I’ve written some sample code, I’ve buried my head in a small stack of technical books, and I’ve read through pages and pages of federal and state laws.

As a result, I’ve identified some major obstacles. On their own, each of the obstacles presents a barrier I could probably overcome. But combined, the accumulated weight of these obstacles is more than I’m willing to tackle for this project.

Needless to say, I’m pretty disappointed.

Anyhow, to give you an idea of the challenges inherent to this project, I’ll walk you through my thought process as I considered the technical and business implications of making the AI-Coder project fun, secure, fast, and legal.

Sounds Like Fun!!!

There are plenty of programmers who write code in their spare time, for fun or self-betterment (as evidenced by more than 120,000 projects and more than 1.3 million registered users at SourceForge), so I’ve never been too concerned when people have asked me how I’d find people willing to write code in their spare time. Hobby programming is already remarkably common. And hobby programming with the potential to win cash prizes is almost a no-brainer.

But the one detail that always nagged at me was this: How many programmers are really passionate about chess strategy?

Sure, coders are more likely to play board games than your average citizen, but focusing on super-geek games like chess, backgammon, go, or othello would be too limiting. To develop a large, broad, and enthusiastic community, I’d need to include a game with more broad-based appeal. Something cool. The kind of game that could even convince non-programmers to start slinging some code.

So I decided to include Texas Hold’Em (or some other poker variant) in the AI-Coder platform. (As a bonus, I’ve already written thousands of lines of poker AI code myself over the last year.)

In my opinion, the availability of cash-money pokerbot tables would be a key ingredient to the long-term success of the AI-Coder project. Although I’d offer cash tournaments for plenty of other turn-based strategy games, I think poker would be the real money-maker.

Dealing from the Bottom of the Deck

Even without offering poker-style games, I’d have to think about cheaters. What are all the possible ways people could exploit the system to gain an unfair advantage?

What if one player could sneak a peek at another player’s cards?

What if a player could modify the state of the table, stacking his own hand with better cards, or sabotaging the hands of his opponents?

What if, in a game with more than two players, two or more players could secretly communicate with one other, conspiring against the solo players at the table? What kind of software architecture can prevent two bots from colluding?

What if, at the moment preceding a catastrophic loss, the losing player can crash the system by blowing the stack, eating through the heap, or overflowing a buffer? How can the software prevent (or at least detect and punish) any bot who sabotages the game to avoid losing?

This is where I thought the .NET platform would provide a straightforward solution. With my experience writing code for a managed environment (the JVM), I assumed that I could get up to speed on .NET security without too much trouble.

My technical experimentation over the last few weeks has proven that assumption wrong.

Microsoft has actually given a lot of thought to the security architecture in the .NET framework with a concept they call AppDomains. All managed code executed by the CLR is first loaded into a privilege-managed AppDomain sandbox. Code executing in one AppDomain is prevented from accessing the objects allocated in another AppDomain unless the objects are deliberately marshalled (using dynamic proxies or serialization) across the sandbox boundaries. In addition, each AppDomain can have its resource-access privileges completely locked down, preventing certain assemblies from accessing the file-system or connecting to a remote host on the network.

By loading each bot into its own AppDomain, I could use those isolation mechanisms to prevent quite a few exploits. A rogue bot would be unable to sabotage the game-state or peek at the hidden cards in his opponents’ hands or collude with another conspiring player.

But, unfortunately, all AppDomains in the parent process still allocate their objects on the same global heap, so it would be impossible to enforce memory restrictions on a player-by-player basis, leaving the door wide open for a player to deliberately over-allocate objects, throwing an OutOfMemoryException and corrupting the state of the current game.

How could I monitor allocations to fairly distribute resources among all the active players?

This is where it gets really tricky.

By implementing the game controller as an unmanaged C++ application, I could create an instance of the CLR as an ICLRRuntimeHost COM object. By instantiating that COM object using a custom implementation of the ICLRPolicyManager interface, I could set my own escalation policy for trapping (and recovering from) OutOfMemoryExceptions, using a custom IHostMemoryManager to keep careful records of allocations, deallocations, and GC compactions. I could catch OutOfMemoryExceptions as they occur, causing the offending player to automatically forfeit his hand.

That’s pretty impressive stuff, but it still wouldn’t really solve the problem. What if, at a ten-player table, Player#1 filled 90% of the available memory with his objects? By the time Player#10 got his turn, he might throw an OutOfMemoryException by allocating only a fraction of the memory unfairly claimed by the first player. Rather than punishing the player who actually uses the last byte of memory, I should punish the player who allocates more than his fair share.

As far as I can tell, the only way to accomplish that granularity of memory management is to run each player’s code in its own separate process, using COM interop for inter-process communication. At that point, the conveniences of the .NET framework fall mostly by the wayside, and I’m left implementing a whole lot of unmanaged C++ code.

I was prepared to write a thin C++ management layer as the controller for this architecture, but this is more than I bargained for. With only a little C++ experience, and no exposure to COM at all, I’m reluctant to pursue this route.

The Need for Speed (or, at least, Non-Slowness)

The idea of having third-party code executing on my server is not appealing, even if that code was confined to execute within a secure sandbox. AI code, often written by novices, would probably chew through a server’s CPU cycles pretty quickly.

I’ve considered building speed-incentives into the game rules. Maybe the winner of a particular game would forfeit a percentage of his winnings if his code was too slow. Maybe the winner of a Hold’Em hand would be determined by some combination of hand strength and execution speed.

But what if a GC collection was triggered in the middle of someone’s algorithm, to clean up for the allocations of the previous player? Without process (and heap) isolation, it would be very hard to come up with a fair mechanism for measuring execution time of any given player’s code.

A few people have suggested to me that I should just host the game server, allowing people to connect their algorithmic code via a SOAP interface, or some other remote API. But then it’s impossible to guarantee the integrity of the game. What if someone’s “AI” code just consists of a GUI where a human can compete against all the other machines (in many cases, humans are much better than machines at playing these games). And what if a few players started teaming with one another, colluding against the other players at the table. The only way to prevent those kinds of exploits is to execute the code in a known secure sandbox.

But what would it cost to fully host an ongoing competition like I’ve envisioned with the AI-Coder project?

In my experience writing poker AI code, a straightforward decision (folding a hand with a deuce and a three, off-suite) can be made in a few milliseconds. But more difficult decisions (like determining whether to fold a straight when an opponent might be bluffing a flush) can take two or three seconds to run through all of the probabilistic calculations, stochastically modelling the opponent’s likely hand, based on his observed play-style. (The exact sequence of checks, calls, and raises tells you a lot about what cards the player is actually holding.)

Realistically, with novices writing code, I’d expect an average ten-seat table to run at real-life poker-table speeds: about one full hand per minute. Maybe two. So a single server would be able to handle between ten and twenty simultaneous users.

In order to be profitable, I’d need to host a large cluster of powerful servers. Although I could start off small with a closed beta, increasing the hardware along with market demand and using an invitation system to control the flow of new members, it would definitely be a challenge to grow a scalable architecture.

I Don’t Want to Go to Prison

And of course, I’ve spent many many hours conducting legal research, trying to identify the potential regulatory hurdles I’d encounter with a business like this.

It’s not pretty.

Most of the laws (at the federal and state level) would consider the AI-Coder business model to be “gambling”, as long as the games involved an “element of chance”. Even if the game outcome is predominantly affected by the skill level of the participants (as would surely be the case with an AI programming contest), the influence of that “element of chance” would make the contest subject to gambling laws.

In Title 18, Chapter 50, Section 1081 of the US Code, a “gambling establishment” is defined as:

The penalty for operating a gambling establishment is detailed in Title 18, Chapter 95, Section 1955, to whit:

Ouch.

And, as if that wasn’t bad enough, I’d like to refer you to Title 18, Chapter 96, Section 1961 and Section 1962:

Racketeering, huh?

And you thought writing AI code was difficult? I bet you’ve never tried writing a thousand lines of code with a pair of brass knuckles on your fingers. Now that’s what I call hard-core programming!! And how would you like to try on a pair of cement shoes, my friend?

Of course, the Feds will be very interested in all the internet traffic going to and from my servers. According to Title 18, Chapter 119, Section 2516:

Of course, all of this relies on the notion that the AI-Coder platform could be classified as “gambling”, a classification that rests largely on the “element of chance” inherent in some of the games.

But what if I could eliminate the element of chance from the games? Obviously, games like chess and backgammon are already purely games of skill. But would it be possible to slightly re-write the rules of Texas Hold’Em to eliminate the element of chance?

I’ve developed an ingenious idea that I call “collaborative shuffling”, wherein one player gets to arrange the deck in whatever order he likes. He can stack the deck to his own advantage. But then he passes the deck to a second player, who re-arranges the cards again. The only restriction is that the second player is unable to see the values of the cards, so he can’t know how the first player arranged them.

The collaborative shuffling process would eliminate randomness from the game, while still providing a mechanism for scattering cards throughout the deck. As a classic example of a Prisoner’s Dilemma, the shuffle would become a key strategic element of the game.

But, even with the “element of chance” gone, would the AI-Coder project be free from legal trouble?

I don’t think so.

Even though it might be possible for a non-random poker variant to pass muster against the federal gambling laws, the state statues are much more varied in their construction.

In Florida, for example, the state Criminal Code (in Title XLVI, Chapter 849, Section 14) specifically prohibits wagering “any money or other thing of value upon the result of any trial or contest of skill, speed or power or endurance of human or beast”, making violations of the prohibition punishable as a second-degree misdemeanor.

Arizona doesn’t create a special prohibition against games of skill, but (in Title 13, Section 3305) it places a blanket prohibition on any wagers concerning “the results of a race, sporting event, contest or other game of skill or chance”. A violation of this statute is a class 1 misdemeanor.

The Arkansas statutes (in Title 5, Chapter 66, Section 113) prohibit “betting any money or any valuable thing on any game of hazard or skill”. The fine is $25.

Similar prohibitions against wagering on skill-based games exist in at least five or six other states.

So, I could probably operate legally, if I eliminated the element of chance from all of my games, and if I excluded residents of non-skill-gaming states from participating.

But the law is a slippery thing. I’d be stupid not to retain expert legal counsel, since I’m not personally capable of keeping up-to-date on the gambling laws for 50 different states, as well as the federal laws (which, by the way, automatically kick-in whenever you’re charged with a violation of a state gambling law).

So, that’s it then?

If it were just the legal issues, I might have the stomach to go for it.

I’ve found a number of attorneys who specialize in gambling laws, and I could hire them to do some research for me, giving me a set of parameters within which I could operate legally.

I don’t have a lot of start-up capital, but getting some sound legal advice would be a good use of that cash.

And if it were just a matter of learning COM interop programming with C++, I’d be up to the task. After all, I’ve learned a half-dozen different programming languages over the last few years, and I could certainly learn a few more.

If my only concern was providing a fun coding experience, or setting up a fast implementation, I’d take the plunge.

But there are too many obstacles here, and I’m afraid I’d injure my probability of succeeding by picking a project so fraught with peril.

Instead, I’m going back to the drawing board.

I’m going to re-visit my previous list of ideas and decide on a more suitable business plan. Unfortunately, despite my enthusiasm for the AI-Coder idea, this is the wrong project for me.

This entry was posted on Sunday, August 27th, 2006 at 9:53 pm and is filed under biz, aicoder. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.