September 11 | Explaining AI Through Games

Please read BEFORE CLASS “Checkers is Solved” (Schaeffer et al., 2007). I am able to access this when I am on the campus internet. Otherwise, it is behind a paywall.

Much of today’s class will be focused on Symbolic, Logic-Based, or Classic AI. This was the assumption that you could represent things in a higher-level, symbolic or human-readable, format and attack problems that way. It led to many advances in AI, particularly search.

Here’s a python notebook explaining some of these algorithms using tic-tac-toe.

Complexity for some common games:

Checkers Arthur Samuel. 1959. Alpha-Beta Pruning. 10^40 - 10^50 range for complexity. Solved 2007
Chess 10^120 (Shannon number) was published in 1950. Yes, the same Shannon who we talked about for WORDLE last week. (Shannon, 1950)
Connect-4. Solved independently 2 weeks apart in 1988 (James Allen 2008; (Allis, 1988) ) . In 2008, it was shown to have 4,531,985,219,092 reachable positions (70,728,639,995,483 had been estimated) (Edelkamp & Kissmann, 2008). The starting player can win.
Othello 10^58. Solved in 2023 (Takizawa, 2023)
Atoms in the Universe 10^80 (very rough approximation)
Tic-tac-toe 10^5. 9! 362,880

Chess was one of the first games to really inspire people when a computer solved it. Gary Kasparov is one of the best chess players ever. He held the highest FIDE ranking for decades. In 1997 (after having previously beaten earlier iterations of the machine, he lost to an IBM computer called Deep Bleu. He even had a Pepsi ad

A Note on Compute

You have probably heard of Moore’s law. Essentially, the number of transitors on a microchip roughly doubles every two years. It is tough to think about exponentials as a human. What does this mean exactly? DeepBlue had an actual 8x8 circuit to mimic a board that was custom designed. It had multiple of these strung together. In 1997, DeepBlue was the 259th most powerful super computer at 11.38 GFLOPS. Here are some other FLOP statistics:

Apollo 11 Guidance Computer 12,250 FLOPS in 1969
CRAY-2 Supercomputer was the fastest machine in 1985 with 1,900,000,000 FLOPS
DeepBlue in 1997 had 11,380,000,000
iPhone today has 2,000,000,000,000 FLOPS capabillities

References

2023

Othello is solved

Hiroki Takizawa

arXiv preprint arXiv:2310.19387, 2023

Bib

@article{takizawa2023othello,
  title = {Othello is solved},
  author = {Takizawa, Hiroki},
  journal = {arXiv preprint arXiv:2310.19387},
  year = {2023},
  url = {https://arxiv.org/abs/2310.19387}
}

2008

Symbolic classification of general two-player games

Stefan Edelkamp and Peter Kissmann

In Annual Conference on Artificial Intelligence, 2008

Bib

@inproceedings{edelkamp2008symbolic,
  title = {Symbolic classification of general two-player games},
  author = {Edelkamp, Stefan and Kissmann, Peter},
  booktitle = {Annual Conference on Artificial Intelligence},
  pages = {185--192},
  year = {2008},
  organization = {Springer},
  url = {https://link.springer.com/chapter/10.1007/978-3-540-85845-4_23}
}

2007

Checkers is solved

Jonathan Schaeffer, Neil Burch, Yngvi Bjornsson, and 5 more authors

science, 2007

Bib

@article{schaeffer2007checkers,
  title = {Checkers is solved},
  author = {Schaeffer, Jonathan and Burch, Neil and Bjornsson, Yngvi and Kishimoto, Akihiro and Muller, Martin and Lake, Robert and Lu, Paul and Sutphen, Steve},
  journal = {science},
  volume = {317},
  number = {5844},
  pages = {1518--1522},
  year = {2007},
  publisher = {American Association for the Advancement of Science},
  url = {https://www.science.org/doi/pdf/10.1126/science.1144079}
}

1988

A knowledge-based approach of connect-four

Louis Victor Allis

International Computer Games Association, 1988

Bib PDF

@article{allis1988knowledge,
  title = {A knowledge-based approach of connect-four},
  author = {Allis, Louis Victor},
  journal = {International Computer Games Association},
  year = {1988},
  url = {https://cris.maastrichtuniversity.nl/en/publications/searching-for-solutions-in-games-and-artificial-intelligence},
}

1950

XXII. Programming a computer for playing chess

Claude E Shannon

The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 1950

Bib

@article{shannon1950xxii,
  title = {XXII. Programming a computer for playing chess},
  author = {Shannon, Claude E},
  journal = {The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science},
  volume = {41},
  number = {314},
  pages = {256--275},
  year = {1950},
  publisher = {Taylor \& Francis},
  url = {https://www.tandfonline.com/doi/pdf/10.1080/14786445008521796}
}