|
|
Milestone Year
1970
Combinatorial Game Theory
There are games where a winning strategy is very easy. But can a player in Chess have a simple (perfect) strategy such that he is guaranteed to win, no matter how his opponent plays? An Institute scientist was fascinated by the apparent complexity gap between easy and Chess-like games. He set out to bridge the gap by identifying the mathematical differences between the easy games and the seemingly hard ones, and attacking them separately in a divide and conquer fashion.
His was able to provide solutions of hitherto unsolved "in-between" games, and prove that Chess-like games are inherently complex ("Exptime-complete"). His study was pivotal to establshing the foundations of combinatorial game theory as a mathematically rigorous subject.