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.