Tic Tac Toe Coding Challenge

[Henrik_Volkers]

Shane,

the good (and bad) thing about those challenges: If you start thinking about it, you hardly can stop the brain cells dancing with that theme...

[BruceAmmons]

Actually, I would allow a lookup table.  I think it would be challenging enough to generate the lookup table.  Of course, I won't take a 2 GB entry, or even a 100 MB entry.  The absolute limit would be around 10 MB, but I would prefer less than 1 or 2 MB.  So perhaps lookup tables won't be possible due to shear size.  Hmmm, perhaps that was another reason I picked a 4x4 grid.

Bruce

[jasonhill]

Bonus points for generating the look up table at run time

Double bonus points for a "general" solution for a nxn grid, where n>3.  Or maybe not.  As I look at my rough draft, it could easily be converted to a "general" loser.

[altenbach]

---

@Bruce Ammons wrote:

I wrote one just for kicks, and discovered that the random player still won around 0.1%, which means my algorithm is flawed.

---

That could actually be a good way to resolve ties! Rank the entries with the same score according to the loosing percentage angainst the random player after a few million games. 😄

I also quickly made a very primitive player just for kicks (purely static evaluation), but it is not perfect. As X it still wins about 4 in a million (very reproducible after 10 million tries), while as O it wins about 5-7%. 😞 Is yours better than that playing as O?

Also make sure to test for legality in your tester (selected coordinates don't yet contain a piece AND are in the range 0..3) and immediately disqualify flawed entries. 😉

[Ray.R]

I'm just reading this thread for now... and being entertained 😉

Not to modify the contest, but an interesting challenge would be the ability to play Tic-tac-toe to win, by having people's code play against one another.  That way whoever actually wins most often and fastest (less time) actually wins.. 

Just throwing a silly idea...

Ray

[altenbach]

---

@JoeLabView wrote:

Not to modify the contest, but an interesting challenge would be the ability to play Tic-tac-toe to win, by having people's code play against one another. 

---

Hey, I did a 20 second modification to my draft and simply inverted the evaluation function. Result (Win%, loose%,draw%) against the randomizer:

As X: [29%, 0%(!), 71%]
As O: [22.5%, 0.01%, 77.5%%]

Beat that!

Interestingly, against itself it is a 100% draw...

[jasonhill]

---

@altenbach wrote:

Interestingly, against itself it is a 100% draw...

---

I thought that was one of the "features" of tic-tac-toe.  If both players play to win, it will always tie.  I would expect it to be doubly true if both players are using the same algorythm.

[Ray.R]

---

jasonhill wroteI would expect it to be doubly true if both players are using the same algorythm.

---

Now that would interesting to try out 😉

[BruceAmmons]

The original idea for the challenge was to play to win.  I decided it was too easy to write an algorithm that would never lose.  I wrote one in a just an hour or two that I think worked pretty well.  That is why we decided to make you try to lose instead of win.  This appears to be more challenging.

For my current solution (discussed earlier), I just inverted the logic on my winning routine.  I found out that it would still win against the random player occasionally, where I expected it to always be a draw or loss.  I figure there has to be a better algorithm that will never win, but I haven't figured it out yet, and I can't prove that it exists.

For the competition, I will have each player play every other entry, once as X and once as O.  The player with the most losses and draws will win, where a loss is 2 points and a draw is 1 point.

If you haven't read the rules on the LabVIEW Zone, please do so.  There are a lot more details provided there than on this discussion.

By the way, Mike Teixeira gets a brownie point for submitting the first entry in the contest.  As soon as I get a few more entries, I will be able to post some preliminary standings...

Bruce

[altenbach]

It seems that it is easy to fully analyze the problem and make a god-like program that fits in a few MB. This is similar to the fully analyzed chess endgame databases originally started by Ken Thompson many years ago.

Removing all symmetry related positions, all illegal positions (number of X=number of O or O+1) and everything with more than two rows of four, there is not much left, for example there are only three unique moves to start the game.

I wrote a quick a dirty program to generate all possible legal positions (takes only a few minutes). now it would be easy to recursively create a scoring table to produce a (win in t, loose in t or draw) to every possible case. Attached in a graph of the number of unique positions as a function of the number of pieces on the board. Anyone got a similar result?

Message Edited by altenbach on 05-01-2006 01:26 PM