John McCarthy, a pioneer in artificial intelligence, describes his views on the subject.
"This article for the layman answers basic questions about artificial intelligence. The opinions expressed here are not all consensus opinion among researchers in AI."
Frequent questions are answered, and an overview of the field of artificial intelligence and its branches is provided.
search
Game Tree Search Algorithms Tutorial
Tutorial slides by Andrew Moore available as PDF.
Introduction to algorithms for computer game playing. We describe the assumptions about two-player zero-sum discrete finite deterministic games of perfect information. We also practice saying that noun-phrase in a single breath. After the recovery teams have done their job we talk about solving such games with minimax and then alpha-beta search. We also discuss the dynamic programming approach, used most commonly for end-games. We also debate the theory and practice of heuristic evaluation functions in games.
Introduction to algorithms for computer game playing. We describe the assumptions about two-player zero-sum discrete finite deterministic games of perfect information. We also practice saying that noun-phrase in a single breath. After the recovery teams have done their job we talk about solving such games with minimax and then alpha-beta search. We also discuss the dynamic programming approach, used most commonly for end-games. We also debate the theory and practice of heuristic evaluation functions in games.
Category: tutorial from http://www.autonlab.org
A-Star Heuristic Search Tutorial
Tutorial slides by Andrew Moore available as PDF.
The classic algorithm for finding shortests paths given an admissible heuristic. We'll deal with the notion of admissibility (summary: admissible = optimistic). We show how you can prove properties of A*. We'll also briefly discuss IDA* (iterative deepening A*).
The classic algorithm for finding shortests paths given an admissible heuristic. We'll deal with the notion of admissibility (summary: admissible = optimistic). We show how you can prove properties of A*. We'll also briefly discuss IDA* (iterative deepening A*).
Category: tutorial from http://www.autonlab.org
Best-First and Depth-First Minimax Search in Practice
Most practitioners use a variant of the Alpha-Beta algorithm, a simple depth-first procedure, for searching minimax trees. SSS*, with its best-first search strategy, reportedly offers the potential for more efficient search. However, the complex formulation of the algorithm and its alleged excessive memory requirements preclude its use in practice. For two decades, the search efficiency of “smart” best-first SSS* has cast doubt on the effectiveness of “dumb” depth-first Alpha-Beta.rnrnThis paper presents a simple framework for calling Alpha-Beta that allows us to create a variety of algorithms, including SSS* and DUAL*. In effect, we formulate a best-first algorithm using depth-first search. Expressed in this framework SSS* is just a special case of Alpha-Beta, solving all of the perceived drawbacks of the algorithm. In practice, Alpha-Beta variants typically evaluate less nodes tha
Category: white paper from http://citeseer.ist.psu.edu
Minimax Game Trees
This essay is a detailed explanation of one of the most important data structures ever created for Game Artificial Intelligence. The minimax tree is at the heart of almost every board game program in existence.
The Minimax Game Tree is used for programming computers to play games in which there are two players taking turns to play moves. Physically, it is just a tree of all possible moves.
The Minimax Game Tree is used for programming computers to play games in which there are two players taking turns to play moves. Physically, it is just a tree of all possible moves.
Category: tutorial from http://www.aihorizon.com
Game Trees: Alpha-Beta Search
We will set up a framework for playing a two-person game in which the two players alternate making moves.
The game can normally be represented as a tree where the nodes represent the current status of the game and the arcs represent the moves. The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. The leaves of the game tree represent terminal positions as one where the outcome of the game is clear (a win, a loss, a draw, a payoff). Each terminal position has a score. High scores are good. For example, we may associate 1 with a win, 0 with a draw and -1 with a loss.
The game can normally be represented as a tree where the nodes represent the current status of the game and the arcs represent the moves. The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. The leaves of the game tree represent terminal positions as one where the outcome of the game is clear (a win, a loss, a draw, a payoff). Each terminal position has a score. High scores are good. For example, we may associate 1 with a win, 0 with a draw and -1 with a loss.
Category: tutorial from http://www.cs.mcgill.ca
« previous1 next »
