Tic Tac Toe Coding Challenge

[altenbach]

Interesting problem. 😄

Soo..., what do the game theoreticians say about this problem. Has it been fully analyzed?

1. Is it always a draw under optimal play? (I think there are final boards possible with not even any 3 in a row)
2. Can X force a win?
3. Can O force a win?

How about a time limit during competition play? Testing the self-play speed can easily be defeated by having the code switch to a very fast algorithm if the side changes with every call of the subVI. 😉

[chilly_charly]

---

altenbach a écrit:...I think there are final boards possible with not even any 3 in a row

---

Here is one. Any other possibility, apart Pi/2 rotations ?

Seems that this challenge will be fun ! I have already lost a couple of hours.

Thanks Bruce !

Message Edité par chilly charly le 04-27-2006 05:32 PM

[chilly_charly]

...or symetry ?

[JeanPierre]

That's too easy. Just play with the same symbol as your opponent 

[altenbach]

CC, there are plenty more drawn position. Just run Bruce's random player a few times and you'll get a nice collection. 🙂

Some statistics on Bruce's random player:

Given enough games, ~41.6% end in a draw, ~31.7% are won by the one who moves first, and ~26.7% by the other player.

I guess the first benchmark would be an engine that wins 100% playing as "O" against the random player.

41% is an awfully high number. I wonder if a perfect play always ends in a draw? 😮 Is the game flawed??? We'll see. 😉

[altenbach]

---

@altenbach wrote:

Given enough games, ~41.6% end in a draw, ~31.7% are won by the one who moves first, and ~26.7% by the other player.

---

Of course "winning" means 4 in a row and actually loosing the challenge of NOT winning. 😄

This is a bit confusing. The program should display the looser after the game has finished, right?

[BruceAmmons]

Yes, I should have made it display the loser.  The main purpose is to give you a clear understanding of how your routine will be called for testing.  In my version, I will use VI server to call each combination of players instead of calling them directly.

I assume Christian put my tester inside a loop, which is a great way to test your routine against the random player.  I wrote one just for kicks, and discovered that the random player still won around 0.1%, which means my algorithm is flawed.

I suspect the perfect player would be able to always draw or win.  I didn't find any proof of this assumption on the web, though.  That is why I picked 4x4 and losing - I didn't find nearly as many "solutions" on the web, so I don't think anybody will be able to copy an algorithm from the web.

I'm glad to see a strong interest in the challenge.  I'm looking forward to seeing some submissions.

Bruce

[BruceAmmons]

I thought about setting a time limit, but I figure even the most inefficient routines will only take a second or two for each turn, and I can live with that.  I suspect most players will take just a few milliseconds to play the entire game, or even less.

Obviously, I wouldn't allow a routine that changes strategies when playing against itself.  That would be called cheating, wouldn't it?

Bruce

[Henrik_Volkers]

Thank you Bruce 🙂

Without searching the web ... I remember an article about a mechanical 3x3 ti tac toe player ... basically a hard coded lookup table.

With the assumption that for every position you can name one best move (to loose)... lets see

Simple lookup table could be a complete I32 table 16 bit x-position and 16 bit o-position and 4 bit for the move = 2GB

 rotation /4 = 512 kB , symmetry /4 = 128kB    minus (most?) left positions where already someone won  .... double for faster lookup

Yepp, a lookup table seems possible

Something missing.. ?  Oh, only the best move

Just my thoughts ... since I have no time for coding... Have FUN   

Followup:

A way to the best move?

Given a list of (possible, resonable?) positions (ca. 64kB), in mean 7 possible moves plus weight factor (7x16bit, 4bit move 12bit factor) roundabout 1GB...

(just a big state mashine ...)

now start random walks and increment/decrement the factor according to the result...

Message Edited by Henrik Volkers on 04-28-2006 10:16 AM

[shoneill]

Henrik,

I too have an initial feeling that this challenge may be less intricate than others, but then I think I thought that about every challenge up until now......

Perhaps look-up tables should not be allowed above, say 100 entries.  Kind of like only allowing the primes up to 1000 in the last challenge.

Personally, I'll try to take part in this one, it's cool.

Shane.