Artificial Intelligence Game Talk, March 13, 2019 (University of Alberta)

Introduction

· A Smart Move – AI and Strategy Games.

U of Alberta created the first Computing Science department in Canada in 1964.
It has a long tradition of research in AI (is rated 3^rd in the world in machine learning).
It has also led in the development of AI for strategy games. The results can be commercialized in non-game applications as well.
Among these are Checkers, Chess, Go and Poker,
The evening’s talks were by Jonathan Schaeffer (computer chess) and Ryan Hayward (the strategy game Hex).
Both are members of the U of A Games Research Group.
By the way, I work at the U of Alberta, but have no connection with either of these fellows, so I am not just plugging their books (though my son bought a paper copy of the chess book and I bought an ebook of the same, so there’s that).
Note also that this blog is based on my notes from the lecture, which I hope are error free, but I can’t guarantee that.

The History of the Game Hex (Ryan Hayward)

The University of Alberta has a Computer Hex Research Group – this talk was part of a book launch, for a book on Hex published by the speaker, Ryan Hayward, a U of Alberta faculty member.
Here’s a link: https://www.amazon.com/Hex-Story-Ryan-B-Hayward-ebook/dp/B07NC2776M
Hex (also known as Polygon) was developed during WW2, in occupied Denmark. It became very popular as a diversion for people in that context.\
Later, it spread to the math department of Princeton University, and thence to the rest of the world after 1957 or so.
It benefited from the cold war obsession with game theory and similar problems, related to the U.S.-U.S.S.R. nuclear standoff.
Its originator (Piet Hein), was a PhD student along with some very notable names in math and physics, of the earlier to mid 20^th century. The game has been associated with people such as Bohr and John Nash (who invented it, independently some years later).
Although he never finished his PhD, he was brilliant in many ways, including the invention of Hex and of the Soma Cube, which was popular in the 1970’s (build a cube from a collection of shapes).
Hex was motivated in part by Hein’s thinking about the 4-color problem in mathematics (minimum number of colors it takes to draw a map, with no bordering countries sharing a color). Many other deep mathematical theorems and principles are latent within the game.
An 11 by 11 board has a phenomenal number of possible legal positons, 10 to the 56^th power, about 10 billion times more than chess.
The game is played on a board made of hexagons (thus the name), where two armies facing each other across the board are attempting to join each other.
It can also be played as a pencil and paper game, rather like a very advanced game of X’s and O’s (aka tick-tack-toe).
The players try to get their armies to join up, while preventing the opponent’s armies from doing the same.
From a strategy point of view, the interesting thing about the game is that it cannot end in a draw, so a winning strategy is to continually block your opponent, and eventually win by doing that.
Like chess, there have been many “set-up” game puzzles, that people can ponder over (i.e. set up a situation, determine which player should ultimately win from that situation).
However, Claude Shannon developed an analog Hex playing machine in 1950. There are computer programs that are competitive with skilled human players.

The History of Computer Chess (Jonathan Schaeffer)

The speaker, Jonathan Schaeffer, also a faculty member at the U of Alberta, has had a long-term role in the development of computer chess games, as well as other computer games (he “solved” checkers).
This talk was also part of a book launch, for a book on the history of computer chess (“Man vs. Machine: Challenging Human Supremacy at Chess”). This is actually Schaeffer’s second book on the subject.
Here’s a link: https://www.amazon.com/Man-vs-Machine-Challenging-Supremacy-ebook/dp/B07KCM9SF7
The talk (and book) has a more historical than technical focus – i.e. history that is more people-oriented than algorithm-oriented.
Chess can be considered the “fruit fly” of computer games and strategy, in the same way that experimentation on Drosophila was foundational for modern genetic research.
Why is computer chess such a big deal?

o It established many milestones in development of artificial intelligence algorithms.

o It motivated many pioneering efforts in both programming and hardware development.

o It resulted in many new algorithms, that often had wider applications than the game itself, such as Machine Learning.

o “Search is Knowledge” – even apparently frivolous activities can lead to useful gains in knowledge and technology.

The dream of building a chess playing computer (or computer program) goes back at least to the 1950’s. At that time, the complexity of the situation was not yet realized (i.e. it was much harder than people expected).
However, the more general history of chess playing machines goes back even further than that.

o In the 1770’s, the “mechanical Turk” version was introduced, which was basically a scam. This machine actually hid a small person inside a cabinet, on which the chess board was built. A mechanical figure (dressed in robes, like an Ottoman would be expected to dress) was supposedly playing the game, though in reality, the person in the cabinet was the real player. This became a bit of a craze.

o Charles Babbage, Victorian inventor of the “analytical engine” worked on a version (or at least scoped one out), though the hardware of the day wasn’t up to standards needed for his inventions.

o In 1912, a very limited “chess playing machine” was developed.

o In 1948, Claude Shannon, one of the key figures in signal theory and computer development outlined some possible software solutions for chess.

o Alan Turing, another key figure in computer development (e.g. Enigma, the Turing Test) wrote a page on a computer algorithm for chess. He played a simulated game himself against the algorithm and lost.

What we now think of, when we think of computer chess, goes back to the late 1960’s, when Greenblatt developed a program that played at a very novice level.
By 1970, the program had been improved somewhat, at the University of Toronto. That institution has been “in the game” since then.
The first World Tournament was in 1974. A Russian program won that contest.
No doubt that sowed some Cold War panic, with a Soviet program winning the tournament. There would have been implications for Artificial Intelligence, military balance of power, and so forth (think of the movie “Colossus”).
Bobby Fischer (eccentric world champ) played an M.I.T. program in 1977 and won, three games to none.
Our book author, Jonathan Schaeffer, became active in his first computer chess tour in 1980.
By 1982, Ken Thompson wrote an important paper on computer chess strength. The main point of the paper was that chess program strength scales with speed, whether that is derived from more clever software or faster hardware. So, computer chess research tended to follow that route, after that.
The University of Alberta had a top playing program in 1983, ranked 2^nd in the world at that time.
By 1986, A “chess chip” was developed, that improved computer chess speed and that program and hardware now played at a weak Grandmaster level.
The U of Alberta’s program at that time, Phoenix, tied for 1^st in the world.
In 1987, the program “Deep Thought” came out, which also utilized new chip designs.
The 1989 World Computer Chess Championship was held in Edmonton, Canada, home of the University of Alberta. About that time, Jonathan Schaeffer switched his computer gaming research to checkers. He established that any game of checkers must eventually end (no stalemate), so in that sense “solved the game”. That took years of development as well as actual playing by the program against itself to establish that fact.
Getting back to chess, in 1989 Gary Kasparov (world champion) beat Deep Thought. But things were getting tougher all the time for Gary.
Deep Thought morphed into Deep Blue (i.e. IBM’s color) by 1996. Kasparov won that year, but by 4 games to 2.
However, in 1997, Kasparov lost 2 ½ games to 3 ½ games to Deep Blue.
By the early 2000s, computer programs had taken over. Humans never won another tournament after that (the last human victory was in 2005).
In terms of chess rating, the top computer programs are now rated at about 3500, whereas the top humans are at about 2800.

Panel Discussion in Computer Gaming and AI in General

· The talk ended with a panel discussion by Martin Mueller (Go), Jonathan Schaeffer (Chess and Checkers), Ryan Hayward (Hex) and Michael Burns (Gamebots).

The subject of the Reinforcement Learning came up, and programs such as AlphaGo were given as an example. It learns the rules, plays itself multiple times and quickly begins to excel. It was noted that a lot of the people that worked on AlphaGo had a University of Alberta connection (faculty, post-docs, PhD students, etc.), and Google has a partnership with the U of A. Many of the Monte Carlo search algorithms used for the purpose were developed at the U of A.
What about multi-player and cooperative games? The panel members said that there was work going on, in these areas, but basically there was a lot left to do. The best algorithms still have a lot of trouble in multi-player games when a group of expert humans work cooperatively against them.
How about games of chance, skill and deception, such as poker? Some versions of poker have been “solved”, but humans still have the edge in the more complex versions of the game.
There was also some discussion about whether these game developments have been used (or could be used) for wider areas of human interest such as economics, military strategy, politics and so forth. Obviously there is a lot of interest in this, but it is probably a long way off. Systems that involve a lot of actors are just intrinsically difficult to model Schaeffer seemed to think that concerns about “the singularity”, “Skynet goes on-line”, “Colossus” and related dystopian futures were overblown and unwarranted (that was my take on the responses, anyway).

Some related blogs of mine:

1) The Movie Colossus, the Book Superintelligence and Artificial Intelligence:

https://dodecahedronbooks.blogspot.com/2018/12/the-movie-colossus-book.html

The movie (about 1970) is about an AI taking control of the world, the book(about 201) is about the prospect of the same. Great movie, way ahead of its time.

2) U of A Lecture – Demystifying Artificial Intelligence- Part 1, History of AI: http://dodecahedronbooks.blogspot.ca/2018/03/u-of-lecture-demystifying-artificial.html

3) U of A Lecture – Demystifying Artificial Intelligence- Part 2, Varieties of AI: http://dodecahedronbooks.blogspot.ca/2018/03/u-of-lecture-demystifying-artificial_3.html

From a talk, also given at the University of Alberta, on the general subject of AI.

4) Computer vs Human in Go: http://dodecahedronbooks.blogspot.ca/2016/03/go-match-alphago-versus-lee-sedol.html #math #statistics #datascience #games #go #AI #kinde #kindlleunlimited

4) Computer vs Human in Go: http://dodecahedronbooks.blogspot.ca/2016/03/go-match-alphago-versus-lee-sedol.html

From a talk, also given at the University of Alberta, on the game between the best human and the program AlphaGo, for the championship of the very complex board game, Go.

Now I will plug a book or two:

If you want to get away from computer games and see the real world, you might want to consider a nice road trip, exploring the contrasts between Canada and the U.S.. If so, then “On the Road with Bronco Billy” is definitely your book.

Sit back and go on a ten day trucking trip in a big rig, through western North America, from Alberta to Texas, and back again. Explore the countryside, learn some trucking lingo, and observe the shifting cultural norms across this great continent. There's even some hockey playoff talk (Oilers-Denver and Oilers-Dallas), for those nostalgic for Canadian playoff representation.

It’s on Amazon (ebook), for a mere 99 cents (U.S.).

Amazon U.S.: http://www.amazon.com/gp/product/B00X2IRHSK

Amazon U.K.: http://www.amazon.co.uk/gp/product/B00X2IRHSK

Amazon Germany: http://www.amazon.de/gp/product/B00X2IRHSK

Amazon Canada: http://www.amazon.ca/gp/product/B00X2IRHSK

Or, if you want to continue contemplating strategic games, you could try “A Dark Horse”, which concerns the troubling run of good luck that a (fictional) horse player experiences, and his extraordinary opponent.

Also on Amazon (ebook), for 99 cents (U.S.).

Amazon U.S.: https://www.amazon.com/dp/B01M9BS3Y5

Amazon U.K.: https://www.amazon.co.uk/dp/B01M9BS3Y5

Amazon Germany: https://www.amazon.de/dp/B01M9BS3Y5

Amazon Canada: https://www.amazon.ca/dp/B01M9BS3Y5