The early history of mechanical game playing was numerous frauds. The most notorious of these was Baron Wolfgang von Kempelen's. "The Turk", a supposed chess playing automation that defeated napoleon before being exposed as a magician's trick 1846, Charles Babbage appears to have contributed the first serious discussion of the feasibility of computer chess and checkers. He also designed, but did not build, a special purpose machine for playing tic-tac-toe. The first game plying machine was built around 1890 by the Spanish engineer Leonrdo Torres y Quevedo. It specialized in the “KRK" chess endgame, guaranteeing a win with king and rook from any position.
In 1951, Alan Turing wrote the first computer program capable of playing a full game of chess. But Turing's program never atually ran on a computer; it was tested by hand simulation against a very weak human player, who defeated it. Meanwhile D.G. Prinz had written and actually run a program that solved chess problem although it did not play a full game. Alex Bernstein wrote the first program to play a full game of standard chess.
John McCarthy conceived the idea of alpha beta search in 1956, although he did not publish it. The NSS chess program used a simplified version of alpha beta; it was the first chess program to do so. According to Nilsson, Arthur Samuel's checkers program also used alpha beta, although Samuel did not mention it in the published reports on the system. Papers describing alpha beta were published in the early 1960s. An implementation of full alpha beta is described by Sladge and Dixon in a program for playing the game of Kalah. Alpha beta was also used by the "Kotok McCarthy" chess program written by a student of John McCarthy. Knuth and Moore provide a history analysis of alpha beta with random successor ordering showed an asymptotic complexity, which seemed rather dismal because the effective branching factor is not much less than b itself. They then realized that the asymptotic formula is accurate. Pearl shows alpha beta to be asymptotically optimal among all fixed depth game tree search algorithms.
John McCarthy conceived the idea of alpha beta search in 1956, although he did not publish it. The NSS chess program used a simplified version of alpha beta; it was the first chess program to do so. According to Nilsson, Arthur Samuel's checkers program also used alpha beta, although Samuel did not mention it in the published reports on the system. Papers describing alpha beta were published in the early 1960s. An implementation of full alpha beta is described by Sladge and Dixon in a program for playing the game of Kalah. Alpha beta was also used by the "Kotok McCarthy" chess program written by a student of John McCarthy. Knuth and Moore provide a history analysis of alpha beta with random successor ordering showed an asymptotic complexity, which seemed rather dismal because the effective branching factor is not much less than b itself. They then realized that the asymptotic formula is accurate. Pearl shows alpha beta to be asymptotically optimal among all fixed depth game tree search algorithms.
0 comments:
Post a Comment