Next: On the ``Big" Questions Up: Chess Isn't Tough Enough: Previous: Checkmate to Debate to

# ``McNaught" and Infinite Games

Seeing as how there is insufficient space to set out all the mathematical niceties (they will have to wait for the full version of this paper), let's dive in and play an infinite game -- a game we call, in deference to some recent investigations carried out by Robert McNaughton, ``McNaught" [McNaughton, 1993]. McNaught isn't a game like chess, mind you: chess, as we've noted, is after all a finite game, one handled quite well by ordinary computation, as even Dreyfus must now admit. We're talking about an infinite game; here's how it works. You will need a place-marker (a dime will do nicely), and the graph shown in Figure 3 (across which you will slide the dime). We will be black, you will be red. Notice that the nodes in the graph of Figure 3 are divided in half: three are red (r) nodes; three are black (b) nodes. If the dime is on an r node, then it's your turn, as red, to move; if the dime is on a b node, it's our turn. Here's how the game proceeds. The dime is placed randomly on one of the nodes, and then we take turns with you, sliding it from node to node, making sure that a move is made in accordance with a connecting arrow. So, if the dime is initially upon , you would move, and your options are and . If you slid the dime to , our only option would be , and so on. Now, here's the thing: you and the two of us are going to take turns back and forth for an infinite amount of time. Since you may complain at this point that you are mortal, we want you to assume for the sake of the game that the three of us, like super-machines, can in fact take turns forever. [Super-machines are those with more power than Turing Machines. Super-minds are beings having, among other things, information-processing power above TMs. For more on super-computation in general, including an introduction to the Arithmetic Hierarchy, see [Bringsjord, 1997a]. For a sustained defense of the view that human persons are indeed super-minds, see the forthcoming book Super-Minds: [Brinsjord and Zenzen, 1997].] Okay, now notice that nodes and are double-circles; this is because these two are ``winning" nodes. We win, as black, if and only if either and are both visited only finitely many times or are both visited infinitely often. You, red, win if and only if one of these two nodes is visited infinitely often and the other finitely often. Got it? Okay, now: What is your strategy? What is your best strategy? What is our best strategy? If we both play our best, who will win? And supposing we play only for a finite amount of time, how could a referee predict a winner?

Don't read this paragraph if you intend to tackle these questions. Only black has an invincible strategy, viz., from move to if has never been visited or if has been visited since the last time was visited; in all other circumstances move to . So there was really no way for you to beat us! It is remarkable that ordinary computation can find this strategy when presented with the game in question [McNaughton, 1993]. (No ordinary computer can literally play the game, of course.) However, for a game utterly beyond the Turing Limit, see the ``undetermined" game featured in [Gale and Stewart, 1953]: this is a game where a winning strategy cannot be devised by ordinary computation (in fact, there is no mathematical function which is a winning strategy!). It seems to us that infinite games, perhaps especially uncomputable infinite games, provide promising frameworks for mind-machine competition. The first step, which we are in the process of taking, is to take a computable infinite game and cast it in terms allowing for mind-mind competition. [We are starting with McNaught. The task of declaring a winner in finite time is rather challenging. See the approach indicated in [McNaughton, 1993].] Other frameworks might involve competition centering around the creation of infinite (and other types of) games.

Next: On the ``Big" Questions Up: Chess Isn't Tough Enough: Previous: Checkmate to Debate to

Selmer Bringsjord
Mon May 12 11:57:39 EDT 1997