QUEST Community Science Blog Author: Dan Gillick

All Posts by Dan:

Poker Research: the Next Hot Topic for Supercomuting?

September 21st, 2009 by Dan Gillick

Visualization of possible chess move sequences (try it here)

Artificial Intelligence has always held a special affinity for games. Chess, in particular, was long considered a realm reserved for exquisite human intelligence: the greatest chess players are called Grandmasters; a large percentage of them are eccentric Russian introverts. Gary Kasparov's defeat, by IBM's specialized supercomputer Deep Blue in 1997, was heralded as a major milestone (he contends the match was unfair). But while the dominance of chess-playing software is culturally significant, does it matter for AI?

Chess, like Checkers, Connect-4, and Go, is a game of perfect information. That is, everything useful for choosing your next move is right there on the board (it would be nice to know what your opponent will do next, but you can assume that your opponent is just trying to make the best possible move too). If you had a computer powerful enough, it could consider every possible next move, every possible response, and so on, and finally deduce, absolutely, how to guarantee a particular outcome. To do this is to solve chess, to answer the question: is it possible for white to force a win? Checkers is solved (both players can force a draw). Connect-4 is solved (the first player can force a win). Chess has too many possible board positions to be solved anytime soon.

Deep Blue can compete with human players by searching many moves ahead, testing all possible combinations, and choosing the next move that leaves its opponent with the worst best option. This approach is called minimax search. Since the computer can't search through to all possible checkmates, it searches to a given depth and scores the resulting board position by the pieces each player still has (roughly speaking, a pawn is 1 point, knights and bishops are 3 points each, a rook is 5 points, and the queen is 8 points). Using this rubric, or heuristic, and searching 10-15 moves into the future, makes for an extremely formidable opponent.

Minimax theory was established by John von Neumann in 1928 and the algorithm was improved in the 1950s and 60s to run more efficiently. Deep Blue contains no general innovation that improves significantly on these now classic techniques. The heuristic for evaluating boards has been refined, and the program has a huge database of well-known openings and end-game sequences-when 5 or fewer pieces are left on the board. Thus, Deep Blue is less a marvel of Artificial Intelligence than of engineering: its success is a direct product of the number of positions it can consider in a second (200 million). This is the Brute Force method of problem solving at its finest.

Most real world problems are not like chess. Political maneuvering, for example, is a game of imperfect information, where each player must guess at underlying motives and resources from superficial clues. The language of political, and in particular war-time gamesmanship, has shifted markedly away from chess… towards poker. Obama tipped his hand, Chavez is bluffing, Ahmedinejad is all in.

And Artificial Intelligence for poker is still far behind humans. The University of Alberta's Polaris system earned a narrow victory at the 2^nd man-machine poker match last July, but the competition involved heads-up limit poker: one-on-one games where the only possible bets are $10 or $20. Compared with the main event at the World Series of Poker, which has no betting limit, and about 10 players at one table, this is something of a "toy" problem. Recent research focuses on how to model opponents-that is, automatically refining the software's understanding of the meaning of each players' bets as information is gathered about how those players play.

Over the next decade, I would guess that poker research, perhaps backed by military funding, will expand significantly. And unlike Deep Blue, poker software that can dominate a table full of professional players, will be the product of significant advances in the field of Artificial Intelligence.






37.762611, -122.409719




Posted in Engineering | Please Comment

Bay Bridge Rising

July 9th, 2009 by Dan Gillick

Sketch drawing of the proposed San Francisco-Oakland Bay Bridge (1913) from Overland Monthly, April 1913.

The Bay Bridge will be closed from September 3rd at 8:00 p.m. until the 8th at 5:00 a.m. During these 105 hours, Caltrans will perform an "essential and unprecedented construction feat."

It turns out there was a lot I didn't know about the Bay Bridge. Its official name, for example is not the Bay Bridge. It's "The James 'Sunny Jim' Rolph Bridge," after the California Governor who died in 1934, two years before the bridge opened (The Golden Gate Bridge opened 6 months later). Around 280,000 vehicles traverse the bridge every day—nearly $7 in bridge tolls per second; The Yerba Buena Tunnel that connects the eastern and western segments is the world's largest diameter bore tunnel; Much of the eastern span is supported by old growth Douglas Firs, driven into firm mud.

As construction grows increasingly noticeable, the new eastern section rising out of the bay, more people are wondering: How will it attach? What happens to the old bridge? What's with the retrofit of the western suspension? And what is this unprecedented feat of construction happening over Labor Day weekend?

The construction website, baybridge360, just received a Webby award in the Government category, and is worth a visit. Videos and slide shows are overlaid on a satellite image of the bay and provide answers to these and other engineering questions. There's a bit of Troy McClure style narration, epic synthesizer for the construction scenes, and techno pop for the fast-forward time lapse photography. At one point, the “Governator” dons a pair of terminator sunglasses for a ceremonial blowtorching.

The new site may be sleek, but some of the most interesting information is buried in the old stalwart: baybridgeinfo.org. The western span's retrofitting, completed in 2004, added some 17 million pounds of structural steel, and included new rollers between the roadway and the bridge supports. The new eastern segment (slated for rebuilding since a section collapsed in the 1989 Loma-Prieta earthquake) will include the world's longest Self-Anchored Suspension (SAS) bridge, connected to a pier-supported "Skyway" (elevated roadway over a mile of mudflats), sloping down to the "Oakland Touchdown."

The 2,047-foot asymmetric SAS will be supported by a single steel tower, embedded in rock, rising 525 feet above sea level. While most suspension bridges use a pair of cables, the new SAS employs a single cable, anchored on the east side, wrapped over and around the tower, and down to the west. The Skyway is supported by a set of steel pipes, driven 300 feet into deep bay mud by a massive hydraulic hammer.

Amidst the construction clamor, considerable attention is afforded to local wildlife. Dense columns of air bubbles helped dissipate shockwaves from the hammering to ease construction-related stress on local fish. For the birds, platforms under the new east span provide cormorant nesting habitat, and the crew is building a 500 square-foot island for the pleasure of the snowy egret and ruddy turnstone. And at the Oakland touchdown, a turbidity-controlling curtain was installed to protect eelgrass, which in turn serves as a filter, improving water quality.

So consider all this next time you lament the $4 bridge toll. The original 1936 toll, collected in both directions, works out to over $20 in 2009 dollars. The bridge is scheduled for completion in late 2013.




37.804556, -122.3711




Posted in Engineering | Please Comment