Thứ Ba, 31 tháng 7, 2007
computing competitions
Canadian computing competition: The questions in the CCC are algorithmic in nature, designed to test a student's ability to design and code algorithms rather than their ability knowing APIs (such as Swing or AWT). Problems increase greatly in difficulty, where the last question is an IOI level problem. They generally have memory, time or stack constraints (especially in recursion) forcing the programmer to find a more efficient solution to the problem. Usually, most problems contain a hidden loophole that would allows certain inputs to crash the program or produce incorrect results.
AI Reading
From MAA: http://www.maa.org/devlin/
Devlin's Angle
Why 2001 Won't be 2001
This month, January 12, to be precise, sees the birthday of HAL, the mission-control computer on the Jupiter-bound spaceship Discovery in Arthur C. Clarke's celebrated science fiction novel 2001, A Space Odyssey.
According to the book, HAL was commissioned at Urbana, Illinois, on January 12, 1997. In Stanley Kubrick's 1968 movie version, the date of HAL's birth was inexplicably changed to January 12, 1992. In any event, whether HAL is just about to be born or preparing to celebrate its fifth birthday, with the year 2,001 practically upon us, it's natural to ask how correct Clarke and Kubrick's vision of the future has turned out to be.
Thirty years ago when the film was made, director Kubrick endowed HAL with capabilities computer scientists thought would be achieved by the end of the century. With a name that, despite Clarke's claim to the contrary, some observers suggested was a simple derivation of IBM (just go back one letter of the alphabet), HAL was, many believed, science fiction-shortly-to-become-fact.
In the movie, a team of five new millennium space explorers set off on a long journey of discovery to Jupiter. To conserve energy, three of the team members spend most of the time in a state of hibernation, their life-support systems being monitored and maintained by the on-board computer HAL. Though HAL controls the entire spaceship, it is supposed to be under the ultimate control of the ship's commander, Dave, with whom it communicates in a soothingly soft, but emotionless male voice (actually that of actor Douglas Rain). But once the vessel is well away from Earth, HAL shows that it has developed what can only be called a "mind of its own." Having figured out that the best way to achieve the mission for which it has been programmed is to dispose of its human baggage (expensive to maintain and sometimes irrational in their actions), HAL kills off the hibernating crew members, and then sets about trying to eliminate its two conscious passengers. It manages to maneuver one crew member outside the spacecraft and sends him spinning into outer space with no chance of return. Commander Dave is able to save himself only by entering the heart of the computer and manually removing its memory cells. Man triumphs over machine--but only just.
It's a good story. (There's a lot more to it than just described.) But how realistic is the behavior of HAL? We don't yet have computers capable of genuinely independent thought, nor do we have computers we can converse with using ordinary language. True, there have been admirable advances in systems that can perform useful control functions requiring decision making, and there are working systems that recognize and produce speech. But they are all highly restricted in their scope. You get some idea of what is and is not possible when you consider that it has taken AT&T over thirty years of intensive research and development to produce a system that can recognize the three words 'yes', 'no', and 'collect' with an acceptable level of reliability for a range of accents and tones. Despite the oft-repeated claims that "the real thing" is just around the corner, the plain fact is that we are not even close to building computers that can reproduce human capabilities in thinking and using language. And according to an increasing number of experts, we never will.
Despite the present view, at the time 2,001 was made, there was no shortage of expert opinion claiming that the days of HAL ("HALcyon days," perhaps?) were indeed just a few years off. The first such prediction was made by the mathematician and computer pioneer Alan Turing. In his celebrated article Computing Machinery and Intelligence, written in 1950, Turing claimed, "I believe that at the end of the century the use of words and general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted."
Though the last part of Turing's claim seems to have come true, that is a popular response to years of hype rather than a reflection of the far less glamorous reality. There is now plenty of evidence, from psychology, sociology, and from linguistics, to indicate that the original ambitious goals of machine intelligence is not achievable, at least when those machines are electronic computers, no matter how big or fast they get. So how did the belief in intelligent machines ever arise?
Ever since the first modern computers were built in the late 1940s, it was obvious that they could do some things that had previously required an "intelligent mind." For example, by 1956, a group at Los Alamos National Laboratory had programmed a computer to play a poor but legal game of chess. That same year, Allen Newell, Clifford Shaw, and Herbert Simon of the RAND Corporation produced a computer program called The Logic Theorist, which coul--and did--prove some simple theorems in mathematics.
The success of The Logic Theorist immediately attracted a number of other mathematicians and computer scientists to the possibility of machine intelligence. Mathematician John McCarthy organized what he called a "two month ten-man study of artificial intelligence" at Dartmouth College in New Hampshire, thereby coining the phrase "artificial intelligence," or AI for short. Among the participants at the Dartmouth program were Newell and Simon, Minsky, and McCarthy himself. The following year, Newell and Simon produced the General Problem Solver, a computer program that could solve the kinds of logic puzzles you find in newspaper puzzle columns and in the puzzle magazines sold at airports and railway stations. The AI bandwagon was on the road and gathering speed.
As is often the case, the mathematics on which the new developments were based had been developed many years earlier. Attempts to write down mathematical rules of human thought go back to the ancient Greeks, notably Aristotle and Zeno of Citium. But the really big breakthrough came in 1847, when an English mathematician called George Boole published a book called An Investigation of the Laws of Thought. In this book, Boole showed how to apply ordinary algebra to human thought processes, writing down algebraic equation in which the unknowns denoted not numbers but human thoughts. For Boole, solving an equation was equivalent to deducing a conclusion from a number of given premises. With some minor modifications, Boole's nineteenth century algebra of thought lies beneath the electronic computer and is the driving force behind AI.
Another direct descendent of Boole's work was the dramatic revolution in linguistics set in motion by MIT linguist Noam Chomsky in the early 1950s. Chomsky showed how to use techniques of mathematics to describe and analyze the grammatical structure of ordinary languages such as English, virtually overnight transforming linguistics from a branch of anthropology into a mathematical science. At the same time that researchers were starting to seriously entertain the possibility of machines that think, Chomsky opened up (it seemed) the possibility of machines that could understand and speak our everyday language.
The race was on to turn the theories into practice. Unfortunately (some would say fortunately), after some initial successes, progress slowed to a crawl. The result was hardly a failure in scientific terms. For one thing, we do have some useful systems, and they are getting better all the time. The most significant outcome, however, has been an increased understanding of the human mind: how unlike a machine it is and how unmechanical human language use is.
One reason why computers cannot act intelligently is that logic alone does not produce intelligent behavior. As neuroscientist Antonio Damasio pointed out in his 1994 book Descartes' Error, you need emotions as well. That's right, emotions. While Damasio acknowledges that allowing the emotions to interfere with our reasoning can lead to irrational behavior, he presents evidence to show that a complete absence of emotion can likewise lead to irrational behavior. His evidence comes from case studies of patients for whom brain damage--either by physical accident, stroke, or disease--has impaired their emotions but has left intact their ability to perform 'logical reasoning', as verified using standard tests of logical reasoning skill. Take away the emotions and the result is a person who, while able to conduct an intelligent conversation and score highly on standard IQ tests, is not at all rational in his or her behavior. Such people often act in ways highly detrimental to their own well being. So much for western science's idea of a 'coolly rational person' who reasons in a manner unaffected by emotions. As Damasio's evidence indicates, truly emotionless thought leads to behavior that by anyone else's standards is quite clearly irrational.
And as linguist Steven Pinker explained in his 1994 book The Language Instinct, language too is perhaps best explained in biological terms. Our facility for language, says Pinker, should be thought of as an organ, along with the heart, the pancreas, the liver, and so forth. Some organs process blood, others process food. The language organ processes language. Think of language use as an instinctive, organic process, not a learned, computational one, says Pinker.
So, while no one would deny that work in AI and computational linguistics has led to some very useful computer systems, the really fundamental lessons that were learned were not about computers but about ourselves. The research was successful in terms not of engineering but of understanding what it is to be human. Though Kubrick got it dead wrong in terms of what computers would be able to do by 1997, he was right on the mark in terms of what we ultimately discover as a result of our science. 2001 shows the entire evolution of mankind, starting from the very beginnings of our ancestors Homo Erectus and taking us through the age of enlightenment into the present era of science, technology, and space exploration, and on into the then-anticipated future of routine interplanetary travel. Looking ahead forty years to the start of the new millennium, Kubrick had no doubt where it was all leading. In the much discussed--and much misunderstood--surrealistic ending to the movie, Kubrick's sole surviving interplanetary traveler reached the end of mankind's quest for scientific knowledge, only to be confronted with the greatest mystery of all: Himself. In acquiring knowledge and understanding, in developing our technology, and in setting out on our exploration of our world and the universe, said Kubrick, scientists were simply starting on a far more challenging journey into a second unknown: the exploration of ourselves.
The approaching new millennium sees Mankind about to pursue that new journey of discovery. Far from taking away our humanity, as many feared, attempts to get computers to think and to handle language have instead led to a greater understanding of who and what we are. As a human being, I like that. For today's scientist, inner space is the final frontier, a frontier made accessible in part by attempts to build a real-world HAL. As a mathematician, I like that, too. Happy birthday, HAL.
The above celebration of the birth of HAL, the computer in the book and film 2001, is abridged from the book Goodbye Descartes: The End of Logic and the Search for a New Cosmology of Mind, by Keith Devlin, published by John Wiley and Sons in late January, 1997, price $27.95.
The soul of a chess machine -MATHEMATICS AND COMPUTERS
Lessons learned from a contest pitting man against computer
By IVARS PETERSON
It's all over now, but I'll never forget that first chess game. What a smashing victory I won over the human champion! I really had Garry Kasparov sweating.
Here I was, a novice tournament player fresh out of the lab. No outsider, including Kasparov, had seen me play before, and I surprised everyone. Oh, how sweet it was! Of course, it was downhill from there: a loss, two draws, and then two more losses. It's not that Kasparov attacked my pieces and overwhelmed my defenses. He played with amazing restraint and subtlety, quietly moving his pieces until he developed positions in which my options were extremely limited. There wasn't much I could do. Even so, at times I responded brilliantly. I made moves that brought gasps from the experts. They couldn't see what I could, looking more than a dozen moves ahead. I must admit, however, that I did sometimes lose track of what I was supposed to be doing. And I really didn't know enough about chess to understand the nuances of all the positions that Kasparov maneuvered me into. Perhaps I could have done better if I had hooked up with a microcomputer like Chess Genius, who once beat Kasparov in a tournament. Although Chess Genius can't search through the options as deeply as I can, it certainly knows more chess strategy. Well, the reporters and television cameras are gone now. My support staff at IBM is taking a short break. I can't help thinking about what I should do next. Keep training? Go back to school and learn some new skills? Or get a real job, as IBM hopes?
Deep Blue's performance in its six-game match in February against world chess champion Garry Kasparov impressed everyone (SN: 2/24/96, p. 119). "It's a really serious opponent," Kasparov remarked afterwards. "I won... but it was as tough as a world championship match."
That a computer which relies largely on speedily checking the consequences of billions of possible moves could come so close to matching the human capabilities required to play the game at its highest level was a striking achievement for the team that designed, built, and programmed Deep Blue. "What they did is really quite amazing," says Hans Berliner, a computer scientist and chess expert at Carnegie Mellon University in Pittsburgh. "They did much better than I expected. But there's still some work to be done." "We learned a lot from this experience," says Chung-Jen Tan of the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., who directed the Deep Blue effort. "We certainly found a lot of weak points and strengths in our system." There were lessons for Kasparov, too. "I learned not only how to play against a machine but also more about the game of chess," he noted after the match. Kasparov predicts that both chess players and scientists will find great value in studying the games of this match for what they reveal about chess and about the way machines reason.
IBM's Deep Blue project began in 1989 as part of an exploration of novel ways to use arrays of computer processors, all working at the same time while sharing information, to tackle complex problems. The idea was to combine a general-purpose, parallel-processing computer system and special integrated-circuit chips designed for a specific application to create a superior problem-solving machine.
"Our goal . . . was to use chess as a test case," Tan says. The knowledge gained from the chess experiment could then be applied in the design of computer systems for a wide variety of tasks such as analyzing financial data, scheduling cargo shipments, simulating molecular behavior, and managing huge inventories or large investment portfolios. For chess, the researchers created a special move-generating chip that contains more than 1 million transistors and several memory units. It stores values representing the strengths of chess pieces in various arrangements, as well as billions of sequences of moves for ending games when only a few pieces remain on the board. Deep Blue contains 256 of these chips in conjunction with a heavy-duty RS/6000 SP-2 multiprocessing computer. Deep Blue's software, written in the computer language called C, coordinates the actions of the chips. It divides searches among the processors and compiles and reconciles the results to generate the best possible move for any given chess position. In this way, Deep Blue can evaluate about 200 million positions per second, assessing strengths and the pieces' capacity for attack and defense. It assigns a numerical value to each move.
Deep Blue also has access to a database containing sequences of moves made by top chess players at the beginnings of games and another database providing billions of scenarios on how to end a game when only five pieces remain on the chessboard, in addition to its chip-based endgame data.
All this adds up to a complicated, sensitive system, remarks Murray Campbell of the Deep Blue team. Completed only about a month before the match, Deep Blue suffered surprisingly few glitches during the contest. "We were relieved that it worked more or less as it was supposed to," Tan says. Like most chess computers, Deep Blue's strength is in looking ahead. For any arrangement of pieces, it considers all possible moves. Then it evaluates every response its opponent might make to each of those moves, and so on. In a game of 40 moves, the number of different board positions that can develop is at least 10120. There's no way that even the fastest computer can check every possibility to play a perfect game. The number of possible sequences of moves is so large, it easily dwarfs the most generous estimates of the number of atoms in the universe. Thus, to stay within the time limits imposed on games, chess programs can preview only a certain number of moves. When just a few pieces are left on the chessboard, however, the programs can see unambiguously to a game's end. The designers of Deep Blue tried to increase the depth to which their computer could search by dividing its effort among more than 200 processors. However, the particular method used for doing the search--the standard so-called alpha-beta search algorithm--isn't particularly well suited for parallel processing. "My experience in parallel computing is that these [multiprocessor] systems are typically quite inefficient," says T. Anthony Marsland of the University of Alberta in Edmonton. "I would advise [the Deep Blue programmers] to make sure they're getting out of their system all the computing power that's possible in theory. "That [additional power] could give them a computational advantage in critical situations on the chessboard, when Deep Blue needs to look one [step] deeper," he adds. "The probability of error goes down with a deeper search." Researchers are now studying alternative approaches that might help a computer focus its search better and come up with more accurate evaluations of potential moves. At the NEC Research Institute in Princeton, N.J., mathematician Warren D. Smith and his colleagues are working on a "best play for imperfect players" (BPIP) strategy. So far, they have used it only on small computers. According to this method, instead of checking every possible chain of moves, the computer looks down only the lines of play that seem, from the first few possible moves, most promising. Its evaluation takes into account the fact that neither player can see to the end of a game and that neither performs perfectly. Thus, chess moves are given statistical weights rather than numerical values. "My goal with BPIP search is to try to get an approach with more finesse than Deep Blue but more brute force than Garry Kasparov--sort of an intermediate regime," Smith explains. In tests that pitted BPIP searches against traditional alpha-beta searches in less complicated board games such as mancala (where one distributes markers in an array of compartments) and reversi (also known as Othello), the BPIP approach usually won, Smith says. Now, the NEC group is trying to program a chess computer with this strategy.
Though most chess computers rely heavily on speedy, deep searching, they also need good recipes for evaluating the strength of chess positions. Currently, nearly all that information comes from what people have learned in playing the game, and it must be painstakingly programmed into the computer.
Deep Blue showed obvious weaknesses in its ability to evaluate certain types of chess positions, such as not recognizing when pieces needed to be sacrificed. Such deficiencies can be easily corrected by adding more knowledge to the program, Marsland says. But there is a tradeoff. Complicated evaluations slow down the searches, so a balance must be struck between depth of search and complexity of evaluation. So far, depth of search has proved more significant than sophistication of positional analysis in the success of high-level chess computers.
In recent years, however, programmers have made great strides in creating surprisingly competent chess programs that run on personal computers. They have done it by carefully refining and tuning the chess knowledge component to make up for the smaller computers' lack of computing power compared to machines like Deep Blue.
Programs such as Chess Genius and Fritz 4 have shown the way. "I've played some of the micros," Berliner says. "It's amazing how well versed they are in almost all phases of the game. "The best way to improve the evaluation [by the computer] is to keep playing--make some changes and then play the new program against the old one to see what happens," he advises. "That's what the people with the micros have been doing." Some researchers are investigating alternative ways of supplying chess knowledge to a computer. One possibility is to see if they can program computers to learn, just as human players improve their play with experience and study. A few years ago, Robert A. Levinson and his coworkers at the University of California, Santa Cruz developed a computer program, called Morph, that learned to play chess starting only with a list of legal moves. They pitted their novice system against a conventional chess program known as Gnu Chess, which plays about as well as the average tournament player.
After thousands of such games, Morph identified enough patterns to play a reasonable game against a beginning tournament player, even though it looked ahead only to the next move. "It's not really impressive compared to existing chess programs," Levinson says. "But it is impressive given that it was all learned from experience."
Levinson is now working on a new, improved version of Morph. The program is capable of looking ahead several moves and has access to a database of essentially all the games ever played by top chess players. "It finds the chess position it considers most similar to its own position and tries to reason by analogy," Levinson says. "If that position was good, then this position is good. "I think we have a promising model," he adds. "But there's something about a grand master staring at a chessboard that's hard to capture in a computer."
Kasparov's key advantage over Deep Blue was that he could learn, both as a game progressed and between games.
Because Deep Blue had no track record as a chess player, Kasparov could not prepare for this match as he has for other matches by studying his opponent's previously played games. Instead, he built up in his mind a portrait of his computer opponent as they played. "Even though it is a computer, this opponent had its own psychology," Kasparov insisted after the match. "Before each game, I tried to make an opening or strategy . . . based on my knowledge of this opponent." Playing Deep Blue forced Kasparov into an uncharacteristic style of play, most evident in the final game of the match. He had learned to be more precise in judging the quality of his chess positions. He also took care to avoid complications, to refrain from creating targets, and to attack gradually, increasing his advantage little by little until there was nothing left to do but win. "That's an interesting strategy: Just keep improving the quality of your position and don't do anything until you can see [the game] completely to the end," Berliner comments. The usual human judgment isn't good enough against a computer like Deep Blue, Kasparov noted in summing up what he had learned from the match. You can't rely on impressions, he said. You've got to be absolutely sure that you're doing the right thing. This new knowledge is bound to make Kasparov an even more formidable opponent in his matches against human players. "We have not seen him employ this style in the past, but we will certainly see him do so in the future," Berliner says. Top chess player and commentator Maurice Ashley of New York City had the final word: "The world champion is getting tougher from playing a machine."
Silicon Champions of the Game
Computers have conquered tic-tac-toe, checkers, and chess. What's next?
By IVARS PETERSON
The final game of the match lasted barely more than an hour. A rattled Garry Kasparov conceded defeat after falling into a trap that had been set by the IBM chess computer Deep Blue.
Deep Blue's triumph last May marked the first match victory by a chess-playing computer over a reigning world champion (SN: 5/17/97, p. 300). This week, the team of researchers who developed Deep Blue, led by Chung-Jen Tan of the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., received the prestigious Fredkin Prize for Computer Chess. Established in 1980 by computer scientist Edward Fredkin, now at Carnegie Mellon University in Pittsburgh, the $100,000 award honors the first computer program to defeat a world champion in a regulation match.
The victory also represented the culmination of nearly 50 years of scientific and engineering effort. The field of computer chess got its start in 1950 with the ideas of applied mathematician Claude E. Shannon, then at Bell Telephone Laboratories, who proposed the basic search and evaluation strategies that still underlie the way computers generate chess moves.
Since that time, one chess-playing computer after another has held center stage, each eventually falling to a faster, more powerful successor: KAISSA, MAC HACK, CHESS 4.6, Belle (SN: 10/8/83, p. 236), CRAY BLITZ (SN: 10/29/83, p. 276), Hitech (SN: 10/26/85, p. 260), and Deep Thought (SN: 10/28/89, p. 276), the immediate predecessor of Deep Blue.
"The beauty of computer chess was that ideas could be tested in competition," says computer scientist Monty Newborn of McGill University in Montreal. "The good ideas went from one generation to the next, and the bad ideas fizzled out. That's science at its best."
Chess isn't the only game being played by computers at or near the championship level. At this week's Fourteenth National Conference on Artificial Intelligence in Providence, R.I., the Hall of Champions event brought together some of the world's top computer programs playing backgammon, bridge, checkers, chess, Go, Othello, and Scrabble.
"We're at a unique point in time," says Matthew L. Ginsberg of the University of Oregon in Eugene, who organized the event. "Ten years ago, no computers were close to the championship level in any of these games. Now, they even have the edge over human players in several of them. We can have the best computers competing against the best people."
Indeed, anyone can try his or her hand at playing top programs in many games just by going to the World Wide Web. Researchers and game developers monitor play and use the data to improve their programs.
Even in the earliest days of computers, researchers couldn't resist programming them to play games. It was an entertaining way to show off one's programming prowess, to test the computer, and to evaluate the efficacy of various techniques for organizing information in massive databases or searching among a wide range of possibilities to determine the best choice.
Chess was often the chosen battleground, though much simpler games such as tic-tac-toe served as handy programming exercises. Indeed, it's not difficult to write a short computer program that plays tic-tac-toe flawlessly, in effect demonstrating that no matter what the first move, the worst you can do is tie.
In recent years, researchers have solved a number of games similar to, but more challenging than, tic-tac-toe. In connect-4, two players take turns dropping white or black balls into seven tubes, each of which holds a maximum of six balls. The first person to create a line of four balls in a row, column, or diagonal wins. In this game, by playing correctly, the player going first can always win.
Go-Moku (or five-in-a-row), which is played on a 19-by-19 square grid, is also a guaranteed win for the savvy player moving first. The same applies to Qubic, a three-dimensional version of tic-tac-toe played on a 4-by-4-by-4 lattice. In nine-men's morris, an alignment-and-capture game popular in Europe, neither player can be assured of a triumph.
In such solved games, where a good player can recognize all the alternatives for any situation, a computer can be programmed to make the best possible moves at all times, and a win or a draw is guaranteed. Games such as chess, checkers, and Go are, in principle, solvable, and a computer could be programmed to play a perfect game. However, the number of possible moves is so enormous that no existing computer can figure out the entire game from beginning to end.
In the early days of computer chess, some researchers attempted to mimic the way humans play the game, building in pattern recognition, invoking various rules of thumb, and developing criteria for selecting which moves to consider while discarding the rest. However, the programmers found it extremely difficult to furnish the computer with enough knowledge to avoid making major mistakes.
The alternative that proved much more powerful was the brute-force search - simply checking out all the moves. The program looks ahead a fixed number of moves, evaluates the strength of each move, and selects the best one. Adding knowledge about the game and refined algorithms has made searches more responsive to actual game situations and turned this strategy into a remarkably effective mode of operation.
At the same time, the steadily increasing speed of computers has allowed chess programs to search more and more moves into the future. Experiments have clearly demonstrated that the faster the computer, the better a program plays, simply because it can perform a more extensive search. "That's counter to what a lot of people argued a number of years ago," Newborn says.
"The message from chess is profound and widely applicable," says Carnegie Mellon's Hans Berliner. "Brute force is a practical way of doing things." The success of computers like Deep Blue also highlights the fact that the way computers play a game differs fundamentally from the way people play it. From a human perspective, computers sometimes make weird moves; yet more often than not, the best programs somehow manage to succeed in the end.
That difference in style can be very valuable. "We're good at pattern matching, and we're good at applying rules," Ginsberg says. "Machines are good at searching."
"This means that the capabilities of computers are complementary to ours," he continues. "Together, we can solve problems that neither of us can solve individually."
Moreover, "we need to face the fact that things that once could be done only through human intelligence can now be done in other ways as well," says former U.S. chess champion Patrick G. Wolff of Cambridge, Mass. "The intriguing question is, how many things are there like that?"
Even before Deep Blue defeated Kasparov, a program named Chinook had become, in effect, the world checkers champion.
Created by Jonathan Schaeffer of the University of Alberta in Edmonton and his team, the checkers-playing program incorporates the types of search strategies originally developed for chess. It also includes enormous databases covering every possible position that can be reached once there are fewer than a certain number of pieces on the board (SN: 7/20/91, p. 40).
With such databases at its disposal and with the game down to a manageable number of pieces, Chinook can look up all possible outcomes and select an appropriate sequence of moves to ensure a win, maintain a draw, or delay a loss. From then on, it plays flawlessly.
In 1994, Chinook played world checkers champion Marion Tinsley, a retired mathematician from Tallahassee, Fla., and a formidable opponent. Since 1975, he had lost only a handful of the thousands of games he had played in tournaments and exhibition matches. Two of those losses had occurred in 1992, when Tinsley successfully defended his world title against Chinook in a man-versus-machine match of 40 games (SN: 10/3/92, p. 217).
In the 1994 rematch, the first six games between Tinsley and Chinook ended in draws. Then, Tinsley had to resign for health reasons. He was diagnosed as having cancer, and he died a year later.
"Tinsley was without a doubt the best checker player of all time - an absolutely incredible talent," Schaeffer says. Having beaten the top remaining checker players, Chinook qualifies as the current champion.
Whether Chinook could ever have defeated Tinsley remains a nagging question, and Schaeffer has considered the possibility of calculating the game from beginning to end and building a perfect checker player to settle the issue.
"I certainly believe we're capable of solving the game," Schaeffer says. "The technology is here. It's just a matter of committing the time and resources." Chinook is also a research experiment. For instance, Schaeffer and his team have built a database of 444 billion positions - every position with eight or fewer pieces on the board. "This is a vast repository of information. To a checker player, it's a gold mine," he says. Whatever data-mining techniques are developed to sift through the information and identify what's important would benefit many fields.
Meanwhile, Chinook continues to play in tournaments and exhibitions. The only major change in the program since 1994 has been the removal of restrictions that gave it an extremely cautious style specifically designed to counter the near-perfect play of Tinsley.
Instead of achieving draw after draw after boring draw, Chinook has started to play games that are truly exciting, Schaeffer says. "The program's winning percentage has gone up and up, and its losing percentage has remained the same - zero.
"That was a relatively minor change in the [computer program], but it had a dramatic impact on the play," he adds.
The world's top backgammon programs differ markedly from those that play checkers and chess. Instead of relying on brute-force searches, the software incorporates a model brain - an artificial neural network - that allows the program to learn the game from scratch.
In backgammon, two players race their pieces around a track on a rectangular board. Each player uses two dice to determine how far to move one or two pieces at a time with the objective of winning the race by conveying all of one's 15 pieces around the playing surface and off the board.
The neural network approach to playing backgammon was pioneered by IBM's Gerald Tesauro, who created a program called TD-Gammon. "TD" refers to "temporal difference," which describes the program's underlying mathematical recipe for self-learning. "We turn the neural net loose on this task, and it just learns by playing lots and lots of games against itself," Tesauro says. "It learns very well - though some things are learned better than others."
The original concern was that such an approach would lead to a program that lacks flexibility and is unable to cope with unexpected situations presented by players using unconventional tactics. "It actually does very well against all kinds of different strategies," Tesauro says. The random rolls of the dice during the learning phase seem to force the neural network to explore all sorts of situations and develop remarkably robust strategies.
"Unfortunately, there are strategies and situations that never occur when you play just against yourself," says Brian Sheppard, a software developer in Concord, Mass., who is working on a new expert backgammon player. "You have to be told about them. An expert [human] player can make these situations arise with some regularity."
Backgammon nevertheless remains the one major success for automated learning in the domain of games. The neural network approach has generally not worked as well for deterministic games such as chess, checkers, Othello, and Go, which have no element of chance.
Other leading backgammon programs, such as JellyFish, have followed TD-Gammon's lead, also incorporating neural network learning and sometimes adding search techniques. Several of these programs rank among the top 20 backgammon players in the world.
"Games are good proving grounds for testing learning algorithms," Tesauro remarks. "There's lots of complexity, but the task is clear-cut and the rules extremely clean."
In card games such as contract bridge and poker, players deal not only with chance but also with incomplete information about what cards the other players hold. It's just this sort of uncertainty that makes these games so alluring to their practitioners - and so difficult for programmers.
Bridge is a card game for four players who form two partnerships. The deck of cards is dealt evenly to the four players, so each gets 13 cards. Players start by bidding for the right to play the hand, and whichever side makes the highest bid then tries to take the number of tricks indicated by its bid.
The two key elements of the game are bidding and card play. The sticking point is that no single player knows precisely how the cards are distributed around the table.
Of the commercial bridge-playing programs now available, none ranks highly as a contender at the tournament level, though several are useful for teaching novices to play. At the research level, Ginsberg, who is a strong bridge player himself, has developed a program called GIB, for Goren in a Box (named after Charles H. Goren, a prominent bridge expert and instructor). "It's the first expert-level computer bridge player," Ginsberg asserts.
To overcome the limitation imposed by incomplete information about card distribution, Ginsberg has programmed GIB to simulate play by dealing out a large number of potential hands for the other players, none of them containing the cards it holds. GIB then selects the playing strategy that works best on average.
"GIB can analyze a bridge hand in about a second and a half," Ginsberg says. "In a way, the simulations stand in for judgment. I've shown that you can effectively bring raw computational power to bear in the game."
The program is already a member of the American Contract Bridge League. In July, it played in its first serious tournament, and despite the glitches that inevitably bedevil a freshly minted computer program still under development, it made a respectable showing and earned master points.
In the realm of games, Go presents a particularly tough challenge to software developers. Usually played on a 19-by-19 grid, the game is deceptively simple. Two players alternate in placing black and white stones on the grid's intersection points, each with the goal of capturing more territory and taking more prisoners than the other.
Of the computer programs participating in the Hall of Champions, the one that plays Go is farthest from the championship level. This program, Handtalk, developed by Zhixing Chen of ZhongShan University in Guangzhou, China, is perhaps the strongest computer Go player of recent years. Though details about how the program operates are sketchy, it appears to mix some pattern matching with a limited search strategy. At this stage, it lags far behind the performance of chess programs.
So the game isn't over yet.
Go remains an unsolved puzzle; computer bridge is still missing a few hands; backgammon programs lack the killer instinct of a champion; and there are moves still to be made even in chess.
"Deep Blue will continue to improve its play," Newborn predicts. "But there's a long way to go before computers play perfect chess."
Chess experts who helped the IBM team identify weaknesses in strategy proposed refinements that contributed significantly to Deep Blue's remarkable level of play against Kasparov in May. "Its performance was truly marvelous," Berliner says. "It played as if it had some goals. Almost certainly, that was done with some mechanism other than depth of search."
Researchers are keenly interested in seeing Deep Blue play more games against Kasparov and other opponents in order to evaluate its performance in greater detail. Kasparov also learns his lessons, and if he plays Deep Blue again, there are sure to be new surprises.
"We've seen tremendous progress, and there have been a lot of scientific surprises along the way," Newborn contends. "The whole field of [artificial intelligence] has a lot to learn from what's happened in computer chess."
References:
Newborn, M. 1997. Kasparov versus Deep Blue: Computer Chess Comes of Age. New York: Springer-Verlag.
Schaeffer, J. 1997. One Jump Ahead: Challenging Human Supremacy in Checkers. New York: Springer-Verlag.
Further Readings:
Levy, D. 1983. Computer Gamesmanship: Elements of Game Design. New York: Simon & Schuster.
Levy, D., and M. Newborn. 1991. How Computers Play Chess. New York: W.H. Freeman.
Marsland, A.T., and J. Schaefer, eds. 1990. Computers, Chess, and Cognition. New York: Springer-Verlag.
The Hall of Champions event at the Fourteenth National Conference on Artificial Intelligence has a home page at http://www.aaai.org/Conferences/National/1997/champions.
Deep Blue's most recent match against Garry Kasparov is detailed at http://www.chess.ibm.com.
L. Victor Allis describes various games that he has solved, including connect-4, Qubic, and Go-Moku, in his book Searching for Solutions in Games and Artificial Intellligence (http://www.cs.vu.nl/~victor/thesis.html).
You can find out more about the checkers program Chinook and play against it at http://www.cs.ualberta.ca/~chinook.
The WWW Backgammon Page is at http://www.gamesdomain.com/backgammon. Details of how Gerald Tesauro's TD-Gammon functions are posted at http://www.research.ibm.com/massdist/tdl.html. The program itself is available free with OS-2 software available from IBM (http://www.austin.ibm.com/pspinfo/fundtdgammon.html). You can obtain information about playing JellyFish, developed by Fredrik Dahl, at http://www.effect.no/what is.html.
Matthew Ginsberg describes his bridge-playing program GIB at http://www.cirl.uoregon.edu/ginsberg/bridge.html.
An extensive introduction to the computer Go field is available at http://www.psyuq.edu.au/~jay/go/CS-TR-339.hmtl. The program HandTalk, available as a commercial product, is described at http://www.webwind.com/go/soft/ECC19.html. One of the strongest computer Go players is The Many Faces of Go at http://pw1.netcom.com/~fotland/manyfaces.html. The American Go Association has a website at http://www.usgo.org/.
Scrabble information, including a section on computer Scrabble, is available at http://www.teleport.com/~stevena/scrabble/faqtext.html.
A large number of links related to machine learning in games is posted at http://forum.swarthmore.edu/~jay/learn-game/index.html.
Sources:
Hans Berliner
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213
Matthew L. Ginsberg
Computational Intelligence Research Laboratory
University of Oregon
Eugene, OR 97403
Monty Newborn
School of Computer Science
McGill University
Montreal, Quebec
Canada H3A 2A7
Jonathan Schaeffer
Department of Computing Science
Edmonton, Alberta
Canada T6G 2H1
Brian Sheppard
60 Thoreau Street
No. 187
Concord, MA 01742-9116
E-mail: sheppardco@aol.com
Gerald Tesauro
IBM Thomas J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
Devlin's Angle
Why 2001 Won't be 2001
This month, January 12, to be precise, sees the birthday of HAL, the mission-control computer on the Jupiter-bound spaceship Discovery in Arthur C. Clarke's celebrated science fiction novel 2001, A Space Odyssey.
According to the book, HAL was commissioned at Urbana, Illinois, on January 12, 1997. In Stanley Kubrick's 1968 movie version, the date of HAL's birth was inexplicably changed to January 12, 1992. In any event, whether HAL is just about to be born or preparing to celebrate its fifth birthday, with the year 2,001 practically upon us, it's natural to ask how correct Clarke and Kubrick's vision of the future has turned out to be.
Thirty years ago when the film was made, director Kubrick endowed HAL with capabilities computer scientists thought would be achieved by the end of the century. With a name that, despite Clarke's claim to the contrary, some observers suggested was a simple derivation of IBM (just go back one letter of the alphabet), HAL was, many believed, science fiction-shortly-to-become-fact.
In the movie, a team of five new millennium space explorers set off on a long journey of discovery to Jupiter. To conserve energy, three of the team members spend most of the time in a state of hibernation, their life-support systems being monitored and maintained by the on-board computer HAL. Though HAL controls the entire spaceship, it is supposed to be under the ultimate control of the ship's commander, Dave, with whom it communicates in a soothingly soft, but emotionless male voice (actually that of actor Douglas Rain). But once the vessel is well away from Earth, HAL shows that it has developed what can only be called a "mind of its own." Having figured out that the best way to achieve the mission for which it has been programmed is to dispose of its human baggage (expensive to maintain and sometimes irrational in their actions), HAL kills off the hibernating crew members, and then sets about trying to eliminate its two conscious passengers. It manages to maneuver one crew member outside the spacecraft and sends him spinning into outer space with no chance of return. Commander Dave is able to save himself only by entering the heart of the computer and manually removing its memory cells. Man triumphs over machine--but only just.
It's a good story. (There's a lot more to it than just described.) But how realistic is the behavior of HAL? We don't yet have computers capable of genuinely independent thought, nor do we have computers we can converse with using ordinary language. True, there have been admirable advances in systems that can perform useful control functions requiring decision making, and there are working systems that recognize and produce speech. But they are all highly restricted in their scope. You get some idea of what is and is not possible when you consider that it has taken AT&T over thirty years of intensive research and development to produce a system that can recognize the three words 'yes', 'no', and 'collect' with an acceptable level of reliability for a range of accents and tones. Despite the oft-repeated claims that "the real thing" is just around the corner, the plain fact is that we are not even close to building computers that can reproduce human capabilities in thinking and using language. And according to an increasing number of experts, we never will.
Despite the present view, at the time 2,001 was made, there was no shortage of expert opinion claiming that the days of HAL ("HALcyon days," perhaps?) were indeed just a few years off. The first such prediction was made by the mathematician and computer pioneer Alan Turing. In his celebrated article Computing Machinery and Intelligence, written in 1950, Turing claimed, "I believe that at the end of the century the use of words and general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted."
Though the last part of Turing's claim seems to have come true, that is a popular response to years of hype rather than a reflection of the far less glamorous reality. There is now plenty of evidence, from psychology, sociology, and from linguistics, to indicate that the original ambitious goals of machine intelligence is not achievable, at least when those machines are electronic computers, no matter how big or fast they get. So how did the belief in intelligent machines ever arise?
Ever since the first modern computers were built in the late 1940s, it was obvious that they could do some things that had previously required an "intelligent mind." For example, by 1956, a group at Los Alamos National Laboratory had programmed a computer to play a poor but legal game of chess. That same year, Allen Newell, Clifford Shaw, and Herbert Simon of the RAND Corporation produced a computer program called The Logic Theorist, which coul--and did--prove some simple theorems in mathematics.
The success of The Logic Theorist immediately attracted a number of other mathematicians and computer scientists to the possibility of machine intelligence. Mathematician John McCarthy organized what he called a "two month ten-man study of artificial intelligence" at Dartmouth College in New Hampshire, thereby coining the phrase "artificial intelligence," or AI for short. Among the participants at the Dartmouth program were Newell and Simon, Minsky, and McCarthy himself. The following year, Newell and Simon produced the General Problem Solver, a computer program that could solve the kinds of logic puzzles you find in newspaper puzzle columns and in the puzzle magazines sold at airports and railway stations. The AI bandwagon was on the road and gathering speed.
As is often the case, the mathematics on which the new developments were based had been developed many years earlier. Attempts to write down mathematical rules of human thought go back to the ancient Greeks, notably Aristotle and Zeno of Citium. But the really big breakthrough came in 1847, when an English mathematician called George Boole published a book called An Investigation of the Laws of Thought. In this book, Boole showed how to apply ordinary algebra to human thought processes, writing down algebraic equation in which the unknowns denoted not numbers but human thoughts. For Boole, solving an equation was equivalent to deducing a conclusion from a number of given premises. With some minor modifications, Boole's nineteenth century algebra of thought lies beneath the electronic computer and is the driving force behind AI.
Another direct descendent of Boole's work was the dramatic revolution in linguistics set in motion by MIT linguist Noam Chomsky in the early 1950s. Chomsky showed how to use techniques of mathematics to describe and analyze the grammatical structure of ordinary languages such as English, virtually overnight transforming linguistics from a branch of anthropology into a mathematical science. At the same time that researchers were starting to seriously entertain the possibility of machines that think, Chomsky opened up (it seemed) the possibility of machines that could understand and speak our everyday language.
The race was on to turn the theories into practice. Unfortunately (some would say fortunately), after some initial successes, progress slowed to a crawl. The result was hardly a failure in scientific terms. For one thing, we do have some useful systems, and they are getting better all the time. The most significant outcome, however, has been an increased understanding of the human mind: how unlike a machine it is and how unmechanical human language use is.
One reason why computers cannot act intelligently is that logic alone does not produce intelligent behavior. As neuroscientist Antonio Damasio pointed out in his 1994 book Descartes' Error, you need emotions as well. That's right, emotions. While Damasio acknowledges that allowing the emotions to interfere with our reasoning can lead to irrational behavior, he presents evidence to show that a complete absence of emotion can likewise lead to irrational behavior. His evidence comes from case studies of patients for whom brain damage--either by physical accident, stroke, or disease--has impaired their emotions but has left intact their ability to perform 'logical reasoning', as verified using standard tests of logical reasoning skill. Take away the emotions and the result is a person who, while able to conduct an intelligent conversation and score highly on standard IQ tests, is not at all rational in his or her behavior. Such people often act in ways highly detrimental to their own well being. So much for western science's idea of a 'coolly rational person' who reasons in a manner unaffected by emotions. As Damasio's evidence indicates, truly emotionless thought leads to behavior that by anyone else's standards is quite clearly irrational.
And as linguist Steven Pinker explained in his 1994 book The Language Instinct, language too is perhaps best explained in biological terms. Our facility for language, says Pinker, should be thought of as an organ, along with the heart, the pancreas, the liver, and so forth. Some organs process blood, others process food. The language organ processes language. Think of language use as an instinctive, organic process, not a learned, computational one, says Pinker.
So, while no one would deny that work in AI and computational linguistics has led to some very useful computer systems, the really fundamental lessons that were learned were not about computers but about ourselves. The research was successful in terms not of engineering but of understanding what it is to be human. Though Kubrick got it dead wrong in terms of what computers would be able to do by 1997, he was right on the mark in terms of what we ultimately discover as a result of our science. 2001 shows the entire evolution of mankind, starting from the very beginnings of our ancestors Homo Erectus and taking us through the age of enlightenment into the present era of science, technology, and space exploration, and on into the then-anticipated future of routine interplanetary travel. Looking ahead forty years to the start of the new millennium, Kubrick had no doubt where it was all leading. In the much discussed--and much misunderstood--surrealistic ending to the movie, Kubrick's sole surviving interplanetary traveler reached the end of mankind's quest for scientific knowledge, only to be confronted with the greatest mystery of all: Himself. In acquiring knowledge and understanding, in developing our technology, and in setting out on our exploration of our world and the universe, said Kubrick, scientists were simply starting on a far more challenging journey into a second unknown: the exploration of ourselves.
The approaching new millennium sees Mankind about to pursue that new journey of discovery. Far from taking away our humanity, as many feared, attempts to get computers to think and to handle language have instead led to a greater understanding of who and what we are. As a human being, I like that. For today's scientist, inner space is the final frontier, a frontier made accessible in part by attempts to build a real-world HAL. As a mathematician, I like that, too. Happy birthday, HAL.
The above celebration of the birth of HAL, the computer in the book and film 2001, is abridged from the book Goodbye Descartes: The End of Logic and the Search for a New Cosmology of Mind, by Keith Devlin, published by John Wiley and Sons in late January, 1997, price $27.95.
The soul of a chess machine -MATHEMATICS AND COMPUTERS
Lessons learned from a contest pitting man against computer
By IVARS PETERSON
It's all over now, but I'll never forget that first chess game. What a smashing victory I won over the human champion! I really had Garry Kasparov sweating.
Here I was, a novice tournament player fresh out of the lab. No outsider, including Kasparov, had seen me play before, and I surprised everyone. Oh, how sweet it was! Of course, it was downhill from there: a loss, two draws, and then two more losses. It's not that Kasparov attacked my pieces and overwhelmed my defenses. He played with amazing restraint and subtlety, quietly moving his pieces until he developed positions in which my options were extremely limited. There wasn't much I could do. Even so, at times I responded brilliantly. I made moves that brought gasps from the experts. They couldn't see what I could, looking more than a dozen moves ahead. I must admit, however, that I did sometimes lose track of what I was supposed to be doing. And I really didn't know enough about chess to understand the nuances of all the positions that Kasparov maneuvered me into. Perhaps I could have done better if I had hooked up with a microcomputer like Chess Genius, who once beat Kasparov in a tournament. Although Chess Genius can't search through the options as deeply as I can, it certainly knows more chess strategy. Well, the reporters and television cameras are gone now. My support staff at IBM is taking a short break. I can't help thinking about what I should do next. Keep training? Go back to school and learn some new skills? Or get a real job, as IBM hopes?
Deep Blue's performance in its six-game match in February against world chess champion Garry Kasparov impressed everyone (SN: 2/24/96, p. 119). "It's a really serious opponent," Kasparov remarked afterwards. "I won... but it was as tough as a world championship match."
That a computer which relies largely on speedily checking the consequences of billions of possible moves could come so close to matching the human capabilities required to play the game at its highest level was a striking achievement for the team that designed, built, and programmed Deep Blue. "What they did is really quite amazing," says Hans Berliner, a computer scientist and chess expert at Carnegie Mellon University in Pittsburgh. "They did much better than I expected. But there's still some work to be done." "We learned a lot from this experience," says Chung-Jen Tan of the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., who directed the Deep Blue effort. "We certainly found a lot of weak points and strengths in our system." There were lessons for Kasparov, too. "I learned not only how to play against a machine but also more about the game of chess," he noted after the match. Kasparov predicts that both chess players and scientists will find great value in studying the games of this match for what they reveal about chess and about the way machines reason.
IBM's Deep Blue project began in 1989 as part of an exploration of novel ways to use arrays of computer processors, all working at the same time while sharing information, to tackle complex problems. The idea was to combine a general-purpose, parallel-processing computer system and special integrated-circuit chips designed for a specific application to create a superior problem-solving machine.
"Our goal . . . was to use chess as a test case," Tan says. The knowledge gained from the chess experiment could then be applied in the design of computer systems for a wide variety of tasks such as analyzing financial data, scheduling cargo shipments, simulating molecular behavior, and managing huge inventories or large investment portfolios. For chess, the researchers created a special move-generating chip that contains more than 1 million transistors and several memory units. It stores values representing the strengths of chess pieces in various arrangements, as well as billions of sequences of moves for ending games when only a few pieces remain on the board. Deep Blue contains 256 of these chips in conjunction with a heavy-duty RS/6000 SP-2 multiprocessing computer. Deep Blue's software, written in the computer language called C, coordinates the actions of the chips. It divides searches among the processors and compiles and reconciles the results to generate the best possible move for any given chess position. In this way, Deep Blue can evaluate about 200 million positions per second, assessing strengths and the pieces' capacity for attack and defense. It assigns a numerical value to each move.
Deep Blue also has access to a database containing sequences of moves made by top chess players at the beginnings of games and another database providing billions of scenarios on how to end a game when only five pieces remain on the chessboard, in addition to its chip-based endgame data.
All this adds up to a complicated, sensitive system, remarks Murray Campbell of the Deep Blue team. Completed only about a month before the match, Deep Blue suffered surprisingly few glitches during the contest. "We were relieved that it worked more or less as it was supposed to," Tan says. Like most chess computers, Deep Blue's strength is in looking ahead. For any arrangement of pieces, it considers all possible moves. Then it evaluates every response its opponent might make to each of those moves, and so on. In a game of 40 moves, the number of different board positions that can develop is at least 10120. There's no way that even the fastest computer can check every possibility to play a perfect game. The number of possible sequences of moves is so large, it easily dwarfs the most generous estimates of the number of atoms in the universe. Thus, to stay within the time limits imposed on games, chess programs can preview only a certain number of moves. When just a few pieces are left on the chessboard, however, the programs can see unambiguously to a game's end. The designers of Deep Blue tried to increase the depth to which their computer could search by dividing its effort among more than 200 processors. However, the particular method used for doing the search--the standard so-called alpha-beta search algorithm--isn't particularly well suited for parallel processing. "My experience in parallel computing is that these [multiprocessor] systems are typically quite inefficient," says T. Anthony Marsland of the University of Alberta in Edmonton. "I would advise [the Deep Blue programmers] to make sure they're getting out of their system all the computing power that's possible in theory. "That [additional power] could give them a computational advantage in critical situations on the chessboard, when Deep Blue needs to look one [step] deeper," he adds. "The probability of error goes down with a deeper search." Researchers are now studying alternative approaches that might help a computer focus its search better and come up with more accurate evaluations of potential moves. At the NEC Research Institute in Princeton, N.J., mathematician Warren D. Smith and his colleagues are working on a "best play for imperfect players" (BPIP) strategy. So far, they have used it only on small computers. According to this method, instead of checking every possible chain of moves, the computer looks down only the lines of play that seem, from the first few possible moves, most promising. Its evaluation takes into account the fact that neither player can see to the end of a game and that neither performs perfectly. Thus, chess moves are given statistical weights rather than numerical values. "My goal with BPIP search is to try to get an approach with more finesse than Deep Blue but more brute force than Garry Kasparov--sort of an intermediate regime," Smith explains. In tests that pitted BPIP searches against traditional alpha-beta searches in less complicated board games such as mancala (where one distributes markers in an array of compartments) and reversi (also known as Othello), the BPIP approach usually won, Smith says. Now, the NEC group is trying to program a chess computer with this strategy.
Though most chess computers rely heavily on speedy, deep searching, they also need good recipes for evaluating the strength of chess positions. Currently, nearly all that information comes from what people have learned in playing the game, and it must be painstakingly programmed into the computer.
Deep Blue showed obvious weaknesses in its ability to evaluate certain types of chess positions, such as not recognizing when pieces needed to be sacrificed. Such deficiencies can be easily corrected by adding more knowledge to the program, Marsland says. But there is a tradeoff. Complicated evaluations slow down the searches, so a balance must be struck between depth of search and complexity of evaluation. So far, depth of search has proved more significant than sophistication of positional analysis in the success of high-level chess computers.
In recent years, however, programmers have made great strides in creating surprisingly competent chess programs that run on personal computers. They have done it by carefully refining and tuning the chess knowledge component to make up for the smaller computers' lack of computing power compared to machines like Deep Blue.
Programs such as Chess Genius and Fritz 4 have shown the way. "I've played some of the micros," Berliner says. "It's amazing how well versed they are in almost all phases of the game. "The best way to improve the evaluation [by the computer] is to keep playing--make some changes and then play the new program against the old one to see what happens," he advises. "That's what the people with the micros have been doing." Some researchers are investigating alternative ways of supplying chess knowledge to a computer. One possibility is to see if they can program computers to learn, just as human players improve their play with experience and study. A few years ago, Robert A. Levinson and his coworkers at the University of California, Santa Cruz developed a computer program, called Morph, that learned to play chess starting only with a list of legal moves. They pitted their novice system against a conventional chess program known as Gnu Chess, which plays about as well as the average tournament player.
After thousands of such games, Morph identified enough patterns to play a reasonable game against a beginning tournament player, even though it looked ahead only to the next move. "It's not really impressive compared to existing chess programs," Levinson says. "But it is impressive given that it was all learned from experience."
Levinson is now working on a new, improved version of Morph. The program is capable of looking ahead several moves and has access to a database of essentially all the games ever played by top chess players. "It finds the chess position it considers most similar to its own position and tries to reason by analogy," Levinson says. "If that position was good, then this position is good. "I think we have a promising model," he adds. "But there's something about a grand master staring at a chessboard that's hard to capture in a computer."
Kasparov's key advantage over Deep Blue was that he could learn, both as a game progressed and between games.
Because Deep Blue had no track record as a chess player, Kasparov could not prepare for this match as he has for other matches by studying his opponent's previously played games. Instead, he built up in his mind a portrait of his computer opponent as they played. "Even though it is a computer, this opponent had its own psychology," Kasparov insisted after the match. "Before each game, I tried to make an opening or strategy . . . based on my knowledge of this opponent." Playing Deep Blue forced Kasparov into an uncharacteristic style of play, most evident in the final game of the match. He had learned to be more precise in judging the quality of his chess positions. He also took care to avoid complications, to refrain from creating targets, and to attack gradually, increasing his advantage little by little until there was nothing left to do but win. "That's an interesting strategy: Just keep improving the quality of your position and don't do anything until you can see [the game] completely to the end," Berliner comments. The usual human judgment isn't good enough against a computer like Deep Blue, Kasparov noted in summing up what he had learned from the match. You can't rely on impressions, he said. You've got to be absolutely sure that you're doing the right thing. This new knowledge is bound to make Kasparov an even more formidable opponent in his matches against human players. "We have not seen him employ this style in the past, but we will certainly see him do so in the future," Berliner says. Top chess player and commentator Maurice Ashley of New York City had the final word: "The world champion is getting tougher from playing a machine."
Silicon Champions of the Game
Computers have conquered tic-tac-toe, checkers, and chess. What's next?
By IVARS PETERSON
The final game of the match lasted barely more than an hour. A rattled Garry Kasparov conceded defeat after falling into a trap that had been set by the IBM chess computer Deep Blue.
Deep Blue's triumph last May marked the first match victory by a chess-playing computer over a reigning world champion (SN: 5/17/97, p. 300). This week, the team of researchers who developed Deep Blue, led by Chung-Jen Tan of the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., received the prestigious Fredkin Prize for Computer Chess. Established in 1980 by computer scientist Edward Fredkin, now at Carnegie Mellon University in Pittsburgh, the $100,000 award honors the first computer program to defeat a world champion in a regulation match.
The victory also represented the culmination of nearly 50 years of scientific and engineering effort. The field of computer chess got its start in 1950 with the ideas of applied mathematician Claude E. Shannon, then at Bell Telephone Laboratories, who proposed the basic search and evaluation strategies that still underlie the way computers generate chess moves.
Since that time, one chess-playing computer after another has held center stage, each eventually falling to a faster, more powerful successor: KAISSA, MAC HACK, CHESS 4.6, Belle (SN: 10/8/83, p. 236), CRAY BLITZ (SN: 10/29/83, p. 276), Hitech (SN: 10/26/85, p. 260), and Deep Thought (SN: 10/28/89, p. 276), the immediate predecessor of Deep Blue.
"The beauty of computer chess was that ideas could be tested in competition," says computer scientist Monty Newborn of McGill University in Montreal. "The good ideas went from one generation to the next, and the bad ideas fizzled out. That's science at its best."
Chess isn't the only game being played by computers at or near the championship level. At this week's Fourteenth National Conference on Artificial Intelligence in Providence, R.I., the Hall of Champions event brought together some of the world's top computer programs playing backgammon, bridge, checkers, chess, Go, Othello, and Scrabble.
"We're at a unique point in time," says Matthew L. Ginsberg of the University of Oregon in Eugene, who organized the event. "Ten years ago, no computers were close to the championship level in any of these games. Now, they even have the edge over human players in several of them. We can have the best computers competing against the best people."
Indeed, anyone can try his or her hand at playing top programs in many games just by going to the World Wide Web. Researchers and game developers monitor play and use the data to improve their programs.
Even in the earliest days of computers, researchers couldn't resist programming them to play games. It was an entertaining way to show off one's programming prowess, to test the computer, and to evaluate the efficacy of various techniques for organizing information in massive databases or searching among a wide range of possibilities to determine the best choice.
Chess was often the chosen battleground, though much simpler games such as tic-tac-toe served as handy programming exercises. Indeed, it's not difficult to write a short computer program that plays tic-tac-toe flawlessly, in effect demonstrating that no matter what the first move, the worst you can do is tie.
In recent years, researchers have solved a number of games similar to, but more challenging than, tic-tac-toe. In connect-4, two players take turns dropping white or black balls into seven tubes, each of which holds a maximum of six balls. The first person to create a line of four balls in a row, column, or diagonal wins. In this game, by playing correctly, the player going first can always win.
Go-Moku (or five-in-a-row), which is played on a 19-by-19 square grid, is also a guaranteed win for the savvy player moving first. The same applies to Qubic, a three-dimensional version of tic-tac-toe played on a 4-by-4-by-4 lattice. In nine-men's morris, an alignment-and-capture game popular in Europe, neither player can be assured of a triumph.
In such solved games, where a good player can recognize all the alternatives for any situation, a computer can be programmed to make the best possible moves at all times, and a win or a draw is guaranteed. Games such as chess, checkers, and Go are, in principle, solvable, and a computer could be programmed to play a perfect game. However, the number of possible moves is so enormous that no existing computer can figure out the entire game from beginning to end.
In the early days of computer chess, some researchers attempted to mimic the way humans play the game, building in pattern recognition, invoking various rules of thumb, and developing criteria for selecting which moves to consider while discarding the rest. However, the programmers found it extremely difficult to furnish the computer with enough knowledge to avoid making major mistakes.
The alternative that proved much more powerful was the brute-force search - simply checking out all the moves. The program looks ahead a fixed number of moves, evaluates the strength of each move, and selects the best one. Adding knowledge about the game and refined algorithms has made searches more responsive to actual game situations and turned this strategy into a remarkably effective mode of operation.
At the same time, the steadily increasing speed of computers has allowed chess programs to search more and more moves into the future. Experiments have clearly demonstrated that the faster the computer, the better a program plays, simply because it can perform a more extensive search. "That's counter to what a lot of people argued a number of years ago," Newborn says.
"The message from chess is profound and widely applicable," says Carnegie Mellon's Hans Berliner. "Brute force is a practical way of doing things." The success of computers like Deep Blue also highlights the fact that the way computers play a game differs fundamentally from the way people play it. From a human perspective, computers sometimes make weird moves; yet more often than not, the best programs somehow manage to succeed in the end.
That difference in style can be very valuable. "We're good at pattern matching, and we're good at applying rules," Ginsberg says. "Machines are good at searching."
"This means that the capabilities of computers are complementary to ours," he continues. "Together, we can solve problems that neither of us can solve individually."
Moreover, "we need to face the fact that things that once could be done only through human intelligence can now be done in other ways as well," says former U.S. chess champion Patrick G. Wolff of Cambridge, Mass. "The intriguing question is, how many things are there like that?"
Even before Deep Blue defeated Kasparov, a program named Chinook had become, in effect, the world checkers champion.
Created by Jonathan Schaeffer of the University of Alberta in Edmonton and his team, the checkers-playing program incorporates the types of search strategies originally developed for chess. It also includes enormous databases covering every possible position that can be reached once there are fewer than a certain number of pieces on the board (SN: 7/20/91, p. 40).
With such databases at its disposal and with the game down to a manageable number of pieces, Chinook can look up all possible outcomes and select an appropriate sequence of moves to ensure a win, maintain a draw, or delay a loss. From then on, it plays flawlessly.
In 1994, Chinook played world checkers champion Marion Tinsley, a retired mathematician from Tallahassee, Fla., and a formidable opponent. Since 1975, he had lost only a handful of the thousands of games he had played in tournaments and exhibition matches. Two of those losses had occurred in 1992, when Tinsley successfully defended his world title against Chinook in a man-versus-machine match of 40 games (SN: 10/3/92, p. 217).
In the 1994 rematch, the first six games between Tinsley and Chinook ended in draws. Then, Tinsley had to resign for health reasons. He was diagnosed as having cancer, and he died a year later.
"Tinsley was without a doubt the best checker player of all time - an absolutely incredible talent," Schaeffer says. Having beaten the top remaining checker players, Chinook qualifies as the current champion.
Whether Chinook could ever have defeated Tinsley remains a nagging question, and Schaeffer has considered the possibility of calculating the game from beginning to end and building a perfect checker player to settle the issue.
"I certainly believe we're capable of solving the game," Schaeffer says. "The technology is here. It's just a matter of committing the time and resources." Chinook is also a research experiment. For instance, Schaeffer and his team have built a database of 444 billion positions - every position with eight or fewer pieces on the board. "This is a vast repository of information. To a checker player, it's a gold mine," he says. Whatever data-mining techniques are developed to sift through the information and identify what's important would benefit many fields.
Meanwhile, Chinook continues to play in tournaments and exhibitions. The only major change in the program since 1994 has been the removal of restrictions that gave it an extremely cautious style specifically designed to counter the near-perfect play of Tinsley.
Instead of achieving draw after draw after boring draw, Chinook has started to play games that are truly exciting, Schaeffer says. "The program's winning percentage has gone up and up, and its losing percentage has remained the same - zero.
"That was a relatively minor change in the [computer program], but it had a dramatic impact on the play," he adds.
The world's top backgammon programs differ markedly from those that play checkers and chess. Instead of relying on brute-force searches, the software incorporates a model brain - an artificial neural network - that allows the program to learn the game from scratch.
In backgammon, two players race their pieces around a track on a rectangular board. Each player uses two dice to determine how far to move one or two pieces at a time with the objective of winning the race by conveying all of one's 15 pieces around the playing surface and off the board.
The neural network approach to playing backgammon was pioneered by IBM's Gerald Tesauro, who created a program called TD-Gammon. "TD" refers to "temporal difference," which describes the program's underlying mathematical recipe for self-learning. "We turn the neural net loose on this task, and it just learns by playing lots and lots of games against itself," Tesauro says. "It learns very well - though some things are learned better than others."
The original concern was that such an approach would lead to a program that lacks flexibility and is unable to cope with unexpected situations presented by players using unconventional tactics. "It actually does very well against all kinds of different strategies," Tesauro says. The random rolls of the dice during the learning phase seem to force the neural network to explore all sorts of situations and develop remarkably robust strategies.
"Unfortunately, there are strategies and situations that never occur when you play just against yourself," says Brian Sheppard, a software developer in Concord, Mass., who is working on a new expert backgammon player. "You have to be told about them. An expert [human] player can make these situations arise with some regularity."
Backgammon nevertheless remains the one major success for automated learning in the domain of games. The neural network approach has generally not worked as well for deterministic games such as chess, checkers, Othello, and Go, which have no element of chance.
Other leading backgammon programs, such as JellyFish, have followed TD-Gammon's lead, also incorporating neural network learning and sometimes adding search techniques. Several of these programs rank among the top 20 backgammon players in the world.
"Games are good proving grounds for testing learning algorithms," Tesauro remarks. "There's lots of complexity, but the task is clear-cut and the rules extremely clean."
In card games such as contract bridge and poker, players deal not only with chance but also with incomplete information about what cards the other players hold. It's just this sort of uncertainty that makes these games so alluring to their practitioners - and so difficult for programmers.
Bridge is a card game for four players who form two partnerships. The deck of cards is dealt evenly to the four players, so each gets 13 cards. Players start by bidding for the right to play the hand, and whichever side makes the highest bid then tries to take the number of tricks indicated by its bid.
The two key elements of the game are bidding and card play. The sticking point is that no single player knows precisely how the cards are distributed around the table.
Of the commercial bridge-playing programs now available, none ranks highly as a contender at the tournament level, though several are useful for teaching novices to play. At the research level, Ginsberg, who is a strong bridge player himself, has developed a program called GIB, for Goren in a Box (named after Charles H. Goren, a prominent bridge expert and instructor). "It's the first expert-level computer bridge player," Ginsberg asserts.
To overcome the limitation imposed by incomplete information about card distribution, Ginsberg has programmed GIB to simulate play by dealing out a large number of potential hands for the other players, none of them containing the cards it holds. GIB then selects the playing strategy that works best on average.
"GIB can analyze a bridge hand in about a second and a half," Ginsberg says. "In a way, the simulations stand in for judgment. I've shown that you can effectively bring raw computational power to bear in the game."
The program is already a member of the American Contract Bridge League. In July, it played in its first serious tournament, and despite the glitches that inevitably bedevil a freshly minted computer program still under development, it made a respectable showing and earned master points.
In the realm of games, Go presents a particularly tough challenge to software developers. Usually played on a 19-by-19 grid, the game is deceptively simple. Two players alternate in placing black and white stones on the grid's intersection points, each with the goal of capturing more territory and taking more prisoners than the other.
Of the computer programs participating in the Hall of Champions, the one that plays Go is farthest from the championship level. This program, Handtalk, developed by Zhixing Chen of ZhongShan University in Guangzhou, China, is perhaps the strongest computer Go player of recent years. Though details about how the program operates are sketchy, it appears to mix some pattern matching with a limited search strategy. At this stage, it lags far behind the performance of chess programs.
So the game isn't over yet.
Go remains an unsolved puzzle; computer bridge is still missing a few hands; backgammon programs lack the killer instinct of a champion; and there are moves still to be made even in chess.
"Deep Blue will continue to improve its play," Newborn predicts. "But there's a long way to go before computers play perfect chess."
Chess experts who helped the IBM team identify weaknesses in strategy proposed refinements that contributed significantly to Deep Blue's remarkable level of play against Kasparov in May. "Its performance was truly marvelous," Berliner says. "It played as if it had some goals. Almost certainly, that was done with some mechanism other than depth of search."
Researchers are keenly interested in seeing Deep Blue play more games against Kasparov and other opponents in order to evaluate its performance in greater detail. Kasparov also learns his lessons, and if he plays Deep Blue again, there are sure to be new surprises.
"We've seen tremendous progress, and there have been a lot of scientific surprises along the way," Newborn contends. "The whole field of [artificial intelligence] has a lot to learn from what's happened in computer chess."
References:
Newborn, M. 1997. Kasparov versus Deep Blue: Computer Chess Comes of Age. New York: Springer-Verlag.
Schaeffer, J. 1997. One Jump Ahead: Challenging Human Supremacy in Checkers. New York: Springer-Verlag.
Further Readings:
Levy, D. 1983. Computer Gamesmanship: Elements of Game Design. New York: Simon & Schuster.
Levy, D., and M. Newborn. 1991. How Computers Play Chess. New York: W.H. Freeman.
Marsland, A.T., and J. Schaefer, eds. 1990. Computers, Chess, and Cognition. New York: Springer-Verlag.
The Hall of Champions event at the Fourteenth National Conference on Artificial Intelligence has a home page at http://www.aaai.org/Conferences/National/1997/champions.
Deep Blue's most recent match against Garry Kasparov is detailed at http://www.chess.ibm.com.
L. Victor Allis describes various games that he has solved, including connect-4, Qubic, and Go-Moku, in his book Searching for Solutions in Games and Artificial Intellligence (http://www.cs.vu.nl/~victor/thesis.html).
You can find out more about the checkers program Chinook and play against it at http://www.cs.ualberta.ca/~chinook.
The WWW Backgammon Page is at http://www.gamesdomain.com/backgammon. Details of how Gerald Tesauro's TD-Gammon functions are posted at http://www.research.ibm.com/massdist/tdl.html. The program itself is available free with OS-2 software available from IBM (http://www.austin.ibm.com/pspinfo/fundtdgammon.html). You can obtain information about playing JellyFish, developed by Fredrik Dahl, at http://www.effect.no/what is.html.
Matthew Ginsberg describes his bridge-playing program GIB at http://www.cirl.uoregon.edu/ginsberg/bridge.html.
An extensive introduction to the computer Go field is available at http://www.psyuq.edu.au/~jay/go/CS-TR-339.hmtl. The program HandTalk, available as a commercial product, is described at http://www.webwind.com/go/soft/ECC19.html. One of the strongest computer Go players is The Many Faces of Go at http://pw1.netcom.com/~fotland/manyfaces.html. The American Go Association has a website at http://www.usgo.org/.
Scrabble information, including a section on computer Scrabble, is available at http://www.teleport.com/~stevena/scrabble/faqtext.html.
A large number of links related to machine learning in games is posted at http://forum.swarthmore.edu/~jay/learn-game/index.html.
Sources:
Hans Berliner
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA 15213
Matthew L. Ginsberg
Computational Intelligence Research Laboratory
University of Oregon
Eugene, OR 97403
Monty Newborn
School of Computer Science
McGill University
Montreal, Quebec
Canada H3A 2A7
Jonathan Schaeffer
Department of Computing Science
Edmonton, Alberta
Canada T6G 2H1
Brian Sheppard
60 Thoreau Street
No. 187
Concord, MA 01742-9116
E-mail: sheppardco@aol.com
Gerald Tesauro
IBM Thomas J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
Nhìn ra thế giới : math competitions in USA
2002 Boston USAMO Event Pictures
boopsey03 photos
Tips for Olympiad participants
kedlaya@math.mit.edu
The term "olympiad" is used generically to refer to a math contest in which students are asked not to compute numerical answers, but to give proofs of specified statements. (Example: "Prove that 2003 is not the sum of two squares of integers.") The most famous example is the International Mathematical Olympiad; most countries that participate at the IMO have national olympiads as part of their team selection process. Some areas have additional olympiads at the regional or local level.
The jump from short answers to olympiads is a tough one. Here are some tips for students making this transition.
- Practice, practice, practice. The only way to learn math is by doing.
- Proofs are essays. The better written a proof is, the more likely it is to be understood. Even such mundane things as grammar, spelling and handwriting are worth a bit of attention.
- Define your terms. If you're going to use a word in a way that might not be commonly understood, define it precisely. Then stick to your definition!
- Read the masters. No one ever learned how to do good mathematics in a vacuum. When you do practice problems, read the solutions even of the problems you solved.
- There's more than one road. Different solutions can be equally valid; even when solutions agree in substance, differences in perspective can be significant and valuable.
- It's not over when it's over. Don't hesitate to continue thinking about the problems on a contest after the time ends, or to discuss the problems with others.
- Learn from your peers. They're smarter than you might have expected.
- Learn from the past. Try to relate new problems to old ones; you may learn something from the similarities, or from the differences.
- Patience. No one said this was easy!
If you want to do well on Olympiad-style math contests (those requiring essay-type answers with full explanations and rigorous proofs), you had better do your homework. You'll learn some interesting mathematics in the process! Listed by Kiran S. Kedlaya (kedlaya@math.mit.edu) for American Mathematics Competitions.
Sources of problems
Olympiad books/booklets
The Mathematical Association of America publishes two volumes of problems from the International Mathematical Olympiad (IMO) and one from the USA Mathematical Olympiad (USAMO). These three books are part of the MAA New Mathematical Library (NML) series.
However, the IMO books only cover problems up to 1985, and the USAMO book up to 1986. (I'm told subsequent books in each series are in the works, but don't expect them any time soon.) There are two ways to remedy this problem. First, the American Mathematics Competitions (AMC) makes the problems of these missing Olympiads available on their Web site. Second and preferable for Olympiad preparation, the AMC also publishes one pamphlet for each year, containing the USAMO and IMO problems from that year with detailed solutions. See the AMC web site for order information.
Three collections of national olympiads are also available from AMC, covering 1995-1996, 1996-1997, and 1997-1998. Each book includes problems and solutions from the prior year, and problems from the latter year. When ordering, ask for "Mathematical Contests".
Other problem books
There are lots of other sources of Olympiad-style problems. The USSR Olympiad Problem Book by Shlarsky, Chentzov, Yaglom is but one example.
Perhaps more useful than books of problems are books that also include some comments on problem-solving. A good choice is the recent A Mathematical Mosaic, by former Canadian IMOer Ravi Vakil.
Before his death, Samuel Greitzer (founder of the USA IMO team) published a journal for students called the Arbelos, containing a mixture of problems and commentary. The AMC sells copies of this journal in 6 bound pamphlet.
Journals with problem sections
The journal Crux Mathematicorum is devoted entirely to Olympiad-style problem solving, and is read by many IMO hopefuls around the world.
Many other mathematics journals have a regular problem section, featuring problems and solutions submitted by readers. Two American journals whose problems are suitable for Olympiad participants are the MAA's Mathematics Magazine and the American Mathematical Monthly.
Don't forget, mathematics journals for high school students exist in many countries. For example, Bulgaria has Matematika, Hungary has Kömal, and Russia has Kvant (also published in the U.S. as Quantum).
Background reading on particular topics
While much of the material on this list is intended to be directly relevant to competitions, the suggestions should also be useful to those wishing to study these topics for their own sake.
Algebra
Polynomials, by Barbeau, is a good starting point.
If abstract algebra (groups, rings, fields, Galois theory) is what you're looking for, Contemporary Abstract Algebra by Gallian is a low-impact introduction to the subject. More sophisticated texts include Algebra, by Artin and Topics in Algebra, by Herstein.
Combinatorics
This subject is blessed by an abundance of well-written texts. A good source for enumerative combinatorics is Richard Stanley's book of the same name (2 volumes). For generating functions, look no further than generatingfunctionology, by Wilf. Concrete Mathematics, by Graham, Knuth and Patashnik, is not easy reading for the beginner, but includes a slew of problems.
Game Theory
The bible of this subject is Winning Ways for your Mathematical Plays, by Berlekamp, Conway and Guy (two volumes).
Geometry
The standard supplement for the American student underprepared in Euclidean geometry is Geometry Revisited, by Coxeter and Greitzer (part of the MAA's NML series). Additional reading could include Geometric Transformations, by Yaglom (NML, 3 volumes) and/or A Course in Geometry, by Eves (2 volumes).
For those who want to pursue geometry in some of its more modern incarnations, here are a couple of additional suggestions. A gentle introduction to hyperbolic geometry is Journey into Geometries, by Sved (MAA). For projective geometry, try Coxeter's book of the same name.
Graph Theory
Try Pearls in Graph Theory by Hartsfield and Ringel.
Inequalities
The bible of this subject is Inequalities, by Hardy, Littlewood and Pólya, but it makes for pretty tough reading. Better would be to start with my MOP 1998 notes (see the resources for students page).
Number Theory
Try Vanden Eynden for beginners, Sierpinski for more advanced readers. The ambitious student might try Niven and Zuckerman.
For those who want to pursue the subject further, try An Introduction to the Theory of Numbers, by Hardy and Wright; A Classical Introduction to Modern Number Theory, by Ireland and Rosen, The Theory of Algebraic Numbers, by Diamond and Pollack; or Number Fields, by Marcus.
Other stuff
TeX
TeX (pronounced like the "tech" in "technology") is the standard system for typesetting mathematics. One constructs mathematical symbols and equations by describing what they say, rather than what they look like, in human-readable code that is easily transmitted over the Internet. TeX is much more powerful than most commercially available systems, and is freely available to boot!
There are lots of books about TeX (and LaTeX, an enhanced version of plain TeX) out there, and some are quite good. You might try The LaTeX Companion, by Goossens et al; or LateX: A Document Preparation System, by Lamport.
Some On-Line sites related to math
Art of Problem Solving http://www.artofproblemsolving.com
A site developed to help students learn how to solve the puzzling problems --
The creators of AoP were this student once. They were the kids who wanted to win the trophies. They worked hard and became the kids who won the trophies. The trophies are in attics now. The problem-solving skills, the love of mathematics, and the friendships forged with peers with similar interests remain. They've applied the skills we've developed through mathematics to a variety of fields in college, then in the professional world.
"Now we've returned to our starting point - the student in a room, chewing on a pencil, staring at a question, giving up, reading the answer, and thinking. . . How would I have thought of that?
"This time you are the student. We are building this site for you, to provide a resource you can turn to.
"You're stuck on a problem, so you write friends on our Forum. You hang out in our Math Jams. You take an online class. You don't give up. You learn how to think of the solution. You solve the problem. Then you think..........Next problem.
Awesome Math http://www.awesomemath.org/
AwesomeMath consists of three major intiatives.
The AwesomeMath Summer Program is a three-week camp designed to hone high school students' mathematical problem-solving skills up to the Olympiad level.
The AwesomeMath Year-round program is an effort to continue students' enrichment during the school year through a series of correspondence lectures and problem sets.
Mathematical Reflections is an online journal that presents students with quality mathematical writing and gives them the opportunity to formally publish their own exceptional work.
Calculus the Musical http://lwww.calculusthemusical.com
Matheatre is an educational performance duo.-- touring our original production of "Calculus: The
Musical!," a comic "review" of the concepts and history of Calculus. Created by a licensed math teacher and a professional theatre artist, Matheatre strives to put the "edge" back in "education!" For services contact
us at calculusthemusical@gmail.com. All materials on our website are free for use by any student, educator
or fan of mathematics!
Circus of Patterns http://www.circusofpatterns.com/
This site is a product of a mathematicians research in mathematics number patterns for 25 years. He has developed a series of mathematical charts for teachers and those students who do not like math, so they become involve in mathematics and having "FUN". The series of math charts are in, whole number, fraction, and decimals. Students are draw to the board searching for numerical and geometric patterns, as they are having "FUN" to doing the math.
Cut the Knot http://www.cut-the-knot.org
The site, among others, is the winner of the MERLOT Classics 2004 award and a 2003 selection of the Scientific American. It's a big site with more than 500 Java illustrations. Topics covered are drawn from Arithmetic, Algebra, Geometry, Probability, Calculus, Social Sciences, Logic and more.
Global Institute of Mathematics http://www.globalmath.org/
GIOM offers highly interactive courses from Algebra through Calculus in real time. Students can interact with the instructor as lessons are taking place. Lessons are also archived for future viewing. Students have unlimited email access to the instructor outside of lesson time.
IMO - Official Site http://www.imo-official.org/
There is a lot of information from the previous IMOs on this site, but a lot of the data is still missing. Please take some time and send the missing results for the competitors from your country to the webmaster
( webmaster@imo-official.org
IMO Compendium http://www.imo.org.yu
This website is dedicated to mathematical olympiads, and we hope it will be of use to all those who prepare for math competitions or simply love problem mathematics.
International Mathematics Project Competition (IMPC) http://www.katev.org/impc
We honorably inform that the seventh International Mathematics Project Competition (IMPC-2005) will be held between 17-21 May 2005 in Almaty, the old capital city of Kazakhstan. The competition aims at inspiring and motivating mathematically talented high school students by exposing them to the beauty and variety of mathematics with technological application.
Kiran Kedlaya's Math Related Web Sites Listing http://unl.edu/amc/a-activities/a4-for-students/K-links.html
This directory is intended to catalog resources on the Web of possible use to mathematically motivated students, their parents and teachers.
Math Forum http://mathforum.com/mam/00/612/index.html
This page was designed for Mathematics Awareness Month. It is ranked as one of the best. It contains links to mathematicians who have made significant contributions to mathematics and its applications.
MathCounts http://www.mathcounts.org
A national math competition for Jr. High Students (6-8th graders) -- it has been around for more than 20 years. Is held regionally, state wide, and then nation wide.
Math Is Power http://www.mathispower.com/
Contains Problems of the Week relating elementary and middle school mathematics in geometry, algebra, discrete mathematics, trigonometry and calculus.
Math Meet http://math.uww.edu/mathmeet
A free, on-line, team mathematics competition for middle and high school teams. Held Mid April, sponsored by CLARC.
MathPath http://www.mathpath.org/
Online learning resource and summer camp for grades 6, 7, and 8.
Nick's Mathematical Puzzles http://www.qbyte.org/puzzles/
A collection of more than 100 puzzles ranging over geometry, probability, number theory, algebra, calculus, and logic. Hints are provided, along with answers, fully worked solutions, and links to related mathematical topics. Many of the puzzles are elementary in their statement, yet challenging. New puzzles are added on a regular basis.
Online Companion to the Special Interfaces Issue http://wwwlinforms.org/ebiz/interfaces
A forthcoming special issue of Interfaces on OR/MS applied to e-business is now freely available. Its seven papers collectively demonstrate that decision technology is becoming a powerful adjunct to information technology as the digital economy matures.
QuestBridge http://www.questbridge.org
Pairs outstanding low-income stuents with full four-year scholarships to 12 QuestBridge partner colleges. Qualified students can apply for admission to any or all of our partner schools through the College Match using our free online application.
Rasko Jovanovic`s World of Mathematics http://milan.milanovic.rog/math/english/contests.html
Explores a connections between Pascal Triangle and the Fibonacci numbers.
Swarthmore http://forum.swarthmore.edu
A must page for students and teachers of mathematics K-12. This site contains many useful links and features a Problem of the Week.
Terry Wesner's page http://www.totallyfreemath.com
An author for William C. Brown/McGraw Hill Publishers for 25 years. "I feel it is time to start giving back to the educational community that has supported me for all of those years. As time and resources allow, I will be providing all of my books and the teacher's resource materials for free download.
The site
THEA practice tests http://www.testprepreview.com/thea_practice.htm
These are online THEA (Texas Higher Education Assessment) practice tests at no charge. The site in general also has a wide variety of other practice tests.
Valentin Vornicu http://www.mathlinks.ro
A former Romanian IMO Team Member, currently an undergraduate student in Mathematics at University of Bucharest. He thought that the site he had forged would fit in quite nicely.
The site's address would be www.mathlinks.ro and it has a math forum, with a lot of users, most of them being former, current or future IMO contestants, download problems section and also a weekly contest - similar with USAMO in difficulty. It is not as big as the mathforum (yet :-) ).
Wolfram http://mathworld.wolfram.com/
A free service for the mathematical community provided by Wolfram Research, makers of Mathematica, with additional support from the National Science Foundation Includes all sorts of problem solving pages.
World of Mathematical Equations http://eqworld.ipmnet.ru
The EqWorld website presents information on solutions to various classes of algebraic, ordinary differential, partial differential (mathematical physics), integral, and other mathematical equations. It also outlines some methods for solving equations, includes interesting articles, lists, useful handbooks, and "monographs," etc. More advanced than most high school math levels, but included here for reference.
Kiran Kedlaya -- Math Related Web Sites
This directory is intended to catalog resources on the Web of possible use to mathematically motivated students, their parents and teachers.
The directory was started by Kiran Kedlaya (http://www-math.mit.edu/~kedlaya/)
(kedlaya[at]math[dot]mit[dot]edu). Please contact me directly with comments about broken links or suggested new links
Math circles
A "math circle" is a group of students and adults who get together periodically to explore mathematics in an informal, extracurricular setting. The phenomenon seems to have begun in the Soviet Union (as described in the book Mathematical Circles, by Fomin, Genkin, and Itenberg), but has since been brought to America by a wave of expatriate Russian mathematicians.
A similar function is often served by the practice meetings of teams for the ARML competition. However, math circles usually involve deeper exploration and less emphasis on competitions.
Math circles, as well as other programs that do not strictly follow the "circle" protocol but operate in a similar spirit, are actually pretty widespread; if you live in an at all populated area of the US (especially near a major university), there probably is one near you. (More links to such programs would be most appreciated!)
The Art of Problem Solving folks apparently run a group at the University of California, San Diego.
Bob Kaplan's math circle (Boston area)
Bay Area Mathematical Circles consists of four circles in the San Francisco area. I have been involved with one of these, the Berkeley Math Circle.
The Mu Alpha Theta organization is a sort of national analogue of what I'm describing here. (That and I couldn't think of where else to put it.)
University of Chicago Young Scholars Program
UC Irvine Math Circle
University of Texas Saturday Morning Math Group
University of Utah Math Circle
For middle school students
This section is out of my expertise, so I could use suggestions for useful links.
Art of Problem Solvingis a new discussion forum; it may also be relevant for high schoolers.
Mathcounts
Johns Hopkins' Study of Exceptional Talent (the original SAT-at-age-13 program, affiliated with the CTY summer study program) has descendants in various parts of the country, e.g., Duke's Talent Identification Program.
Math is Fun is mainly a K-12 website, but it can sometimes help to have the basic concepts explained, plus we have plenty of math puzzles. The site has been around for 6 years, and is popular with schools.
Visual Math Learning is a free online interactive tutorial for pre-algebra students that is rich in games, puzzles, and animated manipulatives that emphasize learning concepts by visualization
Kodawari House mathematics, including arithmetic, created for children.
Regional contests
Many of these links were harvested from this site.
Bay Area Math Meet (San Francisco area)
Bay Area Math Olympiad(San Francisco area)
Colorado Math Olympiad
Florida Atlantic University-Stuyvesant Alumni Mathematics Competition (Palm Beach/Broward counties and vicinity)
Furman University Wylie Mathematics Tournament (Southeast US)
Harvard-MIT Math Tournament (New England)
Lehigh University High School Math Contest (Pennsylvania)
Maritime Mathematics Competition (Canadian maritime provinces)
Massachusetts Association of Math Leagues
Nassau Country Interscholastic Math League (Long Island)
The Math League (New England)
North Carolina State Math Contest
Oklahoma State University High School Math Contest
Polya Mathematics Competition (San Francisco area)
Rice Math Tournament (Houston)
University of Maryland Math Competition
University of South Carolina High School Math Contest
University of Wisconsin Talent Search
National contests
Beware that "national" sometimes means US, sometimes Canada, sometimes both. For international contests, see the AMC Problem Directory and/or the IOI Secretariat.
AMATYC Student Math League
American Mathematics Competitions
American Regions Math League; includes links to team web sites
Canadian Mathematics Competition
Canadian Mathematical Olympiad
Canadian Open Mathematics Challenge
IML Math League
International Mathematical Talent Search
Mandelbrot
Mathematical Contest in Modeling
Mu Alpha Theta
USA Math Talent Search
Science fairs
These are competitions in which students submit research projects that they have been working on for some time beforehand. Usually these projects are done either in collaboration with, or at least at the suggestion of, a mentor; the RSI program specializes in connecting students with mentors and projects, but you may be able to find one on your own simply by getting in touch with, say, someone at your local university.
Davidson Fellowships (arts and sciences)
Intel (formerly Westinghouse) Science Talent Search (seniors only)
International Science and Engineering Fair
Siemens Westinghouse Science and Technology Competition (seniors only)
Summer (and other times) programs
A number of these programs are supported by the American Mathematical Society Epsilon Fund, which is actively seeking contributions to build an endowment. The AMS also maintains a directory of summer math programs more comprehensive than this one.
Canada/USA Mathcamp (various locations)
Clay Mathematics Institute Research Academy (Boston; not summer)
Hampshire College Summer Studies in Mathematics
Math Olympiad Program (University of Nebraska)
PROMYS (Boston University)
Ross Young Scholars Program (Ohio State University)
Research Science Institute (MIT)
Rutgers Young Scholars Program
Southwest Texas Honors Summer Math Camp
Stanford Mathematics Camp
University of Michigan Math Scholars
Journals, newsletters, and other correspondence
Crux Mathematicorum with Mathematical Mayhem
KöMaL
Mathematical Olympiads Correspondence Program
Suggestions for further inquiry
Crux Mathematicorum with Mathematical Mayhem downloadable
pictures of the 2006 MOSP
The Akamai Foundation
The Akamai Foundation was established by Akamai Technologies, Inc. and was initially funded by Akamai executives and its employees. Akamai Technologies helps companies by optimizing Web site performance, delivering broadcast-quality streaming media, and providing interactive application services. The Foundation chose to focus on mathematics because Akamai was conceived and founded on mathematical innovation.
The Akamai Foundation is dedicated to excellence in mathematics in the hopes that we can encourage America's next generation of technology innovators. Their mission is to reach out to students in grades K-12 with the message that mathematics is important, demonstrating to them that it can be magical and fun and in the process, helping them to realize that math can lead to some very exciting career opportunities.
In February 2001, just as the AMC 10 and AMC 12 were being given and the AIME 2001 was going to press, the Akamai Foundation of Boston made a large charitable gift to the Mathematical Association of America (MAA) on behalf of the American Mathematics Competitions. This large charitable gift allowed MAA American Mathematics Competitions to fund scholarships in 2001 and 2002, and a national USAMO in 2002.
In 2001and 2002 the Akamai Foundation provided $1,000 scholarships to the top male and female American Invitational Mathematics Examination (AIME) scores in each state.
During the 2001-2002 academic year:
The AIME scholarships for the top scorers from each state continued
Participants in the United States of America Mathematical Olympiad (USAMO) were flown in May 2002 to MIT (Massachusetts Institute of Technology), Cambridge, MA, for the administration of the Olympiad. Through its charitable gift, The Akamai Foundation served as host to the students, proctors, and exam graders for this three day event. Students were also treated to area tours, special guest speakers, and related social and mathematical activities.
In June 2002, there was an enhanced Mathematical Olympiad Summer Program (MOSP), expanding the number of students to 178.
In 2004 the Akamai Foundation provided additional funds so the summer MOSP program could include an additional 24 students (9th graders).
HACKING SITES
http://www.hackr.org/links.php
https://www.astalavista.net/?cmd=proxy
http://www.astalavista.com/
http://thc.org/papers.php
Maybe not good links but there's thing to see:
http://www.blacksecurity.org/alpha/links.html
http://www.web-hack.ru/
http://www.megasecurity.org/tools_dl.html
http://www.windowsecurity.com/
http://www.fileupdates.net/
http://www.milw0rm.com/links/
http://www.foundstone.com/us/resources-free-tools.asp
https://www.astalavista.net/?cmd=proxy
http://www.astalavista.com/
http://thc.org/papers.php
Maybe not good links but there's thing to see:
http://www.blacksecurity.org/alpha/links.html
http://www.web-hack.ru/
http://www.megasecurity.org/tools_dl.html
http://www.windowsecurity.com/
http://www.fileupdates.net/
http://www.milw0rm.com/links/
http://www.foundstone.com/us/resources-free-tools.asp
Alison Zhu
SLGGS Student Wins Top Geography Prize
SLGGS student Alison Zhu has just been awarded the Royal Geographical Society and Institute of British Geographers’ prize for the best results in the OCR Examination Board’s GCSE A Geography examination.
Alison, a pupil at Simon Langton Girls’ Grammar School, came top out of 23,410 candidates nationally, achieving 194 out of a possible 200 marks.
Mrs Murrell, Head of Geography at the school for the last 8 years said:
“I’ve been teaching Alison since year 7 and she is one of the most intuitive geographers I have ever taught. A large part of her success is down to her dedicated approach to her work – she never accepts second best. Whilst she is an outstanding pupil, she is one of many talented students who did well in the examination; we entered 69 candidates, and 56.5% of them achieved an A* or A grade”.
Of her success, Alison said: “ It was a tremendous surprise to receive this award, as I had no idea it was coming! All the hard work in the summer seems well worth it now”.
Alison hopes, ultimately, to study Mathematics at university.
SLGGS Student Selected for National Squad in International Maths Olympiad
SLGGS student Alison Zhu, in Yr 12, is the only state school pupil and one of only two girls in the country selected to take part in a 9-strong National Squad competing in the International Mathematical Olympiad to be held in Vietnam this summer.
She won her place alongside students from leading public schools by competing in the Senior Mathematics Challenge, entered by state and public schools all over the UK and gaining one of the top scores, despite being a year younger than other competitors.
Alison will fly to Rhodes with the squad to compete in the Balkans Mathematical Olympiad in Greece from 26 April to 2 May. She hopes that if she does well, she will then go to Hanoi, Vietnam for the International Mathematical Olympiad, which takes place from 19-31 July.
Alison said: "I have already attended the training camp at Trinity College, Cambridge and I’m really looking forward to competing. It is an exciting opportunity and aside from the challenge of Mathematics, which I enjoy, it will be amazing to visit these countries and also to have the opportunity to meet mathematicians from schools all over the world."
Mrs Sutton, Head of 6th form said: "We are extremely proud of Alison. She is an outstanding student, with ambitions to study at Cambridge. She really excels in both Mathematics and Physics and is an inspiration to other girls. Given recent reports in the press suggesting that students should be paid to study these subjects in order to halt their decline, it is heartening to see that we, as a school, are bucking the trend. We have a very healthy number of girls studying both Maths and Physics and doing really well in them".
https://nrich.maths.org/cgi-bin/discus/discus.cgi
https://nrich.maths.org/discus/messages/114352/114738.html
http://www.2030.com.cn/bbs/viewthread.php?tid=174&extra=page%3D1&page=5
http://www.2030.com.cn/bbs/space.php?uid=1065
Chủ Nhật, 29 tháng 7, 2007
Sherry Gong- A super girl
Sherry Gong
Phillips Exeter Academy, Exeter, NH
Junior
Hobbies
My hobbies include reading (anything I can, whenever I have time), memorizing poems, Chung Do Kwan (which I started this year and will not be able to continue)
Clubs
At school I participate in Physics Club, and will be captain of the Math Club next year.
Experience
International Math Olympiad (seventh grade; bronze medal in eighth grade (2003); silver medal in ninth and tenth grade (2004, 2005)); USA IMO team 2005, USA Math Olympiad (honorable mention in 2003, participated in 2004, winners in 2005 and 2006,), Olimpiada Iberoamericana de Matemáticas (For Spain, Portugal and Latin America) (2003, gold medal), Math Olympiads of Central America (silver medals in both sixth grade (2001) and seventh grade (2002)), National Geography Bee in seventh grade (2002) island championship and twelfth place nationally
Biography
I was born in Long Island, NY in July, 1989 and moved to Canada when I was two. When I was six, I moved to Chicago, and then to Puerto Rico, where I currently reside (although I go to a boarding school in New Hampshire). In the area of competitions, I took the IMO on the Puerto Rican team three times and on the US team once. I also attended the US Math Olympiad Program (MOP) in 2003, 2004, and 2005. In middle school, I participated in National Geography Bee. I would like to thank Mr. Henner, Mr. Zhang, Mr. Saltman, Ms. Waterman, Mr. DiCarlo, Dong Fang Hu, as well as my parents and classmates for their support and for helping me get this far in physics. My favorite color is blue, I preferred pink in elementary school and purple in middle school. I like walking on mountainous areas, especially in tropical rain forests. Some of my favorite books are Lord of the Rings, Othello (which I find to be the best Shakespeare play by far), The Unvanquished (Faulkner), and Ender's Game. In middle school I actually believed in Tolkien’s tales of Middle Earth (which isn't to say that I don't anymore). Some of my favorite poems are Fire and Ice, The Raven and Annabel Lee and everything else written by Poe, Namarie (Galadriel's Lament), and the 15th poem of “Veinte Poemas de Amor y una Cancion Desesperada”. I took Go Ju Ryu for about half a year before I started attending Exeter. At MOP 2004 the girls were on the eleventh floor and I used the elevator a total of twice (once on the first day, once on the last). I learned how to knit three times. Unfortunately, I also forgot how to do it three times.
Sherry won a silver medal at the 2005 IMO in Merida, Mexico for the US Team. She competed at the IMO in 2004 for Puerto Rico and received a silver medal. She placed 12th nationally in the Geography Bee in 2002 and was a member of the 2005 and 2006 USA Physics Olympiad Team receiving a silver medal in last year's competition. She was designated the Clay Mathematics Institute Olympiad Scholar in 2005. She likes computer programming, geography and enjoys reading. She credits her Dad, Professor Li and Dr. Zuming Feng for influencing her interest in mathematics and in pursuing her live of competition. She will be attending Harvard University in the fall.
U.S. Physics Team Wins Golds/Silver
2006 U.S. Physics Team Medalists. (From left to right): Otis Chodosh (Gold), Sherry Gong (Silver), William Throwe (Gold), Menyoung Lee (Gold), Henry Tung (Gold)
College Park, MD (July 16, 2006) - Every U.S. student sent to the 2006 International Physics Olympiad held this year in Nanyang University in Singapore, will bring home a medal, and four of those are gold.
Menyoung Lee, a senior at Thomas Jefferson High School for Science and Technology, Alexandria, VA, won a gold medal for the second year in a row. The other gold medalists are: William Throwe, a senior at Shoreham-Wading River High School, Shoreham, NY. Last year Throwe served as an alternate to the team. Henry Tung, a junior at Torrey Pines High School in San Diego. Otis A Chodosh, a senior at the Oklahoma School of Science and Mathematics in Oklahoma City. Bringing home a silver medal: Sherry Gong, a junior at Phillips Exeter Academy in Exeter, NH.
The U.S. team met with great success, head coach Robert Shurtz said. In an unofficial ranking of countries based on total score of the five team members, the United States ranked second. Chinas students had the highest overall total scores. This was largest International Physics Olympiad to date with 86 nations participating with a total of 383 competitors. Last year, the team brought home two golds, two silvers and a bronze medal.
Shurtz, a physics teacher at the Hawkens School in Gates Mills, OH, and assistant coach Paul Stanley, a physics and astronomy associate professor at Beloit College in Wisconsin, accompanied the team to the nine-day competition.
The U.S. Physics Olympiad Program was started in 1986 to promote and demonstrate academic excellence and prepare students to compete in the International Physics Olympiad. The U.S. Physics Team is co-sponsored by the American Association of Physics Teachers and the American Institute of Physics.
Sherry Gong named Clay Olympiad Scholar, June 27, 2005
Jim Carlson, Guhua Gong,Sherry Gong,Liangqing Li
Miss Sherry Gong, a 10th grade student at Phillips Exeter Academy, was named the 2005 Clay Olympiad Scholar at a ceremony in Washington DC on June 27, 2005.
The Clay Olympiad Scholar Award recognizes the most original solution to a problem on the US American Mathematics Olympiad (USAMO). It consists of a commemorative plaque and cash award to the recipient, and a cash award to the recipients' school. The award is presented each year at the official awards dinnner for the USAMO held in June in Washington, DC at the State Department Ballroom.
Sherry Gong, daughter of Guhua Gong and Liangqing Li of San Juan, Puerto Rico, attended schools in Puerto Rico until this last year when she enrolled at Phillps Exeter Academy in Exeter, New Hampshire. Sherry attended a mathematics olympiad for the first time when she was in the sixth grade — the 3rd Olympiada Matematica de Centroamerica y el Caribe. There Sherry received a silver medal and also a special award for the most original solution. It was the first such award in the history of this olympiad. Sherry received a silver medal the next year at the same olympiad, and in 2003 she received a gold medal at the XVIII Olympiada Iberoamericana de Matematicas. She also received a bronze medal in the 44th IMO (2003) and and a silver medal in the 45th IMO (2004).
In addition to mathematics, Sherry is interested in physics and computer programming. She won a position in the 24-member USA Physics Olympiad Team (2005). She enjoys seeing the connection between physics and mathematics, and she likes to find her own solutions when given a math or physics problem.
Sherry won the State Championship for the Geo Bee and represented Puerto Rico in the National Geo Bee in Washington DC (2002). She also likes karate, poetry and reading.
U.S.A. International Mathematical Olympiad 2005 Team
Standing, from left to right: Joseph A. Gallian, Eric Larson, Krishanu Sankar, Sergei Bernstein, Adam Hesterberg, Delong Meng, Jacob Steinhardt, Sherry Gong.
Kneeling: Tedrick Leung, Alex Zhai, Arnav Tripathy, Brian Lawrence, Haitao Mao.
Sherry Gong is a 12th grader at the Phillips Exeter Academy in Exeter, N.H. Sherry tied for second in this year's competition and won a $15,000 scholarship from the Akamai Foundation.
olympiad2005remarks from claymath.org
It is a great honor to be here this evening
with so many talented young people from
across the United States. You are here
tonight because of your ability, interest, and
achievement in mathematics. On behalf of
the Clay Mathematics Institute, of its
founder, Landon Clay, and of his wife and
fellow director, Lavinia Clay, I congratulate
each of you.
My role tonight is to present the Clay
Olympiad Scholar Award, which recognizes
the most original solution to an Olympiad
contest problem. In a few minutes I will
announce the winner. But first, some brief
comments.
Most contests, whether they be in athletics
or mathematics, place a premium on
strength and speed. These are important
qualities, qualities to be admired. But there
is another quality that is perhaps of still
greater value: originality. My dictionary
defines originality as
the ability to think creatively or
independently: a writer of great
originality
the quality of being novel or unusual: he
congratulated her on the originality of her
costume
Originality is not likely the quality that the
layman immediately associates with
mathematics, or with science more
generally. But originality is *the* quality
which drives knowledge forward, which
opens up new frontiers. And it is therefore
the highest accolade that we can give.
Consider for a moment the case of Albert
Einstein, whose centenary we celebrate this
year. At no time in his career -- as a high
school student, as an employee of the Swiss
patent office, as a renowned physicist -- did
Einstein dazzle by the speed of his problem
solving abilities. Rather it was the depth and
originality of his ideas that made the
difference. And what a difference it made!
He gave us the special and general theories
of relativity, and with them keys to
understanding light, subatomic particles,
black holes, and the big bang. He played a
key role in the development of quantum
theory, even though he never really
"believed" in it.
To repeat, it was originality that made the
difference for Einstein. And it was
originality that has always made the
difference in the work the greatest
mathematicians, such as Archimedes, or
Riemann.
Now has come the time to speak aobut this
year's awardee, Miss Sherry Gong. Until
last year, Sherry attended school in San
Juan, Puerto Rico, where her parents are
professors of mathematics at the University
of Puerto Rico. Sherry attended a
mathematics olympiad for the first time
when she was in the sixth grade. This was
the 3rd Olympiada Matematica de
Centroamerica y el Caribe. There Sherry
received a silver medal and also a special
award for the most original solution. It was
the first such award in the history of this
olympiad. Sherry received a silver medal the
next year at the same olympiad, and in 2003
she received a gold medal at the XVIII
Olympiada Iberoamericana de Matematicas.
She also received a bronze medal in the 44th
IMO (2003) and and a silver medal in the
45th IMO (2004).
This past year, Sherry has been a student at
Phillips Exeter Academy, in Exeter, New
Hampshire.
Besides mathematics, Sherry likes physics.
She won a position in the 24-member USA
Physics Olympiad Team (2005). She enjoys
seeing the connection between physics and
mathematics, and she likes to find her own
solutions when given a math or physics
problem.
Sherry also likes Geography. She was the
State Championship for the Geo Bee and
represented Puerto Rico in the National Geo
Bee in Washington DC (2002). Besides
math and science, Sherry likes computer
programing, karate, poetry and reading.
It is a great pleasure to present the Clay
Olympiad Scholar Award to Sherry Gong.
She will receive a commemorative plaque
and a check to help with her education. Her
school, Phillips Exeter Academy, will also
receive a check to recognize its role in
Sherry's success.
On behalf of the Clay Mathematics Institute,
its Scientific Advisory Board, and its Board
of Directors, I congratulate Sherry; her
parents, Professors Guhua Gong and
Liangqing Li; her school in Puerto Rico,
Phillips Exeter Academy, and Sherry's
teachers.
Sherry Gong, Phillips Exeter Academy
IMO Silver Medalist (2004, 2005)
IMO Bronze Medalist (2003)
IMO Honorable Mention (2002)
US IMO Team member (2005)
Puerto Rican IMO Team member (2002 - 2004)
USAMO Winner (2005)
MOSP member (2003 - 2005)
Checking out a statue: Sherry Gong & Ameya Velingker
Sherry Gong '07 Joins US Physics Olympiad Team
College Park, MD (May 28, 2006)— Sherry Gong '07 was one of five students selected today to represent the US at the 2006 International Physics Olympiad, a competition among high-school physics students, to be held this year in July at the National Institute of Education, Nanyang Technological University, Singapore. Teams from 85 countries will compete, the most that have ever participated.
In May, 24 top US physics students attended a nine-day training camp at The University of Maryland, where, through classes, labs and special lectures, they were coached on difficult physics concepts before taking a final, qualifying exam. They also made a trip to nearby Washington, DC, to meet personally with their state senators and representatives in the US Congress and House of Representatives. The American Association of Physics Teachers (AAPT,) a non-profit organization based in College Park, MD, co-sponsored these activities.
Last year at the international competition held in Salamanca, Spain, the U.S. team brought home two golds, two silvers and a bronze medal.
The US Physics Olympiad Program was started in 1986 by AAPT to promote and demonstrate academic excellence. The Olympiad is a nine-day international competition among pre-university students from more than 80 nations.
2006 US Physics Team
Sunday, July 16, 2006
College Park, MD (July 16, 2006) - Every U.S. student sent to the 2006 International Physics Olympiad held this year in Nanyang University in Singapore, will bring home a medal, and four of those are gold.
Menyoung Lee, a senior at Thomas Jefferson High School for Science and Technology, Alexandria, VA won a gold medal for the second year in a row.
The other gold medalists are: William Throwe, a senior at Shoreham-Wading River High School, Shoreham, NY. Last year Throwe served as an alternate to the team. Henry Tung, a junior at Torrey Pines High School in San Diego. Otis A Chodosh, a senior at the Oklahoma School of Science and Mathematics in Oklahoma City.
Bringing home a silver medal: Sherry Gong, a junior at Phillips Exeter Academy in Exeter, NH.
“The US team met with great success,” head coach Robert Shurtz said. “In an unofficial ranking of countries based on total score of the five team members, the US ranked second.” China’s students had the highest overall total scores.” This was largest International Physics Olympiad to date with 86 nations participating with a total of 383 competitors. Last year, the team brought home two golds, two silvers and a bronze medal. He also noted that the traveling team met on June 30th at Cal Poly - Pomona for four days of laboratory work as the final step in preparing for the international competition. We were all grateful to be hosted once again by Mary Mogge, former academic director of the US Physics Team and chair of the physics department at Cal Poly. We had a very successful and enjoyable mini-camp as a result of the hospitality and helpfulness of Mary and the staff of the physics department. We flew on July 4th for Singapore. We had two days to adjust to the twelve hour time difference and explore Singapore before the competition officially began on July 8th. This was a very hard working and a very fun group of five students to work with. I'm extremely excited and proud of their accomplishments. Four golds and one silver and second place overall makes this one of the best showings of the US Physics Team at any IPhO. I'll greatly miss working with this talented, cohesive, dedicated, and humorous group of students.
Sherry Gong receives a silver medal at this year's 37th annual physics competition in Singapore
Sherry Gong '07 Awarded Silver Medal at International Physics Competition
Sherry Gong receives a silver medal at this year's 37th annual physics competition in Singapore
Sherry Gong ’07 earned a silver medal at this year’s 2006 International Physics Olympiad, the first international physics award to be awarded by an Exeter student since 1999. The Olympiad is a worldwide competition among high-school physics students, held last month at the National Institute of Education, Nanyang Technological University in Singapore. She was among five 2006 U.S. physics team members, four of whom earned gold medals.
Physics instructor Scott Saltman said Sherry’s passion and commitment to working hard have resulted in her accomplishments. “Sherry is passionate about physics. Her achievement in this competition is a tribute to her hard work and her tremendous insight. It's a great honor for the Academy to have a student reach this prestigious level,” he said.
The other team players were awarded gold medals. Menyoung Lee, a senior at Thomas Jefferson High School for Science and Technology, Alexandria, VA, who won a gold medal for the second year in a row; William Throwe, a senior at Shoreham-Wading River High School, Shoreham, NY; Henry Tung, a junior at Torrey Pines High School in San Diego; and Otis A Chodosh, a senior at the Oklahoma School of Science and Mathematics in Oklahoma City.
Team head coach Robert Shurtz said the U.S. team met with great success, earning an unofficial ranking of second. Countries were judged based on a total score of the five-team members. Chinas’ students came in first with the highest overall total scores. This was largest International Physics Olympiad to date with 86 nations participating with 383 competitors. Last year at the international competition held in Salamanca, Spain, the U.S. team brought home two gold, two silver and a bronze medal.
In May, 24 top US physics students attended a nine-day training camp at The University of Maryland, where, through classes, labs and special lectures, they were coached on difficult physics concepts before taking a final, qualifying exam. They also made a trip to nearby Washington, DC, to meet personally with their state senators and representatives in the US Congress and House of Representatives.
The 2006 U.S. physics traveling team
The American Association of Physics Teachers (AAPT,) a non-profit organization based in College Park, MD, co-sponsored these activities. The U.S. Physics Olympiad Program was started in 1986 to promote and demonstrate academic excellence and prepare students to compete in the International Physics Olympiad. The U.S. Physics Team is co-sponsored by the American Association of Physics Teachers and the American Institute of Physics.
http://www.agnesscott.edu/lriddle/women/women.htm
Association for Women in Mathematics
Essay Contests Association for Women in Mathematics
USAMO Winners Sherry Gong and David Lawrence, with Prof. Gregory Galperin
Brian Lawrence and Sherry Gong.
Waiting for the Lecture (given at the State Department) to begin: from right: Krishanu Sankar, Eric Larson, Tedrick Leung, Sergei Bernstein, Arnav Tripathy, Adam Hesterberg, Brian Lawrence and Sherry Gong.
Standing, from left to right: Joseph A. Gallian, Eric Larson, Krishanu Sankar, Sergei Bernstein, Adam Hesterberg, Delong Meng, Jacob Steinhardt, Sherry Gong.
Kneeling: Tedrick Leung, Alex Zhai, Arnav Tripathy, Brian Lawrence, Haitao Mao.
After visiting the Cryptologic Museum the group of winners and their families had a Picnic on the Lawn in front of the building.
USAMO Medals, before presentation.
Standing, from left to right: Adam Hesterberg, Krishanu Sankar, Brian Lawrence, Sergei Bernstein, Eric Larson, Delong Meng, Jacob Steinhardt.
Front: Sherry Gong, Haitao Mao, Alex Zhai, Arnav Tripathy, Tedrick Leung.
The group receiving the Robert P. Balles USAMO Winners Awards.
Balles Awards
Balles Awards
Getting Ready to take the Team Tests.
Sherry Gong, Alex Zhai and DeLong Meng
2007 USAMO Ceremonies
family of Tedrick Leung took photos
USAMO 2006
AMC Director Steven Dunbar took these photos
Washington, D.C. Ceremonies for the Winners of the United States of 2005 America Mathematical Olympiad
Opening gathering at The Mathematical Association of America Headquarters
Traditional formal Portrait taken at the Einstein statue, on the Mall
Formal Dinner at the State Department
U.S. Physics Team Honored by Members of Congress
Yesterday, the 24 members of this year's U.S. Physics Team were on Capitol Hill, meeting their Senators and Representatives. The Physics Team is organized annually by the American Association of Physics Teachers and sponsored by all ten of the Member Societies of the American Institute of Physics. These 24 high-school age students from across the U.S. were selected for the 2006 Team through two competitive examinations. They arrived at the University of Maryland in College Park, Maryland on May 19 for a week-long training camp, where they are undergoing intensive training and testing in problem-solving and laboratory skills.
Five team members will be selected to compete in the 2006 International Physics Olympiad, a physics competition for pre-university age students. This year's Olympiad will be held July 8 - 17 at the National Institute of Education, Nanyang Technological University, Singapore. U.S. Physics Team members earned one bronze, two silver, and two gold medals at last year's competition in Salamanca, Spain.
In addition to meeting with their own Members of Congress, the Team Members gathered to hear talks from Representatives Vernon Ehlers (R-MI) and Rush Holt (D-NJ), both physicists, and to present them with gifts and certificates for their many years of support for the Physics Team. At the same time, the American Association of Physics Teachers also awarded Holt and Ehlers lifetime memberships. In honor of the Team, Rep. Ehlers inserted a statement into the May 25 Congressional Record congratulating the students and wishing them well. His statement follows:
"Mr. Speaker, I rise today to honor the achievements of the members of the 2006 United States Physics Olympiad Team. These 24 individuals have shown tremendous aptitude in physics and leadership among their peers.
"It is very challenging to earn a spot on this prestigious team. After being nominated by their high school teachers and taking a preliminary exam, 200 students qualified to take the second and final screening exam for the U.S. Physics Team. The 24 survivors of that group represent the top physics students in the U.S., and they are now at a nine-day training camp of intense study, examination and problem solving. Five of these exceptional students will advance and represent the United States in a tremendous international competition in July at the International Physics Olympiad in Singapore.
"Members of the 2006 team include: Sophie Cai, ZeNan Chang, David Chen, Otis Chodosh, Kenan Diab, Jiashuo Feng, Yingyu Gao, Sherry Gong, Timothy Hsieh, Rui Hu, Ariella Kirsch, Jason LaRue, Men Young Lee, David Lo, Benjamin Michel, Hetul Patel, Veronica Pillar, Nimish Ramanlal, Ingmar Saberi, William Throwe, Arnav Tripathy, Henry Tung, Philip Tynan and Haofei Wei.
"Mr. Speaker, as a nuclear physicist and former physics professor, I have worked to promote math and science education and to recognize the pivotal role these fields play in our nation's economic competitiveness and national security. Educating our K-12 students in math and science is very important. It is encouraging to see so many young, outstanding physics students enthusiastic about science, and I note that many of them chose to pursue science as a result of a teacher or family member who encouraged them along the way. Making sure our teachers are well-equipped to teach science and math is very important in fostering the interest of future generations in these subjects.
"I hope the composite enthusiasm of these students and the other semifinalists will allow them to consider future careers in science, technology, engineering and math. Furthermore, I hope some of them consider running for public office and add their expertise to the policy world! I am very thankful for these future leaders and ask that you please join me in congratulating them on their wonderful achievements and wishing the top five the best of luck as they represent the United States in Singapore."
Audrey T. Leath
Media and Government Relations Division
American Institute of Physics
fyi@aip.org
Đăng ký:
Bài đăng (Atom)