Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!munnari.oz.au!bunyip!brolga!eric
From: eric@brolga.cc.uq.oz.au (Eric Halil)
Newsgroups: comp.misc
Subject: Re: Tic-Tac-Toe algorithm?
Message-ID: <1990Jun7.062458.16343@brolga.cc.uq.oz.au>
Date: 7 Jun 90 06:24:58 GMT
References: <13742@venera.isi.edu>
Organization: Prentice Computer Centre
Lines: 70

In article <13742@venera.isi.edu> lpress@venera.isi.edu (Laurence I. Press) writes:
>I recall seeing a very simple algorithm for playing optimal tic-tac-toe
>which was based on merely doing arithmetic on the values of the cells
>when arranged as follows:
>1 2 3
>4 5 6
>7 8 9
>Does anyone know what the trick is (I can't remember)?
>Lar

Is this what you're thinking of? (this was extracted from "Games Playing with
Computers", AG Bell, George Allen & Unwin Lmtd, 1972). Its definitely not
as simple as you said, but I thought it was pretty good.

-----------------------------------------------
When the machine has first move, a simple algorithm *which can never lose* 
was described in

	D. Michie, "Machines that play games", New Scientist, 1961, v12, p367

Here the machine moves are X, humans play O. For every X on the board enter
6, for every empty cell enter 1, and for every O enter -4.

For example,

 X |   | O                                          6 | 1 | -4
---+---+---                                        ---+---+---
   |   | X         is represented by                1 | 1 |  6
---+---+---                                        ---+---+---
 O |   |                                           -4 | 1 |  1

Calculate the eight products of three numbers in a line, thus;

                 6 | 1 | -4     => -24
                ---+---+---
                 1 | 1 |  6     =>   6
                ---+---+---  
                -4 | 1 |  1     =>  -4
               /            \
              /  |   |    |  \
             /   v   v    v   \
           16   -24  1   -24   6

Sum for each empty square *all* the intersecting scores;

		   | -23 |
	      -----+-----+-----
	       -18 |  29 |
	      -----+-----+-----
		   |  -3 | -22

The correct play is in the square of the largest score, in this case the
centre. NB The machine always take the centre as its first move. A weakness
of this algorithm is that it does not take advantage always of an opponents
losing move.
-----------------------------------------------

Can anyone explain this algorithm intuitively?????

Now it should be easy to extend this type of algorithm to similar trivial
closed games, for example Go :-) 

Eric.
----------------------------------+------------------------------------------
Eric Halil                        |
Prentice Computer Centre          |Internet/CSnet:           eric@cc.uq.oz.au
University of Queensland  4072    |Bitnet:      eric%cc.uq.oz.au@uunet.uu.net
AUSTRALIA                         |UUCP:          uunet!munnari!cc.uq.oz!eric
Phone: +61 7 377 3022             |JANET:          eric%cc.uq.oz.au@uk.ac.ukc
----------------------------------+------------------------------------------