lpress@venera.isi.edu (Laurence I. Press) (06/02/90)
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
root@kunivv1.sci.kun.nl (Privileged Account) (06/04/90)
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 I think you are referring to this little game in which the players alternately mention numbers in the range 1..9 until one of them has mentioned three numbers whose sum is 15. This game is essentially equivalent to playing tic-tac-toe on a board that looks like: 8 3 4 1 5 9 6 7 2 Or is there more to it? -- Hans Mulder hansm@cs.kun.nl
eric@brolga.cc.uq.oz.au (Eric Halil) (06/07/90)
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 ----------------------------------+------------------------------------------