Games, Graphs, and Computers: How to Win Without Actually Cheating

May 6, 2008

Bridges. Credit: Xiong-GNU Free Documentation License.Speaker: Dr. Wayne Brehaut, Athabasca University (retired)

Date & Time: May 6, 2008, 7:00 p.m. to 9:00 p.m.

Location: Athabasca University Governing Council Chambers,
1 University Drive, Athabasca, Alberta.

Synopsis: Learn how to solve puzzles and win games without actually cheating! And how to win against someone who doesn't know the best strategy. Simple examples are puzzles where you want to find a path that covers each edge of a figure (graph) exactly once without raising your pencil (including the famous Seven Bridges of Konigsberg Puzzle) and games where players take turns choosing an edge of a graph--or adding a new edge--to form a path from one given point to another (such as Bridg-It, Slink, and Slither).

Even some puzzles and games that don't appear to have anything to do with graphs can be solved with their aid, and a perfect example is Instant Insanity, a puzzle of stacking coloured cubes! We'll see how to solve this game and get some practice.

Some of the simplest "pile of stones" games, such as Nim, that don't involve graphs--or may but don't need to--but just simple counting can teach us much about how to solve games. And they can also give us some insight into how computers operate! And we can program them so we can play them on a computer, and use a "graphical user interface" to make playing more interesting. (And to display hints on our winning next move! )

In addition to these Combinatorial Games, there's another whole class of games stdied in the subject known as "Game Theory"--which turns out to be more fun than its name suggests! We'll see some differences between these two categories of games, and learn some basic game theory so we can solve this more general type of game, such as whether it's best to always fight (hawk), or always run away (dove), or sometimes do one and sometimes the other.

Game Theory is also the basis for much analysis of cooperation and competition: in simple, fun games like tossing pennies; in economics and sociology (such as the "Nash Equilibrium" popularliuzed in the movie "A Perfect Mind"); in nature (such as evolution and "survival of the fittest", and questions such as whether it's best to always fight (hawk), or always run away (dove), or sometimes do one and sometimes the other); and in human conflict (war, which was one of the first main motives for developing the theory).

Science Outreach Athabasca - September 27, 2012

Bottom shadow