From: John Thingstad
Subject: Tick tack (old age attack)
Date: 
Message-ID: <op.tmn07bimpqzri1@pandora.upc.no>
Help me!
I am thouroughly miserable with this code.
The algorithm is wrong.
Many of the optimations don't turn out as planned.
The structure got perverted by adding detail.
I'd like to have a decent program for once. To look back on. But this  
ain't it.
Before I ditch it.. Does anyone see what I missed?

Here is the code:
home.chello.no/~jthing/games/tictactoe.html

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

From: Harold Lee
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <1169670172.214042.290340@j27g2000cwj.googlegroups.com>
On Jan 24, 7:55 am, "John Thingstad" <··············@chello.no> wrote:
> Help me!
> I am thouroughly miserable with this code.
> The algorithm is wrong.
> Many of the optimations don't turn out as planned.
> The structure got perverted by adding detail.
> I'd like to have a decent program for once. To look back on. But this
> ain't it.
> Before I ditch it.. Does anyone see what I missed?
>
> Here is the code:
> home.chello.no/~jthing/games/tictactoe.html

I've always enjoyed the Tic-Tac-Toe explanation in this paper:
http://www.math.chalmers.se/~rjmh/Papers/whyfp.html

You algorithm seems to favor the middle square too heavily: by taking
the center after the first move takes a corner, it always looses (if we
ignore stupid moves by the human player).

-Harold
From: Ray Dillinger
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <45c4d914$0$69041$742ec2ed@news.sonic.net>
Harold Lee wrote:
> On Jan 24, 7:55 am, "John Thingstad" <··············@chello.no> wrote:
> 

> You algorithm seems to favor the middle square too heavily: by taking
> the center after the first move takes a corner, it always looses (if we
> ignore stupid moves by the human player).

No, a perfectly valid Ticktactoe opening strategy is to take the
middle square on your first turn if it's available or a corner
square if not.  The move is strong enough that if you minmax on
your second and subsequent turns you'll never actually lose, and
it saves you the deepest recursion.

				Bear
From: Dan Bensen
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <ep8iso$ajs$1@wildfire.prairienet.org>
John Thingstad wrote:
> Before I ditch it.. Does anyone see what I missed?
A move search, like the one in your Othello game.
With the evaluation function in your ttt code,
you have to look ahead three half-moves to play reliably.

-- 
Dan
www.prairienet.org/~dsb
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmp3lzbkpqzri1@pandora.upc.no>
On Wed, 24 Jan 2007 16:55:49 +0100, John Thingstad  
<··············@chello.no> wrote:

> Help me!
> I am thouroughly miserable with this code.
> The algorithm is wrong.
> Many of the optimations don't turn out as planned.
> The structure got perverted by adding detail.
> I'd like to have a decent program for once. To look back on. But this  
> ain't it.
> Before I ditch it.. Does anyone see what I missed?
>
> Here is the code:
> home.chello.no/~jthing/games/tictactoe.html
>

Ok added quick fix.
rule 2.5
If it's your first move and the other guy has a corner then
take the oposing corner.

This is probaly not as good as minimax which is guaranteed to at win
or draw. But I don't think there are any other ways that you can make
the computer loose every time at least.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Dan Bensen
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <epb2hr$3qh$1@wildfire.prairienet.org>
John Thingstad wrote:
> ... quick fix.
> If it's your first move and the other guy has a corner then
> take the oposing corner.

X|_|X
_|_|_
_|_|O

Your turn :D

-- 
Dan
www.prairienet.org/~dsb
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmq4r3jtpqzri1@pandora.upc.no>
On Thu, 25 Jan 2007 21:09:30 +0100, Dan Bensen <··········@cyberspace.net>  
wrote:

> John Thingstad wrote:
>> ... quick fix.
>> If it's your first move and the other guy has a corner then
>> take the oposing corner.
>
> X|_|X
> _|_|_
> _|_|O
>
> Your turn :D
>

By rule 2

XOX
---
--O

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Rob Warnock
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <_uqdnay4mdlXIiTYnZ2dnUVZ_tfinZ2d@speakeasy.net>
John Thingstad <··············@chello.no> wrote:
+---------------
| Dan Bensen <··········@cyberspace.net> wrote:
| > John Thingstad wrote:
| >> If it's your first move and the other guy has a corner then
| >> take the oposing corner.
| >
| > X|_|X
| > _|_|_
| > _|_|O
| >
| > Your turn :D
| 
| By rule 2
| 
| XOX
| ---
| --O
|
+---------------

I think what Dan meant was that X then does this:

    X|O|X
    _|_|_
    X|_|O

and you're forked.


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmraseiypqzri1@pandora.upc.no>
On Thu, 25 Jan 2007 21:09:30 +0100, Dan Bensen <··········@cyberspace.net>  
wrote:

> John Thingstad wrote:
>> ... quick fix.
>> If it's your first move and the other guy has a corner then
>> take the oposing corner.
>
> X|_|X
> _|_|_
> _|_|O
>
> Your turn :D
>

CL-USER 4 > (tic-tac-toe)
Welcome to the game Tic tac Toe
To play a move select a number on the grid

     1 2 3
  A  - - -
  B  - - -
  C  - - -

Enter move: A1

X - -
- - -
- - O

Enter move: A3

X O X
- - -
- - O

Enter move: C1

X O X
O - -
X - O

Enter move: B2


You won!

CL-USER 5 > (dribble)

Except I can't see how the computer could avoid loosing..

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Lars Brinkhoff
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <85lkjqym9l.fsf@junk.nocrew.org>
"John Thingstad" <··············@chello.no> writes:
>      1 2 3
>   A  - - -
>   B  - - -
>   C  - - -
>
> Enter move: A1
>
> X - -
> - - -
> - - O
>
> Except I can't see how the computer could avoid loosing..

By taking the center square, not the opposing corner.
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmrnqgfxpqzri1@pandora.upc.no>
On Fri, 26 Jan 2007 14:01:58 +0100, Lars Brinkhoff <·········@nocrew.org>  
wrote:

> "John Thingstad" <··············@chello.no> writes:
>>      1 2 3
>>   A  - - -
>>   B  - - -
>>   C  - - -
>>
>> Enter move: A1
>>
>> X - -
>> - - -
>> - - O
>>
>> Except I can't see how the computer could avoid loosing..
>
> By taking the center square, not the opposing corner.

lol. That was what it did originally.

X - -
- O -
- - X

Oops.. You still loose..

X - O
- O -
X - X

X - O
O O -
X X X


-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Nils M Holm
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <epd6v4$9os$1@online.de>
John Thingstad <··············@chello.no> wrote:
> On Fri, 26 Jan 2007 14:01:58 +0100, Lars Brinkhoff <·········@nocrew.org>  
> > By taking the center square, not the opposing corner.
> 
> lol. That was what it did originally.
> 
> X - -
> - O -
> - - X
> 
> Oops.. You still loose..
> 
> X - O
> - O -
> X - X
> 
> X - O
> O O -
> X X X

Here's how my program (http://t3x.org/pstk/ttt.scm) responds
(X = human, O = program, human begins):

X - -   X - -   X - -
- O -   - O -   - O -
- - -   - - X   - O X

Which corner do you want at this point? ;-)

-- 
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
From: Ken Tilton
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <MLquh.83$U43.53@newsfe08.lga>
Nils M Holm wrote:
> John Thingstad <··············@chello.no> wrote:
> 
>>On Fri, 26 Jan 2007 14:01:58 +0100, Lars Brinkhoff <·········@nocrew.org>  
>>
>>>By taking the center square, not the opposing corner.
>>
>>lol. That was what it did originally.
>>
>>X - -
>>- O -
>>- - X
>>
>>Oops.. You still loose..
>>
>>X - O
>>- O -
>>X - X
>>
>>X - O
>>O O -
>>X X X
> 
> 
> Here's how my program (http://t3x.org/pstk/ttt.scm) responds
> (X = human, O = program, human begins):
> 
> X - -   X - -   X - -
> - O -   - O -   - O -
> - - -   - - X   - O X
> 
> Which corner do you want at this point? ;-)
> 

Interesting that even something as simple as ttt defies a rules-based 
approach, which the chess folk quickly (?) abandoned in favor of brute 
force search.

kzo

-- 
Well, I've wrestled with reality for 35 years, Doctor, and
I'm happy to state I finally won out over it.
                                   -- Elwood P. Dowd

In this world, you must be oh so smart or oh so pleasant.
                                   -- Elwood's Mom
From: Ari Johnson
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <m21wlhawyl.fsf@hermes.theari.com>
Ken Tilton <·········@gmail.com> writes:

> Nils M Holm wrote:
>> John Thingstad <··············@chello.no> wrote:
>> 
>>> On Fri, 26 Jan 2007 14:01:58 +0100, Lars Brinkhoff
>>> <·········@nocrew.org>  
>>>
>>>>By taking the center square, not the opposing corner.
>>>
>>>lol. That was what it did originally.
>>>
>>>X - -
>>>- O -
>>>- - X
>>>
>>>Oops.. You still loose..
>>>
>>>X - O
>>>- O -
>>>X - X
>>>
>>>X - O
>>>O O -
>>>X X X
>> Here's how my program (http://t3x.org/pstk/ttt.scm) responds
>> (X = human, O = program, human begins):
>> X - -   X - -   X - -
>> - O -   - O -   - O -
>> - - -   - - X   - O X
>> Which corner do you want at this point? ;-)
>> 
>
> Interesting that even something as simple as ttt defies a rules-based
> approach, which the chess folk quickly (?) abandoned in favor of brute
> force search.

Many many years ago, I wrote a couple of Tic Tac Toe programs (in C).
The best one in the long run (although it lost even to the random-play
program in early rounds) was "learn," which memorized every
configuration the board took in every game it played and kept track of
how many times it won or lost when the board had previously been in
each configuration.  Then, it would pick the configuration in a future
game that gave it the most wins in the past.  That was the lazy
version of brute force.
From: Ken Tilton
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <bCBuh.125$U43.63@newsfe08.lga>
Ari Johnson wrote:
> Ken Tilton <·········@gmail.com> writes:
> 
> 
>>Nils M Holm wrote:
>>
>>>John Thingstad <··············@chello.no> wrote:
>>>
>>>
>>>>On Fri, 26 Jan 2007 14:01:58 +0100, Lars Brinkhoff
>>>><·········@nocrew.org>  
>>>>
>>>>
>>>>>By taking the center square, not the opposing corner.
>>>>
>>>>lol. That was what it did originally.
>>>>
>>>>X - -
>>>>- O -
>>>>- - X
>>>>
>>>>Oops.. You still loose..
>>>>
>>>>X - O
>>>>- O -
>>>>X - X
>>>>
>>>>X - O
>>>>O O -
>>>>X X X
>>>
>>>Here's how my program (http://t3x.org/pstk/ttt.scm) responds
>>>(X = human, O = program, human begins):
>>>X - -   X - -   X - -
>>>- O -   - O -   - O -
>>>- - -   - - X   - O X
>>>Which corner do you want at this point? ;-)
>>>
>>
>>Interesting that even something as simple as ttt defies a rules-based
>>approach, which the chess folk quickly (?) abandoned in favor of brute
>>force search.
> 
> 
> Many many years ago, I wrote a couple of Tic Tac Toe programs (in C).
> The best one in the long run (although it lost even to the random-play
> program in early rounds) was "learn," which memorized every
> configuration the board took in every game it played and kept track of
> how many times it won or lost when the board had previously been in
> each configuration.  Then, it would pick the configuration in a future
> game that gave it the most wins in the past.  That was the lazy
> version of brute force.

Does "lazy" mean "space intensive" vs. "compute intensive"? Anyway...

...as a simple application programmer (not smart like you folks), I am 
fascinated by how one could algorithmically collapse positions, both by 
rotation and, um, mirroring?, to optimize storage/computation. these are 
the same:

x-- --x
--- ---
--- ---

and these are the same:

xo- x--
--- o--
--- ---

so these are all the same:

xo- x-- ---
--- o-- --o
--- --- --x

What's the code for that? I think we need a find-ttt function returning 
two values---wait, one? The matrix transformations necessary to produce 
the sought position, if found?

btw, I saw a few folks offer solutions with hard-coded rules for 
varieties of positions. Kiddies, plz, that is /not/ what we call 
computer programming. The in-between ones where the programmer tried to 
generate rules abstracted one level above concrete positons are fun, 
anyway, if still cheating. But laying out almost one rule per position? 
Puh-leeze. That is called brute force programming: Oh, we lost? Let us 
take everything we know about this particular game and figure out what 
new rule would have won...great! Run it again! <sigh>

The ideal engine gets two parameters, a valid-move-generator and a 
won-lost-determiner, period. Well, also a current-position function so 
it can learn  position assessment and do breadth-first search for the 
best move.

kzo

-- 
Well, I've wrestled with reality for 35 years, Doctor, and
I'm happy to state I finally won out over it.
                                   -- Elwood P. Dowd

In this world, you must be oh so smart or oh so pleasant.
                                   -- Elwood's Mom
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmte3gttpqzri1@pandora.upc.no>
On Sat, 27 Jan 2007 06:41:27 +0100, Ken Tilton <·········@gmail.com> wrote:

>
> The ideal engine gets two parameters, a valid-move-generator and a  
> won-lost-determiner, period. Well, also a current-position function so  
> it can learn  position assessment and do breadth-first search for the  
> best move.
>
> kzo
>

Minimax is a good idea for many games.
With alpha-beta cutoff it can be extended to more complex games.
But I agree with Holm that Minimax seems like overkill here.
He just exploits the simple structure of the problem.

1. There are 3^3 = 27 permutations of three squares
2. There are 3 + 3 + 2 = 8 moves

Abstract away the row, col, diag.
So the simplicity lends itself to direct mapping.

Average of 8 * 27 / 2 = 108 comparisons pr. move.

How is hammering in a nail with a sledgehammer a advantage?
Real elegance is in exploiting the symmetry of the problem.

Indeed if he wanted to extend it to 3D TTT (4 X 4 X 4) he
would have to start over. And your approach is probably right here.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmrtkyy0pqzri1@pandora.upc.no>
On Fri, 26 Jan 2007 16:32:52 +0100, Nils M Holm  
<·················@online.de> wrote:

>
> Here's how my program (http://t3x.org/pstk/ttt.scm) responds
> (X = human, O = program, human begins):
>
> X - -   X - -   X - -
> - O -   - O -   - O -
> - - -   - - X   - O X
>
> Which corner do you want at this point? ;-)
>

You are right! The approach my algorihm uses plainly dosn't work.
1. As it stands it still contains errors according the spesification.
2. Even if it followed the spesification it wouldn't beat this problem.
    You would need to look several steps ahead.

If you don't mind I think I will do a full reimplementation using
your approach. Oh well, I guess anyone can produce a turkey once
in a while.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Nils M Holm
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <epdqdf$j47$1@online.de>
John Thingstad <··············@chello.no> wrote:
> On Fri, 26 Jan 2007 16:32:52 +0100, Nils M Holm  
> <·················@online.de> wrote:
> > Here's how my program (http://t3x.org/pstk/ttt.scm) responds
> > (X = human, O = program, human begins):
> >
> > X - -   X - -   X - -
> > - O -   - O -   - O -
> > - - -   - - X   - O X
> >
> > Which corner do you want at this point? ;-)
> >
> 
> You are right! The approach my algorihm uses plainly dosn't work.
> 1. As it stands it still contains errors according the spesification.
> 2. Even if it followed the spesification it wouldn't beat this problem.
>     You would need to look several steps ahead.
> 
> If you don't mind I think I will do a full reimplementation using
> your approach. [...]

Feel free to use my ttt code in any way you want. BTW, there is
one rule that is not in the table: when the human player does not
occupy the center, the computer does so in its first move.

> Oh well, I guess anyone can produce a turkey once
> in a while.

Happens to the best of us.

-- 
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
From: Robert Uhl
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <m3sldweuxx.fsf@latakia.dyndns.org>
"John Thingstad" <··············@chello.no> writes:
>
> You are right! The approach my algorihm uses plainly dosn't work.

Admitting you're wrong--that's something like 248 Usenet Points...

-- 
Robert Uhl <http://public.xdi.org/=ruhl>
Of course it originated with the Romans!  Who else would _need_ a word
that means `kill every tenth person'?                  --Loren Wiseman
From: John Thingstad
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <op.tmva2pa5pqzri1@pandora.upc.no>
On Fri, 26 Jan 2007 18:01:36 +0100, John Thingstad  
<··············@chello.no> wrote:

> On Fri, 26 Jan 2007 16:32:52 +0100, Nils M Holm  
> <·················@online.de> wrote:
>
>>
>> Here's how my program (http://t3x.org/pstk/ttt.scm) responds
>> (X = human, O = program, human begins):
>>
>> X - -   X - -   X - -
>> - O -   - O -   - O -
>> - - -   - - X   - O X
>>
>> Which corner do you want at this point? ;-)
>>
>
> You are right! The approach my algorihm uses plainly dosn't work.
> 1. As it stands it still contains errors according the spesification.
> 2. Even if it followed the spesification it wouldn't beat this problem.
>     You would need to look several steps ahead.
>
> If you don't mind I think I will do a full reimplementation using
> your approach. Oh well, I guess anyone can produce a turkey once
> in a while.
>

Ok the new Tic Tac Toe game using Nils M. Holm's algorith is now published.
Seems to work fine now! :)

httt://home.chello.no/~jthing/games/tictactoe.html

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Damien Kick
Subject: Re: Tick tack (old age attack)
Date: 
Message-ID: <DWovh.16540$yx6.16318@newsread2.news.pas.earthlink.net>
John Thingstad wrote:

> Ok the new Tic Tac Toe game using Nils M. Holm's algorith is now published.
> Seems to work fine now! :)
> 
> httt://home.chello.no/~jthing/games/tictactoe.html

Wow, and you've even implemented a networking protocol, 
hyper-tic-tac-toe, too <wink>.