[FrontPage] [TitleIndex] [WordIndex

The readings that Lynn asked us to do are:

Shannon on Chess - this one will be presented on Monday, so we will have to meet sometime Sunday to discuss it, and it therefore has to be read soon! Note: we are meeting at 4PM on Sunday 2/4 in the 1st floor EH fishbowl, so if you sign up for this group before then, come to the fishbowl then

Shannon's paper on chess is one of the earliest that discusses the possibility of using artificial intelligence programs to play chess. It was written in 1950 and mentions several things that do not make sense in a modern computing context (e.g. "Machines of this general type are an extension over the ordinary use of numerical computers") but in general stays very relevant even 50 years later. The main point of the paper is to show how to apply the minimax theorem to chess. It first discusses how one might create a function to evaluate a given position and then use minimax with N look-ahead steps to create a viable program. This is called the "Type A" strategy. To improve upon this, Shannon defines some positions as quasi-stable (in the middle of an exchange) and creates a "Type B" strategy that follows unstable positions to their logical conclusion, taking a few promising nodes from the Type A path to extend another M nodes. Finally, Shannon discusses how adding randomness to the algorithm would be beneficial for a couple reasons. To begin with, once a player has found one set of moves that beats a deterministic algorithm, he or she can just play those moves as many times as they want. Secondly, when minimax is applied to a finite number of moves rather than all the way down the search tree to all possible checkmates, there is a possibility that the node found to be the optimal is not actually the best possible play. Therefore, randomly selecting from among the top 3-5 moves might actually yield the best play even though the algorithm claims that it is 3rd best. Shannon concludes by saying that more powerful machines could be built to play chess but that to really shore up the weaknesses of his general approach one would need to create a program that learns from its mistakes.

Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine. Vol 41.

Samuel on Checkers

Slagle on Calculus

Othello (two papers in the middle)

Campbell, Hoane and Hsu. Deep Blue. Artificial Intelligence Journal volume 134, January 2002. http://ece.olin.edu/cr/download?filename=data/Deep_Blue_AIJ_02.pdf

Paper Abstract Since the birth of the artificial intelligence community, there has always been a drive to create a program intelligent enough to play and beat another human at the game of Chess. After the moderate successes of other chess playing computers, such as the Deep Thought series, IBM created Deep Blue. The first iteration lost to the world grand chess champion, Gary Kasparov in 1996. A year later, the improved Deep Blue II won over Kasparov in 1997. This chess machine contains 30 processors that each control 16 special designed Chess Chips that allow a massive parallel, hardware based, game tree search at nearly 100-200 million moves per second. On top of the hardware is sophisticated software that uses a depth limited version of the NegaMax algorithm, which is an enhanced version of alpha-beta pruning, in addition to quiescence searching. A very complex set of evaluation functions combined the knowledge of numerous chess grandmasters to create upwards of 8000 control bits for various evaluation functions and an extremely extensive endgame, opening book, and extended book database. Deep Blue remains one of the most impressive artificial intelligence machines on the planet even a decade after its retirement. --Evan M

Schaeffer, Jonathan and van der Herik, H. Jaap. Games, Computers and Artificial Intelligence. Artificial Intelligence Journal volume 134, January 2002. http://ece.olin.edu/cr/download?filename=data/Intro_Games_AIJ_02.pdf

Kaindl, Herman. Minimaxing: Theory and Practice. AI Magazine, vol. 9 number 3, Fall, 1998. http://ece.olin.edu/cr/download?filename=data/Kaindl_Minimax_AIM_88.pdf

Schaeffer, et al. CHINOOK: The World Man-Machine Checkers Champion. AI Magazine, vol. 17 number 1, Spring 1996. http://ece.olin.edu/cr/download?filename=data/Chinook_AIM_96.pdf

Schaeffer, et al. Man Versus Machine for the World Checkers Championship? AI Magazine, vol. 14 number 2, Summer 1993. http://ece.olin.edu/cr/download?filename=data/Chinook_AIM_93.pdf


2013-07-17 10:46