{"id":2011,"date":"2024-07-01T00:01:57","date_gmt":"2024-07-01T04:01:57","guid":{"rendered":"https:\/\/mathvoices.ams.org\/featurecolumn\/?p=2011"},"modified":"2024-07-15T11:57:48","modified_gmt":"2024-07-15T15:57:48","slug":"looking-ahead","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2024\/07\/01\/looking-ahead\/","title":{"rendered":"Looking ahead"},"content":{"rendered":"<p><span id=\"pullQuote\"><em>Tic-tac-toe is a very simple game, which even humans can figure out completely by using elementary reasoning, and yet a computer first approaching it would face these huge numbers&#8230;<\/em><\/span><\/p>\n<h1 class=\"headlineText\">Looking ahead<\/h1>\n<p><b>Bill Casselman<br \/>\nUniversity of British Columbia<\/b><\/p>\n<h1>Looking ahead<\/h1>\n<blockquote><p>\n<em><br \/>\nThe question of whether the beginning position &#8230; is for one of the players<br \/>\nalready a winning position remains still open.  With its answer chess would of course<br \/>\nlose its status as a game.<br \/>\n<\/em><br \/>\n<br \/>&mdash;Ernst Zermelo, in his talk at the<br \/>\n1912 International<br \/>\nCongress of Mathematicians in Cambridge<\/td>\n<\/blockquote>\n<p>Recent interest in &#8216;Artificial Intelligence&#8217; has provoked me to<br \/>\nlook at the early days in which people attempted to<br \/>\nprogram computers to simulate Natural Intelligence,<br \/>\nand even to outdo humans at certain human<br \/>\nintellectual activities.  My original intention was to try<br \/>\nto understand what fundamental changes have taken place in the field&mdash;i.e., changes other<br \/>\nthan sheer enhancement of machine capability in speed and storage.<br \/>\nBut I became distracted by some rather technical questions,<br \/>\nand I wound up focussing on attempts to make<br \/>\ncomputers good&mdash;or at least competent&mdash;at games<br \/>\nlike checkers and chess.  <\/p>\n<p>\nThe basic strategy for both humans<br \/>\nand machines is to explore possible moves and counter-moves&mdash;requiring<br \/>\na look ahead at possible sequences of future play.<br \/>\nBut humans are able to restrict explorations<br \/>\nto moves that seem more plausible winners.<br \/>\nIn effect, they apply imagination and experience, perhaps<br \/>\ngeometrical intuition, to cut down wasted effort.  Computers did<br \/>\nnot have access to these.<br \/>\nInstead, they could explore a much wider range of options at high speed,<br \/>\nalthough perhaps spending a huge amount of time that a human<br \/>\nwould consider fruitless.<\/p>\n<p>\nExactly what kind of games am I going to consider?  I have two rather different models in mind&mdash;one is<br \/>\nchess, and the other is tic-tac-toe. But my discussion applies to any game meeting the following conditions.<\/p>\n<ul>\n<li>\nThere are two players, making moves alternately.  <\/p>\n<li>\n A game amounts to a sequence of <b>positions<\/b> $q_{0}, q_{1}, q_{2}, \\dots $, and a <b>move<\/b><br \/>\nmeans that the current position changes from $q_{i}$ to $q_{i+1}$,<br \/>\naccording to some specified rules of the game.  From each position only a finite<br \/>\nnumber of moves are allowed.<\/p>\n<li> A certain number of positions are <b>terminal<\/b>, and when one of these<br \/>\noccurs the game is over.  There are at least two<br \/>\nkinds of terminal positions&mdash;those in which one of the players wins.<\/p>\n<li>But now the two models differ. My &#8216;chess model&#8217;<br \/>\nwill be a modified version of chess in which<br \/>\nstalemates are checkmates, and a game can be played forever,<br \/>\nin which case it is considered a draw.<br \/>\nIn the other model, every game is of finite length.<br \/>\nIn this case, there is a new kind of termination, which is a draw after a finite number of moves.\n<\/ul>\n<\/p>\n<p>\nOne of the simplest games meeting these conditions is tic-tac-toe.<\/p>\n<ul>\n<li>\nA position is a display of $\\times$ and $\\circ$<br \/>\nin a $3 \\times 3$ matrix.  <\/p>\n<li>\nEach player is assigned either<br \/>\n$\\times$ or $\\circ$ as their mark, and a move by them<br \/>\namounts to their placing their mark in an empty<br \/>\nspot in the current matrix.  <\/p>\n<li>\nThe initial position is<br \/>\nan empty matrix.  <\/p>\n<li>\nThere are two<br \/>\nkinds of terminal positions:<\/p>\n<ul>\n<li> There are three $\\times$ or $\\circ$ in a line&mdash;horizontal, vertical or diagonal),<br \/>\nor<\/p>\n<li> there is no such triplet,<br \/>\nand the matrix is full.\n<\/li>\n<\/ul>\n<p>In the first case,<br \/>\nthe player whose marks make up the triplet wins.<br \/>\nThe second case is a draw.\n<\/ul>\n<\/p>\n<p>\nBy convention, the first player<br \/>\nto move is $\\times$.<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/moves.png?resize=515%2C68&#038;ssl=1\" alt=\"A sequence of moves in a tic-tac-toe game.\" width=\"515\" height=\"68\" class=\"aligncenter size-full wp-image-2017\" srcset=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/moves.png?w=515&amp;ssl=1 515w, https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/moves.png?resize=300%2C40&amp;ssl=1 300w, https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/moves.png?resize=465%2C61&amp;ssl=1 465w\" sizes=\"auto, (max-width: 515px) 100vw, 515px\" \/><\/div>\n<p><h2>The game tree<\/h2>\n<p>.  <\/p>\n<p>\nTo each of these games is associated a graph<br \/>\nwith oriented edges.<br \/>\nThe nodes are the initial<br \/>\nsequences of positions in a game with moves<br \/>\ndetermining the edges.  That is to say,<br \/>\na <em>position together with the route by which it came about.<\/em><\/p>\n<p>\nSuch a structure is called a <b>tree<\/b>: it has as root node<br \/>\nan initial position, and to every other node is associated a unique path<br \/>\nfrom that root.<\/p>\n<p>In tic-tac-toe there are $9$<br \/>\npossible initial positions after the first move,<br \/>\nand for each of these there are $8$ possible<br \/>\nimmediate sequels, etc.  Without taking the<br \/>\nterminal positions into consideration,<br \/>\nthere are therefore at most<\/p>\n<p>$$ 1 + 9 + 9 \\cdot 8 + 9 \\cdot 8 \\cdot 7 + \\cdots + 9! =<br \/>\n623,530 $$<\/p>\n<p>possible nodes in this graph.  By contrast,<br \/>\nthere are nine possible places in the $3 \\times 3$<br \/>\nmatrix.  It can be empty or contain one of the two<br \/>\nmarks $\\times$, $\\circ$  So there are<br \/>\n$3^{9} = 19,683$ possible positions.<br \/>\nTic-tac-toe is a very simple<br \/>\ngame, which even humans can figure out completely<br \/>\nby using elementary reasoning,<br \/>\nand yet a computer first approaching it would face these huge<br \/>\nnumbers.  As I have said, computers generally replace<br \/>\nintuition and experience by brute force.  But then it takes very little<br \/>\neffort for a machine to scan through the entire game tree,<br \/>\nwhereas for a human it would be a formidable task.<\/p>\n<p>\nAn initial fragment of the game tree is illustrated below:<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt-graph.png?resize=600%2C556&#038;ssl=1\" alt=\"A portion of the game tree showing some of the possibilities in the first five moves of a tic-tac-toe game.\" width=\"600\" height=\"556\" class=\"aligncenter size-full wp-image-2024\" srcset=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt-graph.png?w=600&amp;ssl=1 600w, https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt-graph.png?resize=300%2C278&amp;ssl=1 300w, https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt-graph.png?resize=465%2C431&amp;ssl=1 465w, https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt-graph.png?resize=540%2C500&amp;ssl=1 540w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/div>\n<p>It suffices to exhibit only a matrix, since the path<br \/>\nleading to it is determined.<\/p>\n<h2>Forcing<\/h2>\n<p>What does a computer do with the game tree?<br \/>\nWell, there is a remarkable ideal.<\/p>\n<p>\nThe basic idea in many games is to <b>force<\/b> an opponent&#8217;s moves.<br \/>\nWhat does it mean to force a win?  It means that a player<br \/>\nhas a strategy in mind that tells them how to respond to <em>every<\/em> move by an opponent<br \/>\nin such a way that the eventual outcome is a victory for them.<\/p>\n<p>\nThis is familiar in <a href=\"https:\/\/www.chesspuzzles.com\/\">chess<br \/>\nproblems<\/a>, usually<br \/>\nin which one is presented with a board populated by a small<br \/>\nnumber of pieces, and asked to find a sequence of moves by, say, White,<br \/>\nleading necessarily to checkmate in<br \/>\nsome given number of moves.  Tic-tac-toe also offers similar<br \/>\nphenomena, of a more trival nature.  The position<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/force.png?resize=61%2C61&#038;ssl=1\" alt=\"A tic-tac-toe board with X in the center and O above it\" width=\"61\" height=\"61\" class=\"aligncenter size-full wp-image-2015\" \/><\/div>\n<p>is very bad news for $\\circ$, since if they have placed themself<br \/>\nin that position there is no way<br \/>\nthey can escape losing.  This is something every<br \/>\nplayer realizes very soon.  It takes a lot more work to verify<br \/>\nthoroughly that the position<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/draw.png?resize=61%2C61&#038;ssl=1\" alt=\"A tic-tac-toe board with X in the center and O in the upper left-hand corner\" width=\"61\" height=\"61\" class=\"aligncenter size-full wp-image-2014\" \/><\/div>\n<p>is a forced draw.<\/p>\n<p>\nThe basic idea originated in 1912, at the International Congress of Mathematicians<br \/>\nheld that year in Cambridge, England.<br \/>\nIn one of his two lectures at that Congress,<br \/>\nthe German mathematician Ernst Zermelo announced that<br \/>\nsomething like this held for all games like my chess model.<\/p>\n<p>\n<b>Zermelo&#8217;s Theorem<\/b>.<br \/>\n<em>If a game satisfies my conditions on the chess model,<br \/>\n then exactly one of three possibilities holds:<br \/>\n(1) The first player can force a win,<br \/>\n(2) the second player can force a win,<br \/>\nor (3) either player can force a draw<br \/>\nin the sense that they can force the other player to<br \/>\nkeep on going.<\/em><\/p>\n<p>\nThis is true even for<br \/>\nreally complicated games like chess, so in principle nobody ever need<br \/>\nplay a game&mdash;its outcome, at least in principle, is predetermined<br \/>\nas soon as White and Black have been decided.<\/p>\n<p>\nZermelo&#8217;s proof of his theorem<br \/>\nrelied on subtle if elementary reasoning.<br \/>\nIt is made to look like a kind of tautology&mdash;with<br \/>\n<em>win\/lose\/draw<\/em> looking somewhat like the dichotomy <em>true\/false<\/em>.<br \/>\nUnfortunately there were some flaws<br \/>\n in his approach, as was pointed out<br \/>\na dozen or so years later by the Hungarian<br \/>\nmathematician D&eacute;nes K&ouml;nig, who fixed<br \/>\nsome of them (and in doing so contributed one of my favourite<br \/>\nresults in the theory of infinite graphs, as we shall see later).<br \/>\n  A year later, his compatriot L&aacute;zl&oacute; Kalm&aacute;r fixed everything.<br \/>\nZermelo&#8217;s errors lay mostly in how he handled<br \/>\nthe combinatorics of infinite games, and both D&eacute;nes K&ouml;nig<br \/>\nand L&aacute;zl&oacute; Kalm&aacute;r introduced some subtle and even profound<br \/>\nways to deal with this.<\/p>\n<p>In fact, D&eacute;nes K&ouml;nig and L&aacute;zl&oacute; Kalm&aacute;r proved significantly<br \/>\nmore general versions of &#8216;Zermelo&#8217;s Theorem&#8217;.<br \/>\nIn particular, they extended it to cover<br \/>\nany games that must end in a finite number of moves.<br \/>\nThey did not, however, give any indication of<br \/>\npractical matters.  In principle, one ought to be<br \/>\nable to look at the rules of a game and announce<br \/>\na criterion for the game&#8217;s output.  In fact, one can<br \/>\nindeed write a program that will do that.<br \/>\nBut, as we have seen suggested by tic-tac-toe, the program<br \/>\nmight take a very, very long time.<\/p>\n<p>\nInstead, the arguments of Zermelo<br \/>\nand the Hungarians apply very elementary logic.<\/p>\n<p><\/em><\/p>\n<p><h2>Evaluation<\/h2>\n<\/p>\n<p>Practical implementation of Zermelo&#8217;s Theorem<br \/>\nwas first brought up in the <a href=\"#vonNeumann\">classic book<\/a><br \/>\non game theory by von Neumann and Morgenstern.<\/p>\n<p>\nThe algorithm of von Neumann and Morgenstern, as modified to<br \/>\nplay real games, searches as many sequences of future moves as possible,<br \/>\ntrying to find the &#8216;best&#8217; one.  Ideally, in view of<br \/>\nZermelo&#8217;s Theorem it would in fact explore <em>all<\/em><br \/>\noptions, and choose as its next move that<br \/>\nwhich leads to the truly best outcome.<br \/>\nOf course for serious games, this is impossible,<br \/>\nsince the number of options grows<br \/>\nexponentially with the depth of the search.<br \/>\nReal game-playing programs, starting with Arthur<br \/>\nSamuel&#8217;s checkers program, replace &#8216;best&#8217; by<br \/>\nan estimate of the worth of various positions.<br \/>\nFor example, in checkers one might use the difference in the number of<br \/>\nplayers&#8217; pieces remaining on the board. That is to say,<br \/>\nthe computer assigns a <b>value<\/b> to each<br \/>\noutcome it unpacks, and chooses an optimal path<br \/>\nbased on that.  <\/p>\n<p>\nForget about approximate values.<br \/>\nHow are the true values of arbitrary positions&mdash;equivalently, nodes&mdash;found<br \/>\nin a finite game?<br \/>\nThis was answered by von Neumann and Morgenstern.<br \/>\nFirst of all, to each terminal position is assigned a value,<br \/>\nsay to the first player a $1$ if they win,<br \/>\na $-1$ if they lose, and $0$ if the outcome is a draw.<\/p>\n<p>\nWe now want to assign a value to every node in the game tree.<br \/>\nFirst of all, define the <b>terminal distance<\/b><br \/>\nof a node of the game tree to be<br \/>\nthe maximum number of edges in the tree to a terminal<br \/>\nposition. <\/p>\n<p>\nFor example, the graph below is a fragment from the tic-tac-toe<br \/>\ngraph, listing all the successors of the top matrix.  <\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_end.png?resize=339%2C347&#038;ssl=1\" alt=\"A section of the tic-tac-toe tree showing several games ending with all squares filled.\" width=\"339\" height=\"347\" class=\"aligncenter size-full wp-image-2023\" srcset=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_end.png?w=339&amp;ssl=1 339w, https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_end.png?resize=293%2C300&amp;ssl=1 293w\" sizes=\"auto, (max-width: 339px) 100vw, 339px\" \/><\/div>\n<p>Here are the terminal distances:<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/td.png?resize=244%2C250&#038;ssl=1\" alt=\"A tree showing the scores corresponding to the previous tic-tac-toe positions.\" width=\"244\" height=\"250\" class=\"aligncenter size-full wp-image-2018\" \/><\/div>\n<p>The basic fact is this, whose proof is an easy exercise.<\/p>\n<p>\n<b>Lemma.<\/b>  <em>If a node has terminal distance $d$, then<br \/>\neach of its successor nodes has terminal distance at most $d-1$,<br \/>\nand at least one has terminal distance exactly $d-1$.<\/em><\/p>\n<p>\nThis allows us to compute easily the values of all nodes of<br \/>\nterminal distance $1$, then $2$, $3$ etc.<br \/>\nWe do this in the following fashion.  Suppose<br \/>\n$x$ is a node with successors $y_{1}$, $y_{2}$, &#8230; By the time<br \/>\nwe want to evaluate the node $x$, according to the Lemma, we shall<br \/>\nalready know the values of the $y_{i}$.<br \/>\nIf $x$ is the first player, we choose as the value $v(x)$ of $x$ the <em>maximum<\/em><br \/>\nvalue of the $v(y_{i})$, while if it is the second player&#8217;s turn<br \/>\nwe choose the <em>minimum<\/em>.<\/p>\n<p>\nBelow are the evaluations of the<br \/>\nterminal positions, followed by evaluations of positions of depth 1.<br \/>\nSquares are where the first player is to move.  The first player wants to move<br \/>\nso as to maximize values.  The second player wants to minimize them.<\/p>\n<div align=\"center\">\n<img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_1.png?resize=281%2C288&#038;ssl=1\" alt=\"Evaluations of some possible positions.\" width=\"281\" height=\"288\" class=\"aligncenter size-full wp-image-2019\" \/><br \/>\n<img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_2.png?resize=272%2C278&#038;ssl=1\" alt=\"Evaluations of possible further positions.\" width=\"272\" height=\"278\" class=\"aligncenter size-full wp-image-2020\" \/><\/div>\n<p>Here are the evaluations of positions of terminal distance 2 and 3 in the same example:<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_3.png?resize=272%2C278&#038;ssl=1\" alt=\"Tree with evaluations of positions.\" width=\"272\" height=\"278\" class=\"aligncenter size-full wp-image-2021\" \/><br \/>\n<img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_4.png?resize=272%2C278&#038;ssl=1\" alt=\"Tree with further evaluations of positions.\" width=\"272\" height=\"278\" class=\"aligncenter size-full wp-image-2022\" \/><\/div>\n<p>Here is a brief recursive routine in pseudocode to assign values:<\/p>\n<p><pre>\r\ndef v(n):\r\n    if n is terminal: \r\n        return 1,0,-1 according to the game rules \r\n    else: \r\n        s = x's descendants (of smaller terminal distance than x) \r\n        if x is the first player:\r\n            return the maximum value of v(y) for y in s\r\n        else:\r\n            return the minimum value of v(y) for y in s \r\n<\/pre>\n<h2>Strategies<\/h2>\n<p>What does this have to do with finding whether<br \/>\nany given positions is win, lose, or draw?<br \/>\nThe point is that finding the value of a node<br \/>\ngives you at the same time a best choice of move from that node.<br \/>\nAt the position taken by that move, the opponent<br \/>\nis also given a best move for them.  Etc.<br \/>\nIf $x$ is a node at which $\\times$ is to play,<br \/>\nthe best move will go from $x$ to $y$ if<br \/>\n$v(x) = v(y)$ is maximal among the successors of $x$;<br \/>\nand if $y$ is a node at which $\\circ$ is to play,<br \/>\nthe best move will go to a successor $x$ such that<br \/>\n$v(y) = v(x)$ is maximal among the successors $y$.<br \/>\nAn argument by mathematical induction<br \/>\nwill show that a path from $x$ following<br \/>\nthese moves will be a terminal node with the same value as $x$,<br \/>\nand that any move other than the optimal one<br \/>\ncannot result in a better final outcome.<\/p>\n<h2>Pruning<\/h2>\n<p>A full search for evaluations<br \/>\ntakes a great deal of time and, likely, memory space.<br \/>\nIt can be made much more efficiently by a technique<br \/>\ncalled <b>pruning<\/b>, which allows shorter searches.<br \/>\nThis is crucial for efficients searching.  I cannot explain it in<br \/>\ndetail, because it is a bit complicated, but I can point out<br \/>\nthat even in my example it can be applied.<\/p>\n<p>Suppose I am assigning values to the nodes in this diagram:<\/p>\n<div align=\"center\"><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/ttt_4.png?resize=272%2C278&#038;ssl=1\" alt=\"Tree with further evaluations of positions.\" width=\"272\" height=\"278\" class=\"aligncenter size-full wp-image-2022\" \/><\/div>\n<\/p>\n<p>The scan takes place from left to right.<br \/>\n When I evaluate the second node at level two,<br \/>\nI can stop looking right there, because I know that no subsequent node will<br \/>\nsurpass $1$ in value, and I am looking for a maximum.  There<br \/>\nis a second kind of pruning available when I meet the third node<br \/>\nat level three.  It has value $-1$.  Now I know that the true<br \/>\nvalue of its parent node is looking for a minimum<br \/>\nvalue among its successors.  That minimum will certainly be at most $-1$.<br \/>\nBut at the level two higher, we will be looking for a maximum.<br \/>\nI already have a maximum value of $1$, so I can stop<br \/>\nmy searching immediately.<\/p>\n<p>\nBut techniques for pruning make up another story.<\/p>\n<p><h2>More<\/h2>\n<\/p>\n<p>What exactly did  K&ouml;nig do?<br \/>\nHe formulated and proved something that achieved<br \/>\nsome fame, and now carries his name.<\/p>\n<p>\n<b>K&ouml;nig&#8217;s Lemma<\/b>.<em><br \/>\nSuppose we are given a tree with nodes $x$,<br \/>\nand for each node a finite list of succeeding nodes.<br \/>\nThen either the set of all nodes in the tree<br \/>\nis finite, or there exists an infinite sequence of successors $(x_{i})$ in the tree.<\/em><\/p>\n<p>\nComprehending this is like looking at one of those optical illusions<br \/>\nin which foreground shifts constantly to background&mdash;is it trivial, or not?<br \/>\nThe definitive answer is that it is not.<br \/>\nSome idea of its illusory power can be found in the discussion<br \/>\nin $\\S$ 2.3.4.3 of <a href=\"#knuth\">Knuth&#8217;s book<\/a>.<br \/>\nAnother illustration of its magic can be found in<br \/>\nan intriguing footnote on page 60 of von Neumann-Morgenstern.<\/p>\n<p>\nBut I can present right here one application.<br \/>\nSuppose we are given a game in which each node<br \/>\nhas a finite number of successors.  Then assuming only a finite number of moves at each stage,<br \/>\nand no infinite chains,<br \/>\n<a href=\"\">K&ouml;nig&#8217;s Lemma<\/a> then implies that there are only a finite<br \/>\nnumber of possible games.<\/p>\n<h2>Reading further<\/h2>\n<h3>Chess and checkers<\/h3>\n<ul>\n<li>\n<a id=\"shannon\"><br \/>\nClaude Shannon,<br \/>\n<b>Programming a computer for playing chess<\/b><\/a>,<br \/>\n<em>Philosophical Magazine<\/em> <b>41<\/b> (1950).<\/p>\n<p>\nThis is one of the first to introduce the subject.<\/p>\n<li>\n<a id=\"samuel\"><br \/>\nArthur Samuel,<br \/>\n<b>Some studies in<br \/>\nmachine learning using the game of checkers<\/b><\/a>. In the<br \/>\n<em>IBM Journal of Research and Development<\/em>.  Part I in volume <b>3<\/b> (1959) and part II in<br \/>\nvolume <b>11<\/b> (1967).<\/p>\n<p>\nSamuel wrote programs that played real checkers, and explained them in detail.<br \/>\nUnfotunately, they were never very good, and never made a convincing win against a human<br \/>\nopponent.<\/p>\n<\/ul>\n<h3>Technical articles<\/h3>\n<ul>\n<li>\n<p id=\"vonNeumann\">\nOskar Morgenstern and John von Neumann,<br \/>\n<b>The theory of games and economic behaviour<\/b>,<br \/>\nPrinceton University Press, 1953.<\/p>\n<li>\nUlrich Schwalbe and Paul Walker,<br \/>\n<b>Zermelo and the early history of game theory<\/b>,<br \/>\n<em> Games and Economic Behavior<\/em> <b>34<\/b>.<\/p>\n<p>\nThere are many accounts of what Zermelo,<br \/>\nK&ouml;nig, and Kalm&aacute;r did.  This the first that is both accurate and<br \/>\nthorough.  They point out many misconceptions in the literature,<br \/>\nsome rather astonishing.  As far as I can see<br \/>\n  the quantity of misconceptions in the meantime has only increased,<br \/>\nand they seem to far outnumber the accurate ones.<\/p>\n<li>\n<a href=\"https:\/\/en.wikipedia.org\/wiki\/Zermelo%27s_theorem_(game_theory)\">Wikipedia<br \/>\non Zermelo&#8217;s Theorem<\/a>.<\/p>\n<p>\nAs though to illustrate the observations of Schwalbe and Walker, this is<br \/>\na very inaccurate account. And refers to their article!<\/p>\n<li>\nHeinz-Dieter Ebbinghaus (in Cooperation with Volker Peckhaus),<br \/>\n<b><br \/>\nErnst Zermelo:<br \/>\nan approach to his life and work<\/b>,<br \/>\nSpringer, 2007.<\/p>\n<p>\nSection 3.4.1 contains an interesting account of Zermelo&#8217;s ICM lecture.<\/p>\n<li>\n<p id=\"knuth\"><\/a><br \/>\nDonald E. Knuth,<br \/>\n<b> Fundamental algorithms<\/b>, Addison-Wesley, Second edition 2003.<\/p>\n<\/ul>\n<h3>Even more technical articles<\/h3>\n<p>I must apologize for listing these here.<br \/>\nNot only are they in German, but they are not easy to read even for specialists.<br \/>\nNonetheless, I believe it is useful to have the links.<\/p>\n<ul>\n<li>\nErnst Zermelo,<br \/>\n<b>&Uuml;ber eine Anwendung der Mengenlehre auf der Theorie des Schachspiels,<\/b><br \/>\nProceedings of the 1912 <a href=\"https:\/\/www.mathunion.org\/icm\/proceedings\"><em>International Congress of Mathematicians<\/em><\/a><\/p>\n<p>\nThere is a valuable English translation `On an application of set theory in the theory of games of chess&#8217;<br \/>\nin an appendix to Schwalbe-Walker.<\/p>\n<li>\n<p id=\"konig\">\nD&eacute;nes K&ouml;nig,<br \/>\n<b>&Uuml;ber eine Schlussweise aus dem Endlichen ins Unendliche<\/b>,<br \/>\n<a href=\"http:\/\/pub.acta.hu\/acta\/showCustomerVolume.action?id=5143&amp;dataObjectType=volume&amp;noDataSet=true&amp;style=\">Acta Scientarium Mathematicarum (Szeged) 3 (1927) <\/a><\/p>\n<li>\n<p id=\"kalmar\">\nL&aacute;zl&oacute; Kalm&aacute;r,<br \/>\n<b>Zur Theorie der abstrakten Spielen<\/b>,<br \/>\n<a href=\"http:\/\/pub.acta.hu\/acta\/showCustomerVolume.action?id=5206&amp;dataObjectType=volume&amp;noDataSet=true&amp;style=\">Acta Scientarium Mathematicarum (Szeged) 4 (1928)<\/a><\/p>\n<\/ul>\n<ul>\n<h3>Pruning<\/h3>\n<li>\nDonald Knuth,<br \/>\n<b>An analysis of alpha-beta pruning<\/b>,<br \/>\n<em>Artificial Intelligence<\/em> <b> 6<\/b> (1975).<\/p>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Tic-tac-toe is a very simple game, which even humans can figure out completely by using elementary reasoning, and yet a computer first approaching it would face these huge numbers&#8230; Looking ahead Bill Casselman University of British Columbia Looking ahead The question of whether the beginning position &#8230; is for one<span class=\"more-link\"><a href=\"https:\/\/mathvoices.ams.org\/featurecolumn\/2024\/07\/01\/looking-ahead\/\">Read More &rarr;<\/a><\/span><\/p>\n","protected":false},"author":2,"featured_media":2037,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[147,8,137],"tags":[38,148,165],"class_list":["entry","author-uwhitcher","post-2011","post","type-post","status-publish","format-standard","has-post-thumbnail","category-147","category-bill-casselman","category-math-and-social-sciences","tag-chess","tag-game-theory","tag-tic-tac-toe"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2024\/07\/cropped-FC1380x500x2.png?fit=1380%2C288&ssl=1","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/2011","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/comments?post=2011"}],"version-history":[{"count":8,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/2011\/revisions"}],"predecessor-version":[{"id":2043,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/2011\/revisions\/2043"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media\/2037"}],"wp:attachment":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media?parent=2011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/categories?post=2011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/tags?post=2011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}