Historical weakness of GOFAI in relation to partisan combinatorial games?

Question

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.

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.

Answer 1

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.