[AI@50]
Filene Auditorium, Moore Hall
Dartmouth College
Hanover, NH
Conference notes by Meg Houston Maker
James Moor, intro: Chess was thought to be difficult, so that if one could master a chess program one had achieved something. However, it turns out games are reasonably easy to master, and areas like natural language are much harder. Moor plays a video clip of Marvin Minsky, who says that chess AI projects had to be focused on the middle game, and the opening had to be programmed, so AI chess was not a very promising simulation of human intelligence.
Jonathan Schaeffer, Alberta
Games as a Test-bed for Artificial Intelligence Research
Marvin Minsky is WRONG WRONG WRONG! But he's not even here today to hear me say it! [Minsky left the conference yesterday.]
Building a chess program was viewed as a grand challenge of AI research. It was a goal that seemed attainable, and worthwhile, and was something that the public could relate to (unlike missle trajectories). This was a coup for AI, because this made it accessible to the media. The first computer chess tournaments started in 1970. So this is really the longest-running experiement in AI, and we can see the evolution of successes. Also, chess products were AI's first big commercial success.
Schaeffer clarifies he's not a games researcher -- he's an AI researcher who uses games as his testbed, rather than defense or engineering proglems, etc. He takes an application and does whatever it takes to build a powerful and successful program. It's an overall strategy of building a high-performance system.
In the chess world, we have seen lots of effort in the last 40-50 years. There was a lot of effort that went into building a grand master chess program. It took a lot of effort and money to build it. Visionaries include Claude Shannon, Alan Turing, John McCarthy, Newell and Simon. They underestimated the challenge!
But it turns out that to make a winning chess program, you need an Alpha-beta search algorithm, an evaluation function to decide good and bad chess positions (these are pretty simple), and fast computing hardware. Wtih hindshigt, this all seems obvious, but it was not evident until the 1980s. Hardware was the key to Deep Blue's success. It had 512 special "chess chips" running in parallel. It was a very fast parallel process. But it's an idiot-savant: it plays brilliant chess, but it can't do anything else.
Brute-force search: use a comptuer to do fast searching. Many researchers felt this was not actually AII because it's not how a human would play chess. But there's no argument that can be made that says humans play chess the "right" way. Computer hardware is fundamentally different from hnuman hardwared, so it shouldn't be surprising that these machines operate differently in solving the same problem.
So one of the most profound contributions of chess is the effectiveness of brute force search. It's simple, elegant, and a good match fo the capabilities of the computer. Other AI chess contributions include search enhancements, hardwares colutions, and an appreciation for the difficulty of building high-performance AI systems.
Chess itself was not as interesting for AI researcher (limited, 2-player game) as other games, which were more representative of the real world, involving randomness, etc.
Checkers: Arthur Samuel used checkers for pioneering AI research. This work, from the 1950s and 1960s, is still cited today. Marion Tinsley was a checkers grand master who only lost 3 games in 40 years, but he was beaten in 1994 by Schaeffer's team developed. This system earned the right to play Tinsley by winning up through competition.
Other games: Othello is another game in which the AI machine version completely overwhelmed the human chamption. Backgammon and TD-gammon, a neural-net program, showed other successes. Scrabble also fell (1998), using Brian Sheppard's Maven. To a computer, words are just sequences of letters. Crossword puzzles (1999): Michael Littman and a team built Proverb by building a database of past crossword puzzles. It turns out about 1/3 of clues are repeats from previous puzzles. So just looking up clues can get you 30% performance. If you take the clues and send them to an internet search engine, you get the result pretty quickly. The program does 96% on the NYTimes Crossword Puzzle, without understanding the meanings (semantics) of the clues at all. Poker, Bridge, and Shogi AI products are coming soon. Go still needs a lot of work.
Games are great becuase you have no trouble attracting grad students!
But chess is the past. So what's going on now? Commercial computer games are now a $25 billion a year industry. This isthe new grand challenge in using games as an experimental testbed. Interactive games are the killer app for human-level AI (see John Laird and Michael van Lent).
Example game: Oblivion. It boasts "radiant AI" with realistic characters. Schaeffer plays a clip that is laughably unrealistic. Characters don't react in naturalistic ways to actions in the game.
Why is Game AI Hard?
Games have to be developed to run on a 2-year-old computer, and can't use the whole CPU (just 10-20%). You have to use limited memory and limited disk, and the program has to be thoroughly tested. You need real-time response (no long computing times). Content generation is the dominant cost in R&D. Realism is essential, and the game has to be fun. The Academic AI community doesn't develop solutions useful in the game AI community. Researchers think nothing of using lots of memory, long processing times, etc.
Random numbers are the most powerful AI tool. Because from a random sequence of events, users discern intelligent behavior. It's not truly random, it's controlled; it's not as if the character walks randomly choosing directions. Rather, it's controlled in that having made a random decision, the character's next decision is consistent with that first decision. So it looks like flow, it looks naturalistic to users.
Obstacles to Quality AI in Gaming
There is little research money in industry, and the game industry is suspicious of academic research: about 90% of what's published as "useful for games" is not actually usable by the gaming AI community.
Want a challenge?
Get rid of your fast hardware, use little time and memory, try to create realism and give real-time response. Human-level AI is needed today.
Danny Kopec, Brooklyn
Chess and AI
What you see in matches between humans and computers relies on human frailties. Machines can learn from humans, and humans can learn from machines.
Chess is very much alive. It hasn't really been solved yet. In May 1997, IBM's Deeper Blue defeated Kasparov, but Kopec doesn't put much stock into this, because it was a very quick match, and Kasparov changed his usual strategy, and the machine exploited that. Kopec gives many other examples of chess matches between humans and computers over the last 5-10 years. Results are mixed, but adding complexity is that the tournaments and exhibitions are being run often with times controls -- 60- or 90-minute time control (match length) with a 10- or 30-second increment (time to make a move).
Is the machine "thinking" when it's calculating? There is disagreement here. There's nothing to say that they have to "think" the same as humans. Kopec shows many examples in which the right play is counterintuitive. Humans play by heuristics, experience, knowledge, intuition, knowledge, and pattern matching. Human chess involves psychology: gambling your own knowledge against your opponent's knowledge. Humans search what's important on the board, and know how to choose what's important. Chess is way more than search.
Comments