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/
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
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
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
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/
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
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/
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
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/
"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.
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/
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
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.
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
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/
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/
"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
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/
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>.