1
$\begingroup$

I was recently perusing the paper Some Studies in Machine Learning Using the Game of Checkers II--Recent Progress (A.L. Samuel, 1967), which is interesting historically.

I was looking at this figure, which involved Alpha-Beta pruning.

enter image description here

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, 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".

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Dennis Soemers Sep 12 '18 at 8:37
  • 1
    $\begingroup$ 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? $\endgroup$ – Neil Slater Sep 12 '18 at 8:59
  • $\begingroup$ @DennisSoemers This helps to clarify. Not necessarily terminal values. Here I'm thinking just of a given present state, without regard to future states. $\endgroup$ – DukeZhou Sep 16 '18 at 23:18
  • $\begingroup$ @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. $\endgroup$ – DukeZhou Sep 16 '18 at 23:25
  • $\begingroup$ @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. $\endgroup$ – DukeZhou Sep 16 '18 at 23:31
2
$\begingroup$

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 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. 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., 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); 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 (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 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.

$\endgroup$
  • 1
    $\begingroup$ 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 paper for those interested.) $\endgroup$ – DukeZhou Sep 16 '18 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.