Answers.Body: <p>If the game is not <a href="https://en.wikipedia.org/wiki/Sequential_game" rel="nofollow noreferrer">sequential</a>, 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 <a href="https://en.wikipedia.org/wiki/Combinatorial_game_theory" rel="nofollow noreferrer">combinatorial games</a>. </p>
  
  <p>(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.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-22T12:07:48.333Z
Answers.Text: 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.
Answers.UserDisplayName: Exprove
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-22T21:44:33.500Z
Answers.Text: @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.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-22T01:52:02.467Z
Answers.LastActivityDate: 2018-12-22T01:57:52.967Z
Answers.LastEditDate: 2018-12-22T01:57:52.967Z
Answers.UserDisplayName: DukeZhou
Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>These do not seem, <em>prima facie</em>, 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."</p>
  
  <p>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.</p>
  
  <p><strong>References</strong></p>
  
  <p><a href="https://www.ime.usp.br/~rbrito/docs/1-s2.0-0004370275900193-main.pdf" rel="nofollow noreferrer"><em>An analysis of alpha-beta pruning</em></a>, DE Knuth, RW Moore, Artificial intelligence, 1975</p>
  
  <p><a href="http://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf" rel="nofollow noreferrer"><em>An improvement of the Scout tree-search algorithm</em></a>, A Reinefeld, ICCA Journal, 1983</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-30T02:46:28.590Z
Answers.LastActivityDate: 2018-12-30T02:46:28.590Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>This question was asked in an AI exam. How would you answer such question?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-21T13:49:38.630Z
Comments.Text: 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.
Comments.UserDisplayName: Oliver Mason
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-22T01:35:00.467Z
Comments.Text: 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.)*
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-22T02:01:37.740Z
Comments.Text: @OliverMason I am thinking it is a trick question ;)
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-12-29T01:15:21.483Z
Comments.Text: 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.
Comments.UserDisplayName: DukeZhou
Tags: <game-ai><game-theory><alpha-beta-pruning>
Title: Can Alpha–Beta be used on symmetric zero sum games?
UserDisplayName: Exprove
ThreadText: # Can Alpha–Beta be used on symmetric zero sum games?
  
  (Asked by: username_0 on 2018-12-21)
  
  This question was asked in an AI exam. How would you answer such question?
  
  **Tags:** game-ai, game-theory, alpha-beta-pruning
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: 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.)*  
  > **username_2**: @username_1 I am thinking it is a trick question ;)  
  > **username_2**: 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.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2018-12-22. Score: 3
  
  If the game is not [sequential](https://en.wikipedia.org/wiki/Sequential_game), 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](https://en.wikipedia.org/wiki/Combinatorial_game_theory).
  
  (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.)
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_2**: @username_0 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.  
  
  ---
  
  ### Answer by username_3 on 2018-12-30. Score: 0
  
  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*](https://www.ime.usp.br/~rbrito/docs/1-s2.0-0004370275900193-main.pdf), DE Knuth, RW Moore, Artificial intelligence, 1975
  
  [*An improvement of the Scout tree-search algorithm*](http://www.top-5000.nl/ps/An%20improvement%20to%20the%20scout%20tree%20search%20algorithm.pdf), A Reinefeld, ICCA Journal, 1983
  
  
  ---
  
  