Information Processing

Just another weblog

Archive for July 2007

I, Robot

leave a comment »

My security badge from a meeting with Israeli internet security company CheckPoint (Nasdaq: CHKP). There was some discussion as to whether I should be classified as a robot or a robot genius 🙂

Infoworld article: … RGguard accesses data gathered by a sophisticated automated testbed that has examined virtually every executable on the Internet. This testbed couples traditional anti-virus scanning techniques with two-pronged heuristic analysis. The proprietary Spyberus technology establishes causality between source, executable and malware, and user interface automation allows the computers to test programs just as a user would – but without any human intervention.

Written by infoproc

July 31, 2007 at 9:42 pm

Posted in robot genius, startups

Tyler Cowen and rationality

with 3 comments

I recently came across the paper How economists think about rationality by Tyler Cowen. Highly recommended — a clear and honest overview.

The excerpt below deals with rationality in finance theory and strong and weak versions of efficient markets. I believe the weak version; the strong version is nonsense. (See, e.g, here for a discussion of limits to arbitrage that permit long lasting financial bubbles. In other words, capital markets are demonstrably far from perfect, as defined below by Cowen.)

Although you might think the strong version of EMH is only important to traders and finance specialists, it is also very much related to the idea that markets are good optimizers of resource allocation for society. Do markets accurately reflect the “fundamental value of corporations”? See related discussion here.

Financial economics has one of the most extreme methods in economic theory, and increasingly one of the most prestigious. Finance concerns the pricing of market securities, the determinants of market returns, the operating of trading systems, the valuation of corporations, and the financial policies of corporations, among other topics. Specialists in finance can command very high salaries in the private sector and have helped design many financial markets and instruments. To many economists, this ability to “meet a market test” suggests that financial economists are doing something right. Depending on one’s interpretation, the theory of finance makes either minimal or extreme assumptions about rationality. Let us consider the efficient markets hypothesis (EMH), which holds the status of a central core for finance, though without commanding universal assent. Like most economic claims, EMH comes in many forms, some weaker, others stronger. The weaker versions typically claim that deliberate stock picking does not on average outperform selecting stocks randomly, such as by throwing darts at the financial page. The market already incorporates information about the value of companies into the stock prices, and no one individual can beat this information, other than by random luck, or perhaps by outright insider trading.

Note that the weak version of EMH requires few assumptions about rationality. Many market participants may be grossly irrational or systematically biased in a variety of ways. It must be the case, however, that their irrationalities are unpredictable to the remaining rational investors. If the irrationalities were predictable, rational investors could make systematic extra-normal profits with some trading rule. The data, however, suggest that it is very hard for rational investors to outperform the market averages. This suggests that extant irrationalities are either very small, or very hard to predict, two very different conclusions. The commitment that one of these conclusions must be true does not involve much of a substantive position on the rationality front.

The stronger forms of EMH claim that market prices accurately reflect the fundamental values of corporations and thus cannot be improved upon. This does involve a differing and arguably stronger commitment to a notion of rationality.

Strong EMH still allows that most individuals may be irrational, regardless of how we define that concept. These individuals could literally be behaving on a random basis, or perhaps even deliberately counter to standard rationality assumptions. It is assumed, however, that at least one individual does have rational information about how much stocks are worth. Furthermore, and most importantly, it is assumed that capital markets are perfect or nearly perfect. With perfect capital markets, the one rational individual will overwhelm the influence of the irrational on stock prices. If the stock ought to be worth $30 a share, but irrational “noise traders” push it down to $20 a share, the person who knows better will keep on buying shares until the price has risen to $30. With perfect capital markets, there is no limit to this arbitrage process. Even if the person who knows better has limited wealth, he or she can borrow against the value of the shares and continue to buy, making money in the process and pushing the share price to its proper value.

So the assumptions about rationality in strong EMH are tricky. Only one person need be rational, but through perfect capital markets, this one person will have decisive weight on market prices. As noted above, this can be taken as either an extreme or modest assumption. While no one believes that capital markets are literally perfect, they may be “perfect enough” to allow the rational investors to prevail.

“Behavioral finance” is currently a fad in financial theory, and in the eyes of many it may become the new mainstream. Behavioral finance typically weakens rationality assumptions, usually with a view towards explaining “market anomalies.” Almost always these models assume imperfect capital markets, to prevent a small number of rational investors from dwarfing the influence of behavioral factors. Robert J. Shiller claims that investors overreact to very small pieces of information, causing virtually irrelevant news to have a large impact on market prices. Other economists argue that some fund managers “churn” their portfolios, and trade for no good reason, simply to give their employers the impression that they are working hard. It appears that during the Internet stock boom, simply having the suffix “dot com” in the firm’s name added value on share markets, and that after the bust it subtracted value.11

Behavioral models use looser notions of rationality than does EMH. Rarely do behavioral models postulate outright irrationality, rather the term “quasi-rationality” is popular in the literature. Most frequently, a behavioral model introduces only a single deviation from classical rationality postulates. The assumption of imperfect capital markets then creates the possibility that this quasi-rationality will have a real impact on market phenomena.

The debates between the behavioral theories and EMH now form the central dispute in modern financial theory. In essence, one vision of rationality — the rational overwhelm the influence of the irrational through perfect capital markets — is pitted against another vision — imperfect capital markets give real influence to quasi-rationality. These differing approaches to rationality, combined with assumptions about capital markets, are considered to be eminently testable.

Game theory and the failed quest for a unique basis for rationality:

Game theory has shown economists that the concept of rationality is more problematic than they had previously believed. What is rational depends not only on the objective features of the problem but also depends on what actors believe. This short discussion has only scratched the surface of how beliefs may imply very complex solutions, or multiple solutions. Sometimes the relevant beliefs, for instance, are beliefs about the out-of-equilibrium behavior of other agents. These beliefs are very hard to model, or it is very hard to find agreement among theorists as to how they should be modeled.

In sum, game theorists spend much of their time trying to figure out what rationality means. They are virtually unique amongst economists in this regard. Game theory from twenty years ago pitted various concepts of rationality against each other in purely theoretical terms. Empirical results had some feedback into this process, such as when economists reject Nash equilibrium for some of its counterintuitive predictions, but it remains striking how much of the early literature does not refer to any empirical tests. This enterprise has now become much more empirical, and more closely tied to both computational science and experimental economics.

Computational economics and the failed quest for a unique basis for rationality:

Nonetheless it is easy to see how the emphasis on computability puts rationality assumptions back on center stage, and further breaks down the idea of a monolithic approach to rationality. The choice of computational algorithm is not given a priori, but is continually up for grabs. Furthermore the choice of algorithm will go a long way to determining the results of the model. Given that the algorithm suddenly is rationality, computational economics forces economists to debate which assumptions about procedural rationality are reasonable or useful ones.

The mainstream criticism of computational models, of course, falls right out of these issues. Critics believe that computational models can generate just about “any” result, depending on the assumptions about what is computable. This would move economics away from being a unified science. Furthermore it is not clear how we should evaluate the reasonableness of one set of assumptions about computability as opposed to another set. We might consider whether the assumptions yield plausible results, but if we already know what a plausible result consists of, it is not clear why we need computational theories of rationality.

As you can tell from my comments, I do not believe there is any unique basis for “rationality” in economics. Humans are flawed information processing units produced by the random vagaries of evolution. Not only are we different from each other, but these differences arise both from genes and the individual paths taken through life. Can a complex system comprised of such creatures be modeled through simple equations describing a few coarse grained variables? In some rare cases, perhaps yes, but in most cases, I would guess no. Finance theory already adopts this perspective in insisting on a stochastic (random) component in any model of security prices. Over sufficiently long timescales even the properties of the random component are not constant! (Hence, stochastic volatility, etc.)

Written by infoproc

July 30, 2007 at 4:38 pm

From physics to finance

with 7 comments

Professor Akash Bandyopadhyay recounts his career trajectory from theoretical physics to Wall Street to the faculty of the graduate school of business at Chicago in this interview.

One small comment: Bandyopadhyay says below that banks hire the very best PhDs from theoretical physics. I think he meant to say that, generally, they hire the very best among those who don’t find jobs in physics. Unfortunately, few are able to find permanent positions in the field.

Mike K. — if you’re reading this, why didn’t you reply to the guy’s email? 🙂

CB: Having a Ph.D. in Theoretical Physics, you certainly have quite a unique background compared to most other faculty members here at the GSB. Making a transition from Natural Science to Financial Economics and becoming a faculty member at the most premier financial school in the world in a short span of five years is quite an unbelievable accomplishment! Can you briefly talk about how you ended up at the GSB?

AB: Sure. It is a long story. In 1999, I was finishing up my Ph.D. in theoretical physics at the University of Illinois at Urbana Champaign when I started to realize that the job situation for theoretical physicists is absolutely dismal. Let alone UIUC, it was very difficult for physicists from even Harvard or Princeton to find decent jobs. As a matter of fact, once, when I was shopping at a Wal-Mart in the Garden State, I bumped into a few people who had Ph.D. in theoretical physics from Princeton and they were working at the Wal-Mart’s check-out counter. Yes, Wal-Mart! I could not believe it myself!

CB: So, what options did you have at that point?

AB: When I started to look at the job market for theoretical physicists, I found that the top investment banks hire the very best of the fresh Ph.D.s. I started to realize that finance (and not physics!) is the heart of the real world and Wall Street is the hub of activity. So, I wanted to work on Wall Street – not at Wal-Mart! (laughs!)

I knew absolutely nothing about finance or economics at that time, but I was determined to make the transition. I got a chance to speak with Professor Neil Pearson, a finance professor at UIUC, who advised me to look at the ‘Risk’ Magazine and learn some finance by myself. There were two highly mathematical research papers at the end of an issue that caught my attention. Having a strong mathematical background, I could understand all the mathematical and statistical calculations/analysis in those papers, although I could not comprehend any of the financial terminology. As I perused more articles, my confidence in my ability to solve mathematical models in finance grew. At that point, I took a big step in my pursuit of working on the Street and e-mailed the authors of those two articles in the Risk Magazine, Dr. Peter Carr at the Banc of America Securities and Dr. Michael Kamal at Goldman Sachs. Dr. Carr (who, later on I found, is a legend in mathematical finance!), replied back in 2 lines: ‘If you really want to work here, you have to walk on water. Call me if you are in the NYC area.’

CB: So, we presume you went to NYC?

AB: After some contemplation, I decided to fly to NYC; I figured I had nothing to lose. Dr. Carr set me up for an interview a few weeks later. Being a physics student throughout my life, I was not quite aware of the business etiquettes. So, when I appeared in my jeans, T-shirt and flip-flops at the Banc of America building at 9 West 57th Street, for an interview, there was a look on everyone’s face (from the front desk staffs to everyone I met) that I can never forget. Looking back, I still laugh at those times.

CB: Did you get an offer from Banc of America?

AB: Not at the first attempt. After the interview, I was quite positive that I would get an offer. However, as soon as I returned home, I received an email from Dr. Carr saying, “You are extremely smart, but the bank is composed of deal makers, traders, marketers, and investment bankers. We are looking for someone with business skills. You will not fit well here.” He suggested that we both write a paper on my derivation of Black-Scholes/Merton partial differential equation, or even possibly a book. He also suggested I read thoroughly (and to work out all the problems of) the book “Dynamic Asset Pricing Theory” by Darrell Duffie. In fact, Duffie’s book was my starting point in learning financial economics. I assume your readers never heard of this book. It is a notoriously difficult book on continuous time finance and it is intended for the very advanced Ph.D. students in financial economics. But, it was the right book for me – I read it without any difficulty in the math part and it provided me with a solid foundation in financial economics. Anyway, I think I am going too off tangent to your question.

CB: So, what did you do after you received that mail from Dr. Carr?

AB: The initial set back did not deter me. I already started to become aware of my lack of business skills. So I offered Dr. Carr to work as an unpaid intern at Banc of America to gain experience and to learn more about the financial industry and the business. Dr. Carr finally relented and made me an offer to work as an unpaid intern in his group during the summer of 1999.

CB: What did you do during the internship?

AB: Upon my arriving, Dr. Carr told me that, “A bank is not a place to study. A bank is a place to make money. Be practical.” This was probably the best piece of advice I could get. He gave me three tasks to help me get more familiar with finance and get closer to bankers. First, catalog and classify his books and papers on finance and at the same time flip through them. This way, believe it or not, I read tens of thousands of papers and other books that summer. Second, I helped test a piece of software, Sci-Finance, which would help traders to set and hedge exotic option prices. Thirdly, I answered math, statistics, and other quantitative modeling questions for equity, fixed income and options traders, and other investment bankers.

CB: Wow! That is a lot of reading for one summer. So, did you get a full time offer from Banc of America after your internship? What did you do after that?

AB: Yes, I got an offer for them, but then I had more than a year left to finish my PhD thesis, so I accepted an even better offer from Deutsche Bank next summer. I worked at Deutsche for three months in the summer of 2000. Then moved to Goldman Sachs for a while (where I gave seminars on finance theory to the quants, traders, and risk managers), then, after finishing my Ph.D., I took an offer from Merrill Lynch as the quant responsible for Convertible Bond valuation in their Global Equity Linked Products division in New York. I left Merrill after a few months to lead the North America’s Equity Derivatives Risk Management division in Société Generale. So, basically, I came to GSB after getting some hardcore real-world experience in a string of top investment banks.

CB: Are there any ‘special’ moments on Wall Street that you would like to talk about?

AB: Sure, there are many. But one that stands out is the day I started my internship at Banc of America. As is the norm in grad school or academia, I felt that I had to introduce myself to my colleagues. So, on my very first day of internship, I took the elevator to the floor where the top bosses of the bank had offices. I completely ignored the secretary at the front desk, knocked on the CEO and CFO’s door, walked in, and briefly introduced myself. Little did I know that this was not the norm in the business world!!! Shortly thereafter, Dr. Carr called me and advised that I stick to my cube instead of ‘just wandering around’! In retrospect, that was quite an experience!

CB: What made you interested in teaching after working for top dollar on Wall Street?

AB: You mean to say that professors here don’t get paid top dollar? (laughs)

I always planned to be in academia. To be totally honest with you, I never liked the culture of Wall Street. Much of the high profile business in Wall Street heavily relies on the academic finance research, but, after all, they are there to make money, not to cultivate knowledge. One must have two qualities to succeed well in this financial business: First, one must have a solid knowledge on the strengths and limitations of financial models (and the theory), which comes from cutting edge academic research, and second, one must have the skills to translate the academic knowledge into a money-making machine. I was good in the first category, but not as good in the second. …

Written by infoproc

July 28, 2007 at 8:00 pm

Posted in careers, finance, physics, quants


with 3 comments

I generally try to keep this blog free of kid pictures, but I found these old ones recently and couldn’t resist!

Written by infoproc

July 28, 2007 at 4:15 pm

Posted in babies

Humans eke out poker victory

leave a comment »

But only due to a bad decision by the human designers of the robot team! 🙂

Earlier post here.

NYTimes: The human team reached a draw in the first round even though their total winnings were slightly less than that of the computer. The match rules specified that small differences were not considered significant because of statistical variation. On Monday night, the second round went heavily to Polaris, leaving the human players visibly demoralized.

“Polaris was beating me like a drum,” Mr. Eslami said after the round.

However, during the third round on Tuesday afternoon, the human team rebounded, when the Polaris team’s shift in strategy backfired. They used a version of the program that was supposed to add a level of adaptability and “learning.”

Unlike computer chess programs, which require immense amounts of computing power to determine every possible future move, the Polaris poker software is largely precomputed, running for weeks before the match to build a series of agents called “bots” that have differing personalities or styles of play, ranging from aggressive to passive.

The Alberta team modeled 10 different bots before the competition and then chose to run a single program in the first two rounds. In the third round, the researchers used a more sophisticated ensemble of programs in which a “coach” program monitored the performance of three bots and then moved them in and out of the lineup like football players.

Mr. Laak and Mr. Eslami won the final round handily, but not before Polaris won a $240 pot with a royal flush than beat Mr. Eslami’s three-of-a-kind. The two men said that Polaris had challenged them far more than their human opponents.

Written by infoproc

July 26, 2007 at 8:42 pm

Posted in ai, poker

Man vs machine: live poker!

leave a comment »

This blog has live updates from the competition. See also here for a video clip introduction. It appears the machine Polaris is ahead of the human team at the moment.

The history of AI tells us that capabilities initially regarded as sure signs of intelligence (“machines will never play chess like a human!”) are discounted soon after machines master them. Personally I favor a strong version of the Turing test: interaction which takes place over a sufficiently long time that the tester can introduce new ideas and watch to see if learning occurs. Can you teach the machine quantum mechanics? At the end will it be able to solve some novel problems? Many humans would fail this Turing test 🙂

Earlier post on bots invading online poker.


World-Class Poker Professionals Phil Laak and Ali Eslami
Computer Poker Champion Polaris (University of Alberta)

Can a computer program bluff? Yes — probably better than any human. Bluff, trap, check-raise bluff, big lay-down — name your poison. The patience of a monk or the fierce aggression of a tiger, changing gears in a single heartbeat. Polaris can make a pro’s head spin.

Psychology? That’s just a human weakness.

Odds and calculation? Computers can do a bit of that.

Intimidation factor and mental toughness? Who would you choose?

Does the computer really stand a chance? Yes, this one does. It learns, adapts, and exploits the weaknesses of any opponent. Win or lose, it will put up one hell of a fight.

Many of the top pros, like Chris “Jesus” Ferguson, Paul Phillips, Andy Bloch and others, already understand what the future holds. Now the rest of the poker world will find out.

Written by infoproc

July 25, 2007 at 4:02 pm

Posted in ai, poker, turing test

What is a quant?

leave a comment »

The following log entry, which displays the origin of and referring search engine query for a pageload request to this blog, does not inspire confidence. Is the SEC full of too many JD’s and not enough people who understand monte carlo simulation and stochastic processes? (U.S. Securities & Exchange Commission)

District Of Columbia, Washington, United States, 0 returning visits

Date Time WebPage

24th July 2007 10:04:52
referer: is a quants&btnG=Search

24th July 2007 12:11:59
referer: Munger and the pricing of derivatives&btnG=Google Search

Written by infoproc

July 24, 2007 at 7:31 pm

Posted in finance, quants, sec

Income inequality and Marginal Revolution

leave a comment »

Tyler Cowen at Marginal Revolution discusses a recent demographic study of who, exactly, the top US wage earners are. We’ve discussed the problem of growing US income inequality here before.

To make the top 1 percent in AGI (IRS: Adjusted Gross Income), you needed to earn $309,160. To make it to the top 0.1 percent, you needed $1.4 million (2004 figures).

Here’s a nice factoid:

…the top 25 hedge fund managers combined appear to have earned more than all 500 S&P 500 CEOs combined (both realized and estimated).

Somewhat misleading, as this includes returns on the hedgies’ own capital invested as part of their funds. But, still, you get the picture of our gilded age 🙂

One of the interesting conclusions from the study is that executives of non-financial public companies are a numerically rather small component of top earners, comprising no more than 6.5%. Financiers comprise a similar, but perhaps larger, subset. Who are the remaining top earners? The study can’t tell! (They don’t know.) Obvious candidates are doctors in certain lucrative specialties, sports and entertainment stars and owners of private businesses. The category which I think is quite significant, but largely ignored, is founders and employees of startups that have successful exits. Below is the comment I added to Tyler’s blog:

The fact that C-level execs are not the numerically dominant subgroup is pretty obvious. The whole link between exec compensation and inequality is a red herring (except in that it symbolizes our acceptance of winner take all economics).

I suspect that founders and early employees of successful private companies (startups) that have a liquidity event (i.e., an IPO or acquisition) are a large subset of the top AGI group. Note, though, that this population does not make it into the top tier (i.e., top 1 or .1%) with regularity, but rather only in a very successful year (the one in which they get their “exit”). Any decent tech IPO launches hundreds of employees into the top 1 or even .1%.

It is very important to know what fraction of the top group are there each year (doctors, lawyers, financiers) versus those for whom it is a one-time event (sold the business they carefully built over many years). If it is predominantly the latter it’s hard to attribute an increase in top percentile earnings to unhealthy inequality.

To be more quantitative: suppose there are 1M employees at private companies (not just in technology, but in other industries as well) who each have a 10% chance per year of participating in a liquidity event that raises their AGI to the top 1% threshold. That would add 100k additional top earners each year, and thereby raise the average income of that group. If there are 150M workers in the US then there are 1.5M in the top 1%, so this subset of “rare exit” or employee stock option beneficiaries would make up about 7% of the total each year (similar to the corporate exec number). But these people are clearly not part of the oligarchy, and if the increase in income inequality is due to their shareholder participation, why is that a bad thing?

We reported earlier on the geographic distribution of income gains to the top 1 percent: they are concentrated in tech hotbeds like silicon valley, which seems to support our thesis that the payouts are not going to the same people every year.

Written by infoproc

July 23, 2007 at 1:05 am

Many Worlds: A brief guide for the perplexed

with 2 comments

I added this to the earlier post 50 years of Many Worlds and thought I would make it into a stand alone post as well.

Many Worlds: A brief guide for the perplexed

In quantum mechanics, states can exist in superpositions, such as (for an electron spin)

(state)   =   (up)   +   (down)

When a measurement on this state is performed, the Copenhagen interpretation says that the state (wavefunction) “collapses” to one of the two possible outcomes:

(up)     or     (down),

with some probability for each outcome depending on the initial state (e.g., 1/2 and 1/2 of measuring up and down). One fundamental difference between quantum and classical mechanics is that even if we have specified the state above as precisely as is allowed by nature, we are still left with a probabilistic prediction for what will happen next. In classical physics knowing the state (e.g., position and velocity of a particle) allows perfect future prediction.

There is no satisfactory understanding of how or exactly when the Copenhagen wavefunction “collapse” proceeds. Indeed, collapse introduces confusing issues like consciousness: what, exactly, constitutes an “observer”, capable of causing the collapse?

Everett suggested we simply remove wavefunction collapse from the theory. Then the state evolves in time always according to the Schrodinger equation. Suppose we follow our electron state through a device which measures its spin. For example: by deflecting the electron using a magnetic field and recording the spin-dendent path of the deflected electron using a detector which amplifies the result. The result is recorded in some macroscopic way: e.g., a red or green bulb lights up depending on whether deflection was up or down. The whole process is described by the Schrodinger equation, with the final state being

(state)   =   (up) (device recorded up)   +   (down) (device recorded down)

Here “device” could, but does not necessarily, refer to the human or robot brain which saw the detector bulb flash. What matters is that the device is macroscopic and has a large (e.g., Avogadro’s number) number of degrees of freedom. In that case, as noted by Everett, the two sub-states of the world (or device) after the measurement are effectively orthogonal (have zero overlap). In other words, the quantum state describing a huge number of emitted red photons and zero emitted green photons is orthogonal to the complementary state.

If a robot or human brain is watching the experiment, it perceives a unique outcome just as predicted by Copenhagen. Success! The experimental outcome is predicted by a simpler (sans collapse) version of the theory. The tricky part: there are now necessarily parts of the final state (wavefunction) describing both the up and down outcomes (I saw red vs I saw green). These are the many worlds of the Everett interpretation.

Personally, I prefer to call it No Collapse instead of Many Worlds — why not emphasize the advantageous rather than the confusing part of the interpretation?

Do the other worlds exist? Can we interact with them? These are the tricky questions remaining…

Some eminent physicists who (as far as I can tell) believe(d) in MW: Feynman, Gell-Mann, Hawking, Steve Weinberg, Bryce DeWitt, David Deutsch, Sidney Coleman … In fact, I was told that Feynman and Gell-Mann each claim(ed) to have independently invented MW, without any knowledge of Everett!

Written by infoproc

July 23, 2007 at 12:26 am

Man vs machine: poker

with 4 comments

It looks like we will soon add poker to the list of games (chess, checkers, backgammon) at which machines have surpassed humans. Note we’re talking about heads up play here. I imagine machines are not as good at playing tournaments — i.e., picking out and exploiting weak players at the table.

How long until computers can play a decent game of Go?

Associated Press: …Computers have gotten a lot better at poker in recent years; they’re good enough now to challenge top professionals like Laak, who won the World Poker Tour invitational in 2004.

But it’s only a matter of time before the machines take a commanding lead in the war for poker supremacy. Just as they already have in backgammon, checkers and chess, computers are expected to surpass even the best human poker players within a decade. They can already beat virtually any amateur player.

“This match is extremely important, because it’s the first time there’s going to be a man-machine event where there’s going to be a scientific component,” said University of Alberta computing science professor Jonathan Schaeffer.

The Canadian university’s games research group is considered the best of its kind in the world. After defeating an Alberta-designed program several years ago, Laak was so impressed that he estimated his edge at a mere 5 percent. He figures he would have lost if the researchers hadn’t let him examine the programming code and practice against the machine ahead of time.

“This robot is going to do just fine,” Laak predicted.

The Alberta researchers have endowed the $50,000 contest with an ingenious design, making this the first man-machine contest to eliminate the luck of the draw as much as possible.

Laak will play with a partner, fellow pro Ali Eslami. The two will be in separate rooms, and their games will be mirror images of one another, with Eslami getting the cards that the computer received in its hands against Laak, and vice versa.

That way, a lousy hand for one human player will result in a correspondingly strong hand for his partner in the other room. At the end of the tournament the chips of both humans will be added together and compared to the computer’s.

The two-day contest, beginning Monday, takes place not at a casino, but at the annual conference of the Association for the Advancement of Artificial Intelligence in Vancouver, British Columbia. Researchers in the field have taken an increasing interest in poker over the past few years because one of the biggest problems they face is how to deal with uncertainty and incomplete information.

“You don’t have perfect information about what state the game is in, and particularly what cards your opponent has in his hand,” said Dana S. Nau, a professor of computer science at the University of Maryland in College Park. “That means when an opponent does something, you can’t be sure why.”

As a result, it is much harder for computer programmers to teach computers to play poker than other games. In chess, checkers and backgammon, every contest starts the same way, then evolves through an enormous, but finite, number of possible states according to a consistent set of rules. With enough computing power, a computer could simply build a tree with a branch representing every possible future move in the game, then choose the one that leads most directly to victory.

…The game-tree approach doesn’t work in poker because in many situations there is no one best move. There isn’t even a best strategy. A top-notch player adapts his play over time, exploiting his opponent’s behavior. He bluffs against the timid and proceeds cautiously when players who only raise on the strongest hands are betting the limit. He learns how to vary his own strategy so others can’t take advantage of him.

That kind of insight is very hard to program into a computer. You can’t just give the machine some rules to follow, because any reasonably competent human player will quickly intuit what the computer is going to do in various situations.

“What makes poker interesting is that there is not a magic recipe,” Schaeffer said.

In fact, the simplest poker-playing programs fail because they are just a recipe, a set of rules telling the computer what to do based on the strength of its hand. A savvy opponent can soon gauge what cards the computer is holding based on how aggressively it is betting.

That’s how Laak was able to defeat a program called Poker Probot in a contest two years ago in Las Vegas. As the match progressed Laak correctly intuited that the computer was playing a consistently aggressive game, and capitalized on that observation by adapting his own play.

Programmers can eliminate some of that weakness with game theory, a branch of mathematics pioneered by John von Neumann, who also helped develop the hydrogen bomb. In 1950 mathematician John Nash, whose life inspired the movie “A Brilliant Mind,” showed that in certain games there is a set of strategies such that every player’s return is maximized and no player would benefit from switching to a different strategy.

In the simple game “Rock, Paper, Scissors,” for example, the best strategy is to randomly select each of the options an equal proportion of the time. If any player diverted from that strategy by following a pattern or favoring one option over, the others would soon notice and adapt their own play to take advantage of it.

Texas Hold ’em is a little more complicated than “Rock, Paper, Scissors,” but Nash’s math still applies. With game theory, computers know to vary their play so an opponent has a hard time figuring out whether they are bluffing or employing some other strategy.

But game theory has inherent limits. In Nash equilibrium terms, success doesn’t mean winning — it means not losing.

“You basically compute a formula that can at least break even in the long run, no matter what your opponent does,” Billings said.

That’s about where the best poker programs are today. Though the best game theory-based programs can usually hold their own against world-class human poker players, they aren’t good enough to win big consistently.

Squeezing that extra bit of performance out of a computer requires combining the sheer mathematical power of game theory with the ability to observe an opponent’s play and adapt to it. Many legendary poker players do that by being experts of human nature. They quickly learn the tics, gestures and other “tells” that reveal exactly what another player is up to.

A computer can’t detect those, but it can keep track of how an opponent plays the game. It can observe how often an opponent tries to bluff with a weak hand, and how often she folds. Then the computer can take that information and incorporate it into the calculations that guide its own game.

“The notion of forming some sort of model of what another player is like … is a really important problem,” Nau said.

Computer scientists are only just beginning to incorporate that ability into their programs; days before their contest with Laak and Eslami, the University of Alberta researchers are still trying to tweak their program’s adaptive elements. Billings will say only this about what the humans have in store: “They will be guaranteed to be seeing a lot of different styles.”

Written by infoproc

July 22, 2007 at 3:56 am

Posted in ai, poker