Philosophy Dictionary of ArgumentsHome
| |||
|
| |||
| Author | Concept | Summary/Quotes | Sources |
|---|---|---|---|
|
Peter Norvig on Computer Games - Dictionary of Arguments
Norvig I 189 Computer Games/artificial intelligence/algorithms/Norvig/Russell: A game can be defined by the initial state (how the board is set up), the legal actions in each state, the result of each action, a terminal test (which says when the game is over), and a utility function that applies to terminal states. In two-player zero-sum games with perfect information, the minimax algorithm can select optimal moves by a depth-first enumeration of the game tree. The alpha–beta search algorithm computes the same optimal move as minimax, but achieves much greater efficiency by eliminating sub trees that are provably irrelevant. Usually, it is not feasible to consider the whole game tree (even with alpha–beta), so we Norvig I 190 need to cut the search off at some point and apply a heuristic evaluation function that estimates the utility of a state. Many game programs precompute tables of best moves in the opening and endgame so that they can look up a move rather than search. Games of chance can be handled by an extension to the minimax algorithm that evaluates a chance node by taking the average utility of all its children, weighted by the probability of each child. Optimal play in games of imperfect information, such as Kriegspiel and bridge, requires reasoning about the current and future belief states of each player. A simple approximation can be obtained by averaging the value of an action over each possible configuration of missing information. >Minimax algorithm. History of mechanical games: The most notorious of these was Baron Wolfgang von Kempelen’s (1734–1804) “The Turk,” a supposed chess-playing automaton that defeated Napoleon before being exposed as a magician’s trick cabinet housing a human chess expert (see Levitt, 2000)(1). Computer chess: In 1846, Charles Babbage (who had been fascinated by the Turk) appears to have contributed the first serious discussion of the feasibility of computer chess and checkers (Morrison and Morrison, 1961)(2). VsBabbage: He did not understand the exponential complexity of search trees, claiming “the combinations involved in the Analytical Engine enormously surpassed any required, even by the game of chess.” Chess: The NSS chess program (Newell et al., 1958)(3) used a simplified version of alpha-beta; it was the first chess program to do so. Alpha–beta pruning was described by Hart and Edwards (1961)(4) and Hart et al. (1972)(5). Alpha-beta was used by the “Kotok - McCarthy” chess program written by a student of John McCarthy (Kotok, 1962)(6). Knuth and Moore (1975)(7) proved the correctness of alpha-beta and analysed its time complexity. Pearl (1982b)(8) shows alpha–beta to be asymptotically optimal among all fixed-depth game-tree search algorithms. >Chess/artificial intelligence/Norvig/Russell. 1. Levitt, G. M. (2000). The Turk, Chess Automaton. McFarland and Company. 2. Morrison, P. and Morrison, E. (Eds.). (1961). Charles Babbage and His Calculating Engines: Selected Writings by Charles Babbage and Others. Dover. 3. Newell, A., Shaw, J. C., and Simon, H. A. (1958). Chess playing programs and the problem of complexity. IBM Journal of Research and Development, 4(2), 320–335. 4. Hart, T. P. and Edwards, D. J. (1961). The tree prune (TP) algorithm. Artificial intelligence project memo 30, Massachusetts Institute of Technology. 5. Hart, P. E., Nilsson, N. J., and Raphael, B. (1972). Correction to “A formal basis for the heuristic determination of minimum cost paths”. SIGART Newsletter, 37, 28–29. 6. Kotok, A. (1962). A chess playing program for the IBM 7090. AI project memo 41, MIT Computation Center. 7. Knuth, D. E. (1975). An analysis of alpha–beta pruning. AIJ, 6(4), 293–326._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition. |
Norvig I Peter Norvig Stuart J. Russell Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010 |
||
> Counter arguments against Norvig
> Counter arguments in relation to Computer Games
Ed. Martin Schulz, access date 2024-04-25