Tic Tac Toe Coding Challenge

[Kevin_Price]

Shane,

Ok, I'll watch your "Ultracon" player during a match to see what the strategy looks like.  Whatever it is, I know it sure runs fast!

Re: the scoring system.  I just partially remembered a little tidbit from a linear algebra course.  It had to do with neat little application of matrix math.  Oh hey!  The book is on my shelf.   Just a sec (riffle, riffle).

OK, there was a cute example for ranking the strength of competitors where each player matches up 1 time against each other player.  You construct a "domination" matrix D where each element d(i,,j) == 1 iff player i beats player j, else 0.  So the sum of row i gives the # of wins by player i.   The cute part is that you can account for "strength of schedule" somewhat by squaring the matrix, i.e., D*D.  Row i of this result sums all the wins by all the opponents that player i beat.  Finally, you can rank players by summing row i of (D + D*D).  This method gives greater reward for beating competition that also did well.  It does not penalize you for losing to competition that did poorly however.

Anyway, I think there's at least the germ of a good idea in there for how to handle scoring.  Some other off-the-cuff thoughts on scoring:

A. 100 head-to-head matchups: I'm not sure this is enough to discriminate.  For example, CCref (playing first as "X") beats KP2a about 1 time in 1000 quite consistently and never loses.  It's clearly better, but 100 head-to-head matchups isn't likely to reveal that fact.

B. 1 point for draw, 2 points for forced-win: My gut feel is that this isn't enough reward for a forced-win.  I'd think something nearer to a 10-to-1 ratio might be better, but that's also just a guess.

C. Pattern challenges: quite interesting, but probably shouldn't be considered for official contest.  It'd be interesting to present some impossible patterns too, like 2 X's and 4 O's or something.  Really stack the deck against the various algorithms.

D. Multiple entries: I've heard of some programming contests where people tried to scam the system by putting in several similar entries with a subtle but exploitable flaw.  Then the "real" entry exploits the heck out of that flaw to artificially inflate its own score.  So if multiple entries per person are allowed, perhaps their results against each other shouldn't count.

-Kevin P.

[Kevin_Price]

Re: Shane's "Ultracon":  OK, last night I paid attention.  Nice simple strategy -- no wonder it ran so fast!  (BTW, it's one of those nice, simple, elegant solutions that makes me go d'oh! and wish I'd thought of it on my own.)

I found a nice little tweak to my "KP2a" player that actually improves it.  The essence of it, in vague terms, is like this:  when I evaluate a given board position, I evaluate plays that put me in greater danger of 4-in-a-row and I evaluate plays that block the opponent from making 4-in-a-row.

KP2a is rather conservative, preferring to avoid its own 4-in-a-rows even if it means blocking potential opponent 4-in-a-rows.  So I did an experiment where I simply swapped the evaluation ratings (preferring to put myself at some risk in order to keep potential opponent 4-in-a-rows open) to try to get more aggressive.

Here are some observations from the aptly-named KP2b:

1. Has never been beaten by any of the players posted here (except the nefarious Deep Toe).

2. Playing as 1st player "X", can beat CCref about 10% of the time with 90% draws.  Playing as 2nd player "O", we have 100% draws.

3. Playing against Random, performs better than KP2a but still worse than CCref.

Again, I tried a few tiny little tweaks to the evaluation function, based on some ideas that intuitively seemed sensible.  Each of them made things quite noticeably worse.  So my best result still arises from an implementation bug rather than careful consideration.

-Kevin P.

[Ben]

CC wrote:

"

Seems that the excitement is decreasing. Are the thread and challenge already dead ?

"

I just posted to LAVA to try and step up the competion level a notch.

Ben

[chilly_charly]

---

Ben a écrit:

I just posted to LAVA to try and step up the competion level a notch.

---

Ben,

That's a great idea. I wish I had it before ! 🙂

I have been really pleased to learn that you intend to participate one way or the other to this challenge. I hope to compete soon against one of your productions.

[280Z28]

So this challenge ends July 14? I'll try and get something in. 🙂

[altenbach]

---

@chilly charly wrote:

checker board (always draw, but that can be tricky...)

The S-fence :(the second win or draw)

The A-fence (the second win or draw)

The Vee (always draw)

---

Here's my analysis of these positions under optimal play (Objective: playing to loose!):

1. Checker board (100% draw)
2. S-Fence (100% draw)
3. A-Fence (100% draw)
4. Vee (100% draw)

I have made a very simple "Deepest Toe" human interface that plays optimally for either win or loose (selectable at any time). You can easily check any position and it will tell you the outcome for each possible current move. I am not ready to share any code (yes, it is all pure G!), but attached is a LabVIEW 7.1 executable for your enjoyment. You can use it to analyze where your code makes mistakes (requires LabVIEW 7.1 runtime).

(This is just a first draft, so there are probably little bugs. I'll post a more polished version at a later time).

For example, in the position of the attached picture, O can force a loss in 8, four other positions are even, and four other moves would cause a win in 9 (and thus a loss of the challenge).

Message Edited by altenbach on 05-14-2006 09:59 AM

[Ray.R]

Thanks Altenbach.

WOW!!  You guys are seriously into this game..  WoW!..

I wish I had the time to investigate some strategy...  I should still be able to submit something and hopefully not come in last place..  😮  But this is definetly an interesting challenge and fun to read the postings!!  🙂

JLV

[johnsold]

Christian,

What about those of us on other platforms? I can't test my ideas (which seem to be along the same lines as yours) on my Mac.

Thanks,

Lynn

[chilly_charly]

Seems that Altenbach designed the optimal player. Thumb up. 🙂 😠 😄

Does this mean that the challenge is over ? Do we already know the name of the winner ? Fortunately, I don't think so.

From the beginning it has been stated that this reverse TTT competition would always lead to a draw, assuming a perfect play. After some web search I even found that this had been demonstrated mathematically.

We soon discovered that the ability to win against weak players would ultimately make the difference. Although it is relatively easy to build a player that never loose whatever its opponent, the real challenge is to build a player that would also always win against a weaker player, any time a mistake is made. Although Altenbach's player is undoubtedly excellent at that, he is not yet the best : The winner will be able to choose the best moves before the opponent makes a mistake... 🙂 

Just to stir the pot, among the various thingsI have produced so far, there is evolutionnary dead-end player able to win 100 % of the time against CC-ref when playing as X, and 60 % as O (score 200/160). However, that's nearly the only thing he is good at ... :(:D

Thanks again to Bruce for designing this fun challenge.

[altenbach]

---

@chilly charly wrote:

Does this mean that the challenge is over ? Do we already know the name of the winner ? Fortunately, I don't think so.

---

Oh, I fully agree! There is much more to the competition than a perfect player, else I would not have posted it. Believe me, I thought long and hard before posting if it would encourage or discourange others form participating and came to the conclustion that it would raise interest. 🙂

Some other ideas:

• Since we know that all boards with up to five pieces are a draw, all games should start from random 5 piece positions. This way many games between any two competitors can be played and scored and there won't be any duplicate games.
• If I can make the perfect player, everybody can. 😄 So who can make the fastest and smallest! 😮
• We could make a scorer that offers a few thousand "difficult positions", then counts how many are solved correctly by each entry and in what time.
• Players should also properly detect illegal positions.

I actually would suggest to change the player template: We don't need the player input, it is redundant because it can be determined from the given position. We only need the board input. Instead we should have an error output if the player determines that the given position is illegal (e.g. 5Xs and 6Os, etc.). How about an output to resign??