This question was asked in an AI exam. How would you answer such question?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ I would try to answer it by researching the properties of alpha-beta, and then symmetric zero sum games. Then I would consider whether it was a good fit. $\endgroup$– Oliver MasonCommented Dec 21, 2018 at 13:49
-
1$\begingroup$ I attempted an answer, but since you provide so little context, I have to guess at it. (Although the precise definition indicates pure game theory, it would be nice to see how your professor defines a game, because once you mention alpha-beta, I start thinking combinatorial games.) $\endgroup$– DukeZhouCommented Dec 22, 2018 at 1:35
-
1$\begingroup$ @OliverMason I am thinking it is a trick question ;) $\endgroup$– DukeZhouCommented Dec 22, 2018 at 2:01
-
1$\begingroup$ ps-- I had to answer the way I did due to incomplete information, but, if you link the lecture notes, I can be more directly definitive. Simple answer is no. $\endgroup$– DukeZhouCommented Dec 29, 2018 at 1:15
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
If the game is not sequential, there would be no game tree and no need for pruning. Alpha-beta is a technique applied to look-ahead search. Alpha-beta has demonstrated utility in algorithms that play combinatorial games.
(Even in iterated dilemmas, it doesn't really branch because it's simultaneous, more of a vine than a tree. Decisionmaking would be based on mathematical analysis of the payoff matrix and statistical analysis of competitor behavior over time.)
-
1$\begingroup$ I am understanding what you saying, but is a symmetric zero sum game always a simultaneous game (not sequential)? In other words isn't there any sequential symmetric zero sum game? The question itself only ask that so I suppose that you can't specify if is whether sequential or not. $\endgroup$– ExproveCommented Dec 22, 2018 at 12:07
-
$\begingroup$ @Exprove That's what I was wondering--the question only gives a partial description of what is being defined as a game, so I had to intuit that the teacher is talking about the canonical game theory context of simultaneous games. Typically people don't talk about payoff matrixes in the context of combinatorial games. Zero-sum and symmetric are unrelated to the qualities of games that produce models to which look-ahead/pruning can be applied. $\endgroup$– DukeZhouCommented Dec 22, 2018 at 21:44
$\begingroup$
$\endgroup$
Symmetry indicates that a single role definition is shared among the players. Zero-sum indicates that the aggregated gain over all players for any possible disposition of game play is zero.
Alpha-beta is a search thrift strategy invented in 1956 by John McCarthy. It is used by an individual player to maximize the probability of favorable game disposition by selecting from move options based on the permutations of game play dependent on each possible selection.
These do not seem, prima facie, to be mutually exclusive. Alpha-beta may be an effective computing cost reduction strategy on symmetric zero-sum games. An example is chess game play automation. Furthermore, Reinfield (1983) quotes Knuth and Moore (1975): "The most widely used method for pruning trees of two-person zero-sum games like chess is the alpha-beta algorithm."
If the values of the chess game play dispositions of win, draw, and loss are assigned 1, 0, and -1 respectively, then chess is a zero-sum game. If a single random bit is used to determine which player moves first, chess is symmetric. The various machine players in the winner's circle from 1978 to 2017 that used alpha-beta to achieve their victory confirms.
References
An analysis of alpha-beta pruning, DE Knuth, RW Moore, Artificial intelligence, 1975
An improvement of the Scout tree-search algorithm, A Reinefeld, ICCA Journal, 1983
answered Dec 30, 2018 at 2:46