Answers.Body: <p>Nice question!</p>
  
  <p>I think there are a couple of issues at work here.</p>
  
  <blockquote>
    <p>Is the historical weakness of GOFAI in relation to non-trivial
    combinatorial games partly a function of the structure of the games
    studied, where game states and token values cannot be precisely
    quantified?</p>
  </blockquote>
  
  <p>I think the short answer is <em>yes</em>. The real issue is in the last part:</p>
  
  <blockquote>
    <p>token values cannot be precisely quantified</p>
  </blockquote>
  
  <p>The most successful GOFAI approaches to these games were all some variation on A* search, combining combinatorial search with some form of <em>heuristic function</em> that estimated the value of the pieces and their positions in any given state. Piece counting is probably a better heuristic than not counting anything at all, but it's still clearly incorrect, because a player with less material may still have an overwhelming positional advantage. Some heuristics can try to estimate this positional advantage as well however.</p>
  
  <p>The real problem that GOFAI encounters in these games is that positional advantage can be <em>emergent</em> in ways that require incredible heuristic power to detect. Checkers is a good example. In the 1990's, the <a href="https://webdocs.cs.ualberta.ca/~chinook/project/" rel="nofollow noreferrer">Chinook project</a> at the University of Alberta set out to solve it completely. Checkers is notable because it had the same world champion for more than 15 consecutive years, <a href="https://en.wikipedia.org/wiki/Marion_Tinsley" rel="nofollow noreferrer">Marion Tinsley</a>. Tinsley lost a total of 7 competitive matches over 40 years of play. This makes him an especially interesting person to examine when we look at combinatorial games. Figuring out how Tinsley plays can help us understand how human intelligence works in games like this. In the course of solving checkers, the researchers noted that Tinsley was making moves that required up to <em>42 move lookaheads</em> to reveal an advantage (See <a href="https://doi.org/10.1609/aimag.v17i1.1208" rel="nofollow noreferrer">Schaeffer et al.</a>, AI Magazine, Vol. 17, Issue 1).  </p>
  
  <p>This strongly suggests that Tinsley was <em>not</em> methodically considering each possible move. Instead, by his own admission, his thinking was guided by a combination of <em>memory</em> over his 40 year career (in one match against Chinook in 1992, he indicated he was trying to recall a sequence from a match 30 years prior when making a move (<a href="https://www.aaai.org/ojs/index.php/aimagazine/article/download/1040/958" rel="nofollow noreferrer">AI Magazine Volume 14, Number 2</a>); and of attentional heuristics (i.e. not thinking about every move sequence, and being able to reliably rule out parts of the search space without looking at them).</p>
  
  <p>The key is that for GOFAI to solve checkers without heuristics (i.e. to solve it exactly), required enormous amounts of computational power, because some moves yield positional advantages that require 40+ moves of followthrough. Even an incredibly simple game (branching factor of 2) would be hard under that constraint.</p>
  
  <p>In contrast though, self-play techniques like those pioneered in Backgammon with <a href="http://enzodesiage.com/wp-content/uploads/2017/08/tesauro-tdgammon-1995.pdf" rel="nofollow noreferrer">TD-Gammon</a> (Tesauro, Comm. of the ACM 1995) mimic the process through which Tinsley became so good: they play lots and lots of games, learn a good heuristic estimate of position and material value, and more importantly, can learn to <em>remember</em> odd circumstances that require careful play. TD-Gammon achieved worldclass play despite only explicitly looking 2 moves ahead. GOFAI search techniques weren't even close despite searching much more deeply.</p>
  
  <p>Modern research on <a href="https://www.nature.com/articles/d41586-018-03067-x" rel="nofollow noreferrer">attention</a> could salvage the GOFAI approach however. If you can learn to tell what's important, you might be able to get a lot more value out of deeper lookaheads. This seems even closer to how Tinsley played: great ability to estimate value was used to guide an explicit analysis of a specific chain of moves.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-16T23:08:10.730Z
Answers.Text: Thanks for this answer, and the TD-Gammon link in particular!  *(There's a nice little writeup on it in Matthew Lai's [Giraffe Chess](https://arxiv.org/pdf/1509.01549.pdf) paper for those interested.)*
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-12T12:03:23.320Z
Answers.LastActivityDate: 2018-09-12T12:03:23.320Z
Answers.UserDisplayName: John Doucette
Body: <p>I was recently perusing the paper <a href="https://researcher.watson.ibm.com/researcher/files/us-beygel/samuel-checkers.pdf" rel="nofollow noreferrer"><em>Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress</em> (A.L. Samuel, 1967)</a>, which is interesting historically.</p>
  
  <p>I was looking at this figure, which involved Alpha-Beta pruning.</p>
  
  <p><a href="https://i.sstatic.net/qT5oL.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qT5oL.png" alt="enter image description here"></a> </p>
  
  <p>It occurred to me that the types of non-trivial, non-chance, perfect information, zero-sum, sequential, partisan games utilized (Chess, Checkers, Go) involve game states that cannot be precisely quantified. For instance, there is no way to ascribe an objective value to a piece in Chess, or any given board state.  In some sense, the assignment of values is arbitrary, consisting of estimates.</p>
  
  <p>The combinatorial games I'm working on are forms of <a href="http://mbranegame.com/tutorial/" rel="nofollow noreferrer">partisan Sudoku</a>, which are bidding/scoring (economic) games involving territory control.  In these models, any given board state produces an array of ratios allowing precise quantification of player status. Token values and positions can be precisely quantified.  </p>
  
  <p>This project involves a consumer product, and the approach we're taking currently is to utilize a series of agents of increasing sophistication to provide different levels challenge for human players.  These agents also reflect what is known as a "<a href="http://julian.togelius.com/Lantz2017Depth.pdf" rel="nofollow noreferrer">strategy ladder</a>".   </p>
  
  <p>Reflex Agents <em>(beginner)</em> <br>
  Model-based Reflex Agents <em>(intermediate)</em> <br>
  Model-based Utility Agents <em>(advanced)</em></p>
  
  <p><em>Goals may also be incorporated to these agents such as desired margin of victory (regional outcome ratios) which will likely have an effect on performance in that narrower margins of victory appear to entail less risk.</em></p>
  
  <p>The "respectably weak" vs. human performance of the first generation of reflex agents suggests that strong GOFAI might be possible. (The branching factors are extreme in the early and mid-game due to the factorial nature of the models, but initial calculations suggest that even a naive minimax lookahead will be able to look farther more effectively than humans.) Alpha-Beta pruning in partisan Sudoku, even sans a learning algorithm, should provide greater utility than in previous combinatorial game models where the values are estimates. </p>
  
  <ul>
  <li><strong>Is the historical weakness of GOFAI in relation to non-trivial combinatorial games partly a function of the structure of the games studied, where game states and token values cannot be precisely quantified?</strong></li>
  </ul>
  
  <p><strong>Looking for any papers that might comment on this subject, research into combinatorial games where precise quantification is possible, and thoughts in general.</strong>  </p>
  
  <p>I'm trying to determine if it might be worth attempting to develop a strong GOFAI for these models prior to moving up the ladder to learning algorithms, and, if such a result would have research value.  </p>
  
  <p>There would definitely be commercial value in that strong GOFAI with no long-term memory would allow minimal local file size for the apps, which must run on lowest-common-denominator smartphones with no assumption of connectivity.  </p>
  
  <p><em>PS- My previous work on this has involved defining the core heuristics that emerge from the structure of the models, and I'm slowly dipping my toes into the look ahead pool.  Please don't hesitate to let me know if I've made any incorrect assumptions.</em></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-31T17:37:56.107Z
Comments.Text: Regarding weakness or strength of GOFAI, read [Jacques Pitrat's books](https://en.wikipedia.org/wiki/Jacques_Pitrat) and see [RefPerSys](http://refpersys.org/).
Comments.UserDisplayName: Basile Starynkevitch
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-12T08:37:42.387Z
Comments.Text: I'm wondering about these "precisely quantifiable game states"... are these terminal game states? If so, that's no different from games like chess/go. If they're not terminal... are they really "precisely quantifiable"? Can there not be subsequent actions that change the value? If a game state is not terminal, it's game-theoretic value is normally defined in terms of game-theoretic values of successor states.
Comments.UserDisplayName: Dennis Soemers
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-12T08:59:22.530Z
Comments.Text: Precise quantification is possible *theoretically* for game states in chess and go. It would consist of -1, 0, 1 labels for each game state, referring to eventual lose, win, draw when playing *perfectly* versus another perfect-playing agent. Agents like AlphaGo estimate this function. I think you need to explain more about what you mean by *quantifying* a game state - from what I can tell, this is something to do with bidding values and a scoring system related to that, that is within your game?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-16T23:18:14.577Z
Comments.Text: @DennisSoemers This helps to clarify.  Not necessarily terminal values. Here I'm thinking just of a given present state, without regard to future states.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-16T23:25:02.790Z
Comments.Text: @NeilSlater thanks for your comments.  I'm going to think on it and look to edit the question to include what I mean by quantification.  (In these forms of partisan sudoku, the elements confer points in the regions of their placement. You can look at any given board state and determine the regional score as a ratio.  In the two player game with 9 regions, this can range from 0/9 to 9/0.)  The bidding element involves a more advanced mechanic which introduces regional stability based on the disparity between players' points-in-region, used to order a endgame cascade that determines the outcome.
Comments.UserDisplayName: DukeZhou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-09-16T23:31:45.657Z
Comments.Text: @NeilSlater The endgame cascade can cause regions to flip between players, changing the controlling player.  When that happens, opposing elements defect. (Elements can influence neighboring regions, and defection can alter the deltas in those regions.) This renders any given element placement a bid, because the placing player may not ultimately control an element they place. But the AIs can run this cascade from any give state to discern its actual status as opposed to the apparent status.
Comments.UserDisplayName: DukeZhou
Tags: <game-ai><alpha-beta-pruning><symbolic-ai><combinatorial-games>
Title: Historical weakness of GOFAI in relation to partisan combinatorial games?
UserDisplayName: DukeZhou
ThreadText: # Historical weakness of GOFAI in relation to partisan combinatorial games?
  
  (Asked by: username_0 on 2018-09-11)
  
  I was recently perusing the paper [*Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress* (A.L. Samuel, 1967)](https://researcher.watson.ibm.com/researcher/files/us-beygel/samuel-checkers.pdf), which is interesting historically.
  
  I was looking at this figure, which involved Alpha-Beta pruning.
  
  [![enter image description here](https://i.sstatic.net/qT5oL.png)](https://i.sstatic.net/qT5oL.png)
  
  It occurred to me that the types of non-trivial, non-chance, perfect information, zero-sum, sequential, partisan games utilized (Chess, Checkers, Go) involve game states that cannot be precisely quantified. For instance, there is no way to ascribe an objective value to a piece in Chess, or any given board state. In some sense, the assignment of values is arbitrary, consisting of estimates.
  
  The combinatorial games I'm working on are forms of [partisan Sudoku](http://mbranegame.com/tutorial/), which are bidding/scoring (economic) games involving territory control. In these models, any given board state produces an array of ratios allowing precise quantification of player status. Token values and positions can be precisely quantified.
  
  This project involves a consumer product, and the approach we're taking currently is to utilize a series of agents of increasing sophistication to provide different levels challenge for human players. These agents also reflect what is known as a "[strategy ladder](http://julian.togelius.com/Lantz2017Depth.pdf)".
  
  Reflex Agents *(beginner)*   
  Model-based Reflex Agents *(intermediate)*   
  Model-based Utility Agents *(advanced)*
  
  *Goals may also be incorporated to these agents such as desired margin of victory (regional outcome ratios) which will likely have an effect on performance in that narrower margins of victory appear to entail less risk.*
  
  The "respectably weak" vs. human performance of the first generation of reflex agents suggests that strong GOFAI might be possible. (The branching factors are extreme in the early and mid-game due to the factorial nature of the models, but initial calculations suggest that even a naive minimax lookahead will be able to look farther more effectively than humans.) Alpha-Beta pruning in partisan Sudoku, even sans a learning algorithm, should provide greater utility than in previous combinatorial game models where the values are estimates.
  
  * **Is the historical weakness of GOFAI in relation to non-trivial combinatorial games partly a function of the structure of the games studied, where game states and token values cannot be precisely quantified?**
  
  **Looking for any papers that might comment on this subject, research into combinatorial games where precise quantification is possible, and thoughts in general.**
  
  I'm trying to determine if it might be worth attempting to develop a strong GOFAI for these models prior to moving up the ladder to learning algorithms, and, if such a result would have research value.
  
  There would definitely be commercial value in that strong GOFAI with no long-term memory would allow minimal local file size for the apps, which must run on lowest-common-denominator smartphones with no assumption of connectivity.
  
  *PS- My previous work on this has involved defining the core heuristics that emerge from the structure of the models, and I'm slowly dipping my toes into the look ahead pool. Please don't hesitate to let me know if I've made any incorrect assumptions.*
  
  **Tags:** game-ai, alpha-beta-pruning, symbolic-ai, combinatorial-games
  > **Comments:**
  > **username_2**: I'm wondering about these "precisely quantifiable game states"... are these terminal game states? If so, that's no different from games like chess/go. If they're not terminal... are they really "precisely quantifiable"? Can there not be subsequent actions that change the value? If a game state is not terminal, it's game-theoretic value is normally defined in terms of game-theoretic values of successor states.  
  > **username_3**: Precise quantification is possible *theoretically* for game states in chess and go. It would consist of -1, 0, 1 labels for each game state, referring to eventual lose, win, draw when playing *perfectly* versus another perfect-playing agent. Agents like AlphaGo estimate this function. I think you need to explain more about what you mean by *quantifying* a game state - from what I can tell, this is something to do with bidding values and a scoring system related to that, that is within your game?  
  > **username_0**: @DennisSoemers This helps to clarify.  Not necessarily terminal values. Here I'm thinking just of a given present state, without regard to future states.  
  > **username_0**: @NeilSlater thanks for your comments.  I'm going to think on it and look to edit the question to include what I mean by quantification.  (In these forms of partisan sudoku, the elements confer points in the regions of their placement. You can look at any given board state and determine the regional score as a ratio.  In the two player game with 9 regions, this can range from 0/9 to 9/0.)  The bidding element involves a more advanced mechanic which introduces regional stability based on the disparity between players' points-in-region, used to order a endgame cascade that determines the outcome.  
  > **username_0**: @NeilSlater The endgame cascade can cause regions to flip between players, changing the controlling player.  When that happens, opposing elements defect. (Elements can influence neighboring regions, and defection can alter the deltas in those regions.) This renders any given element placement a bid, because the placing player may not ultimately control an element they place. But the AIs can run this cascade from any give state to discern its actual status as opposed to the apparent status.  
  > **username_1**: Regarding weakness or strength of GOFAI, read [Jacques Pitrat's books](https://en.wikipedia.org/wiki/Jacques_Pitrat) and see [RefPerSys](http://refpersys.org/).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2018-09-12. Score: 2
  
  Nice question!
  
  I think there are a couple of issues at work here.
  
  > Is the historical weakness of GOFAI in relation to non-trivial
  > combinatorial games partly a function of the structure of the games
  > studied, where game states and token values cannot be precisely
  > quantified?
  
  I think the short answer is *yes*. The real issue is in the last part:
  
  > token values cannot be precisely quantified
  
  The most successful GOFAI approaches to these games were all some variation on A\* search, combining combinatorial search with some form of *heuristic function* that estimated the value of the pieces and their positions in any given state. Piece counting is probably a better heuristic than not counting anything at all, but it's still clearly incorrect, because a player with less material may still have an overwhelming positional advantage. Some heuristics can try to estimate this positional advantage as well however.
  
  The real problem that GOFAI encounters in these games is that positional advantage can be *emergent* in ways that require incredible heuristic power to detect. Checkers is a good example. In the 1990's, the [Chinook project](https://webdocs.cs.ualberta.ca/~chinook/project/) at the University of Alberta set out to solve it completely. Checkers is notable because it had the same world champion for more than 15 consecutive years, [Marion Tinsley](https://en.wikipedia.org/wiki/Marion_Tinsley). Tinsley lost a total of 7 competitive matches over 40 years of play. This makes him an especially interesting person to examine when we look at combinatorial games. Figuring out how Tinsley plays can help us understand how human intelligence works in games like this. In the course of solving checkers, the researchers noted that Tinsley was making moves that required up to *42 move lookaheads* to reveal an advantage (See [Schaeffer et al.](https://doi.org/10.1609/aimag.v17i1.1208), AI Magazine, Vol. 17, Issue 1).
  
  This strongly suggests that Tinsley was *not* methodically considering each possible move. Instead, by his own admission, his thinking was guided by a combination of *memory* over his 40 year career (in one match against Chinook in 1992, he indicated he was trying to recall a sequence from a match 30 years prior when making a move ([AI Magazine Volume 14, Number 2](https://www.aaai.org/ojs/index.php/aimagazine/article/download/1040/958)); and of attentional heuristics (i.e. not thinking about every move sequence, and being able to reliably rule out parts of the search space without looking at them).
  
  The key is that for GOFAI to solve checkers without heuristics (i.e. to solve it exactly), required enormous amounts of computational power, because some moves yield positional advantages that require 40+ moves of followthrough. Even an incredibly simple game (branching factor of 2) would be hard under that constraint.
  
  In contrast though, self-play techniques like those pioneered in Backgammon with [TD-Gammon](http://enzodesiage.com/wp-content/uploads/2017/08/tesauro-tdgammon-1995.pdf) (Tesauro, Comm. of the ACM 1995) mimic the process through which Tinsley became so good: they play lots and lots of games, learn a good heuristic estimate of position and material value, and more importantly, can learn to *remember* odd circumstances that require careful play. TD-Gammon achieved worldclass play despite only explicitly looking 2 moves ahead. GOFAI search techniques weren't even close despite searching much more deeply.
  
  Modern research on [attention](https://www.nature.com/articles/d41586-018-03067-x) could salvage the GOFAI approach however. If you can learn to tell what's important, you might be able to get a lot more value out of deeper lookaheads. This seems even closer to how Tinsley played: great ability to estimate value was used to guide an explicit analysis of a specific chain of moves.
  
  > **Comments:**
  > **username_0**: Thanks for this answer, and the TD-Gammon link in particular!  *(There's a nice little writeup on it in Matthew Lai's [Giraffe Chess](https://arxiv.org/pdf/1509.01549.pdf) paper for those interested.)*  
  
  ---
  
  