Here is the new coding challenge!!!  You need to create a vi that will play the game of tic tac toe.  It will be played on a 4x4 grid, and the objective is to LOSE the game, not win.  The complete rules are found on the LabVIEW Zone.
 
The attached template has the required inputs and outputs for testing.  If you don't use this template, I will not be able to test your submission.
 
I will answer any questions about the challenge on this forum.  Please post your questions here and don't email them to me.
 
Once there are a few submissions, I will start posting the current standings and update them frequently.
 
Can you be the biggest loser?
 
Bruce


Tic Tac Toe Template1.zip:
http://forums.ni.com/attachments/ni/170/181709/1/Tic Tac Toe Template1.zip

You should be able to find it <a href="http://forums.ni.com/ni/board/message?board.id=BreakPoint&amp;message.id=359#M359" target="_blank">here</a>, but as Altenbach pointed out, it's a  lousy joke. If this is an example of classic french humor then the french should probably stick&nbsp;with making&nbsp;food.
P.S. As I mentioned in the last thread, I like this challenge. If I have time I might even take a shot at it.

Thanks for the link tst... Have to admit that this is typical french humour - which indeed is terrible :smileysad: - but let me had that despite my frenchness (not my fault, I got it from my parents ;)) I do understand and prefer from far english humour.- 
L'humour anglais souligne avec amertume et d�sespoir l'absurdit� du monde. 

 - 
L'humour fran�ais se moque de ma belle-m�re.
 Pierre Desproges (very famous french funny guy with very sarcastic sense of humour);)

JoeLabView wrote:
 ======== Now where did I put that Tool Palette!!???!!! ======== 

I think you left it right under your CVI workspace. :smileyvery-happy:Talk about a desktop metaphor... :smileywink:

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

- Is it always a draw under optimal play? (I think there are final boards possible with not even any 3 in a row)

- Can X force a win?

- 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. ;)
 

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 ?
 
<img src="http://forums.ni.com/attachments/ni/170/181875/1/TTT.png"> 
&nbsp;

Seems that this challenge will be fun ! I have already lost a couple of hours. 
&nbsp;
Thanks Bruce !
&nbsp;Message Edit� par chilly charly le 04-27-2006  05:32 PM


TTT.png:
http://forums.ni.com/attachments/ni/170/181875/1/TTT.png

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? :o Is the game flawed??? We'll see. ;)

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. :D
This is a bit confusing. The program should display the looser after the game has finished, right?

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

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 :smileywink::smileyvery-happy:
Just my thoughts ... since I have no time for coding... Have FUN    
 

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. :D
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. ;)

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

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.

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

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?
<img src="http://forums.ni.com/attachments/ni/170/182428/1/UniqueTics.png"> 
&nbsp;Message Edited by altenbach on 05-01-2006  01:26 PM


UniqueTics.png:
http://forums.ni.com/attachments/ni/170/182428/1/UniqueTics.png

CC
Is you entry trying to loose or trying to win here? ;)

Neat challenge!  However, looking at some people's results vs. the random player makes me wonder if having each opponent pair play only 2 matches is really enough.  If either player uses a non-deterministic algorithm, I'd think you'd need to run many matches to more accurately determine whether one's a better loser than the other.
I've got an algorithm in mind that's conceptually pretty simple, but which is liable to give an equal rating to several possible "next plays".  In such cases, I'd just pick randomly from the otherwise-equal possibilities.  If there's a subtle flaw or subtle advantage in this approach when playing against a deterministic algorithm, it's highly unlikely to show up in just 2 matches...
I also wonder about the scoring.  It sure seems that most decent competitors will almost always play to a draw.  Let's just suppose there ends up being 20 entries that always draw against each other, and never "lose" to anyone by making their own 4-in-a-row.   Their "win" total will then come from the weaker competition, and the contest is mostly determined by matches with the weaker players rather than matches with stronger players.  Sorta like having the NBA championship determined by who had the best record against the Knicks.
I'd kinda like to see more than one champion category.  Easy for me to say since I don't have to perform the matchups or evaluations...
1. Simple scoring system (similar or same as original), tiebreaker based on some kind of efficiency metric that considers code size, memory used, execution speed, whatever else.
2. Raw strength - each player matches up >100x with each other player.  Result should be more statistically significant.  Tiebreaker -- ?
3. Generalized algorithm -- based on results facing off against other generalized players for a variety of NxN board sizes.  (Still based on ending game at first 4-in-a-row).
Finally, since the coding challenge is categorized under "Code Sharing", shouldn't we also have an open-source stage of competition?  Or maybe we can just do it voluntarily in the forum?  I'd like to think of the official contest as the closed-source stage.  Immediately after that, it'd be cool for participants with good / unique approaches to describe their algorithms and post code.  Then the goal is to produce an open source player that beats the original contest winner.
-Kevin P.

Kevin, you raise some interesting points.  I didn't expect the possibility of different outcomes from the same players.  Perhaps I will put a loop in so each match is played 100 times as you suggested.  The scoring system is designed to be automatic, so I don't have to set up every match.  Another possibility is running each player against the random player a million times or so to see how they do.  Then we could have a tie breaker for all the ones that win or draw 100% of the time.
 
I considered using a different size board as a tie breaker, but that makes the original problem much more complex if you have to be able to play any NxN grid instead of just a 4x4 grid.  I would be open to using a different tie breaker if we could reach a general consensus on what it should be.
 
I really like the idea of an open-source version after the official competition is over.  I would even be able to work on that one, since I can't compete in my own contest.  I won't complain if people chose to share their strategies during the competition, although that is likely to hurt their own entry.
 
One of my concerns is that I want this competition to be something that any LabVIEW programmer could do well at.  I think with a little work, many people could come up with a decent player.  I don't want to limit it to the expert programmers only.
 
Let's see how the competition progresses before we start trying to change the rules.
 
Bruce

I thought we needed a better opponent than Bruce random player.
So here is my first unofficial submission. Don't expect too much from it  : it's slow and can be beaten often. But it never loses a game against the random player and doesn't always react in the same way. So I believe it's a fair partner.
I hope you will have some fun with it. Please post your score, comments and publish your own better opponent as soon as possible...
 


Tic Tac Toe CC ref.llb:
http://forums.ni.com/attachments/ni/170/182662/1/Tic Tac Toe CC ref.llb

altenbach a �crit:...Could you post them with a passworded diagram (instead of removed diagram). I cannot open them in LabVIEW 8.0 where I develop.


Sorry Christian, I never remember the pro or cons of diagram removal !Here is a more compact, password protected version (7.0).
Since it is slightly different from the previous one, please use this last version  as provisionnal reference instead.

Some scores, averaged for 100 plays, and calculated according to the challenge rules (2 for a win, 1 for a draw) :

CC ref player against the random player : 198 as first player, 188 as second player
CC ref player against himself : 108/92
My own score, against the CC ref player : 152/108


Tic Tac Toe CC Folder.zip:
http://forums.ni.com/attachments/ni/170/182702/1/Tic Tac Toe CC Folder.zip

This will be my last entry for a few days.
Although I don't think that I have run on the right direction, my best score against the ref player is now 176/150. Try to beat this !
Hope I'll be able to enjoy your own progress. Good wiring !
 

Shane,
 
Here is a  6.1 version. Not sure it's working.hope to see your contributions soon !Message Edit� par chilly charly le 05-03-2006  12:07 PM


Tic Tac Toe 6.zip:
http://forums.ni.com/attachments/ni/170/182729/1/Tic Tac Toe 6.zip


Tic Tac Toe CC ref.vi:
http://forums.ni.com/attachments/ni/170/182729/2/Tic Tac Toe CC ref.vi

Bruce Ammons a �crit: ... Kevin, you raise some interesting points.  I didn't expect the possibility of different outcomes from the same players.  Perhaps I will put a loop in so each match is played 100 times as you suggested.  The scoring system is designed to be automatic, so I don't have to set up every match.  Another possibility is running each player against the random player a million times or so to see how they do.  Then we could have a tie breaker for all the ones that win or draw 100% of the time...


Bruce and Kevin,
One possible approach is to evaluate the way the opponent is playing the game, and to adapt one's strategy accordingly : I believe there are some ways to always end up with a draw against strong opponents. However, using systematically this attitude would be a mistake against weaker opponents, against which a winning strategy could be applied. Of course, this requires a few runs before deciding which is the best approach. So I vigorously sustain Kevin's suggestion to score the players after a significant number of runs. I'll post my first submission as soon as the evaluation details will be decided.
Bruce, why do you think you can't compete ? Even if you can't pretend to be ranked as a normal competitor since you'll have access to other's code (although that's not mandatory), I think  you shouldn't remain a "passive" observer... ;)

Very nice CC!
I have lots of improvements to do!  ;)

I should be able to post something up tonight.  I threw some stuff together quick last night and faced off with CC ref.  As 1st player, I "succeeded in losing" slightly less often than CC.  As 2nd player, I got trounced.  With one extremely minor tweak in my evaluation function, I was able to only barely get beat as 2nd player.  When I was 1st player we had a dead heat.  I let it run for hours and we had over 2.5 million draws with no victories either way.
I have rethought my evaluation function a bit, and I plan on trying some new weightings that (for the moment) seem to make a little more sense.   As I considered more specific scenarios, I realized that I as a human would have occasionally chosen differently than my algorithm might.  I'll try to fix that tonight, and then I'll see how good my intuition is...
Bruce -- heartily agreed that we should let the comptetion progress a bit before tinking with rules / scoring.  I think some tweaks *will* be helpful, but I'm not prepared to argue exactly *which* tweaks will be best.  Further discussion here should hopefully start leading to some fair degree of consensus.   I also support your goal to make this competition one where people can do well without being LabVIEW experts.  As many of us are seeing, it isn't terribly hard nor does it take very long to hack up a pretty decent algorithm.  Hopefully that'll result in dozens of entries and a very lively competition / discussion.  With several past challenges, I would tinker a bit but generally abandon the effort before completion due to time constraints.  The couple I saw through to completion *did* require quite a bit of time, and the winners clearly needed to call on their in-depth LabVIEW expertise.
Extremely vague outline of my base concept: Consider all possible plays, perform an evaluation on them, select the "best" play.  If there are several that tie for best, pick one of them at random.  At this point, the evaulation is purely static, based only on the current state of the board.  No trending from the past and no predictions of the future.
Other vague thoughts: may want to break down algorithm somewhat like chess -- one algorithm for the opening, something different for the mid-game, and yet something else for the end game.  My approach "feels like" more of a mid-game algorithm and is probably not too bad for openings either.  I'll probably mess around with some different endgame ideas though.
Ta ta for now,
-Kevin P.
 

Kevin Price wrote:

I should be able to post something up tonight.  I threw some stuff together quick last night and faced off with CC ref.  As 1st player, I "succeeded in losing" slightly less often than CC.  As 2nd player, I got trounced.  




I achieved similar results. 
With a minor tweek, his winnings increased by 10%, which is still far away if he is the 1st player. But improved by approx 20% if he is the 2nd player.   But twice as many draws (which is still insignificant...).  I haven't spent much time developing a gaming strategy, but thank you CC for setting the initial bar!  (you deserve many stars for that).
R.

Kevin,
Nice infos you found on the web ! The similarity between the RPS and the TTT chalenge is striking ! That's exactly the conclusion I reached experimentally after playing a while with the ref and random players.
I observe that you choosed a "secure" strategy in your own KP2A vi, preferring to reach a draw against  a serious opponent than winning against other weak players. Now you'll have to find a way to detect rapidly a weaker player... :)
Another possible way to rank the different strategies would be to evaluate the performances in problem solving. For instance, compare the various vi players against CCref, using the following initial configuration,  XX O  OO  O XX
 The result is very interesting ;) While Bruce random player manages to win a few games (when playing second), KP2A and CCref always reach a draw. Never lose... but never win either !..  As a matter of fact, with the proposed configuration, the first to play should always lose against an advanced player (can you demonstrate this statement ? ;)). Means that KP2A and CCref are quite far from optimality ;) :D
So there is a lot of room for improvements and I would like to see some contributions from other competitors. Christian ? Ben ? Tst ? Shane ? JLV ? What are you preparing in the dark ?
 

chilly charly wrote:

I would like to see some contributions from other competitors. Christian ? Ben ? Tst ? 


You can all relax. I'm not preparing some secret algorithm which will blow all of you out of the way. :smileywink:
Unfortunately, I know that if I even look at this I will be forced to keep going and I don't have the time. I started doing some checks when Bruch initially brought this up but haven't even got to have a working version. Looks like I'm going to have to sit this one out as well. :smileysad:

chilly charly wrote:

Christian ? Ben ? Tst ? Shane ? JLV ? What are you preparing in the dark ?



I actually submitted a very dumb but simple and fast algorithm to Bruce a few days ago. It is so dumb that it does not even look at the pieces of the opponent. :o Maybe I can convert it to 7.0, remove the diagram and post it so you guys with the fancy algoritms can be proud of yourself. :)
At the moment, I don't have any time to work on these things but I have some ideas for much stronger tic DAQtac toe code... ;)

OK, as promised, here's my first draft (LabVIEW 7.0, passworded).
Have your players chew it up and spit it out! :o Have fun. :D
Be warned, I'll be back !


TTTAltenbach001.vi:
http://forums.ni.com/attachments/ni/170/183197/1/TTTAltenbach001.vi

Christian,
Thanks for this most interesting entry ! Actually, I didn't understand immediately what was going on there ! :D:D
 
OK, back to serious things now.
After some tweaking of the CCref player parameters, here is what I have obtained : the Deep Toe player. I believe it might well win against any opponent : Deep Toe never loses a game and scores
- 198/195 (first/second player) against the random player
- 162/182 against CCref
- 102/123 against KP2A
In the O-ring problem solving (see (and study...) my previous post), it even scores 200/200 ! :O
 
Since it would definitely kill the challenge, I promize solemnly not to submit it to Bruce ;) :D:D:D


Deep Toe.vi:
http://forums.ni.com/attachments/ni/170/183222/1/Deep Toe.vi

chilly charly wrote:
Damn'it... je suis d�couvert ! :D:D:D


It really never had a chance on my tester:
<img src="http://forums.ni.com/attachments/ni/170/183393/1/CCDisqualified.png"> 
Of course Bruce's tester allows even the following player code to always "loose", the minimalistic Deep Toe:
<img src="http://forums.ni.com/attachments/ni/170/183393/2/DeepestToe.png"> 
&nbsp;Message Edited by altenbach on 05-05-2006  01:35 PM


CCDisqualified.png:
http://forums.ni.com/attachments/ni/170/183393/1/CCDisqualified.png


DeepestToe.png:
http://forums.ni.com/attachments/ni/170/183393/2/DeepestToe.png

I don't get what chilly is thinking.
about the scoring, i guess every player plays with everyone else including the random player? (how many matches).

chilly charly wrote:

For instance, compare the various vi players against CCref, using the following initial configuration,  XX O  OO  O XX
 The result is very interesting ;) 
So there is a lot of room for improvements and I would like to see some contributions from other competitors. Christian ? Ben ? Tst ? Shane ? JLV ? What are you preparing in the dark ?



Yes...  This is the first trick that I implemented..  By the looks of it, you also appear to start with a similar pattern, with a preference with the rightmost "O".  I modified my vi to block your moves...  But I have not yet had time to implement suffisticated algorithms, so your vi wins (or rather loses) most of the time.  However, I managed to increase the number of ties.  
I will probably post an example as soon as I get decent number of loses.  ;)
Once again, thanks CC for setting the bar. 
Ray

Altenbach,
We draw every game...
<img src="http://forums.ni.com/attachments/ni/170/183581/1/altenbach.jpg"> 
And CC's get's 80+ wins when running first, and ~5 wins if starts second.
Now... why does a CC loss (win) count as a draw????&nbsp;
I'll try to attach pictures
<img src="http://forums.ni.com/attachments/ni/170/183581/2/what%20the%20TTT.jpg"> 
&nbsp;
&nbsp;Message Edited by JoeLabView on 05-08-2006  01:20 PM


altenbach.JPG:
http://forums.ni.com/attachments/ni/170/183581/1/altenbach.JPG


what the TTT.JPG:
http://forums.ni.com/attachments/ni/170/183581/2/what the TTT.JPG

JLV,
I have to confess that I didn't understand a piece of your last post ! Seems that I missed a few posts or is that a "private" discussion with Christian ?

JoeLabView wrote:

Now... why does a CC loss (win) count as a draw???? 


This looks like an illegal position. SInce X always starts, the number of O on the board must be the same as the number of X or one less.
 
What do you use for scoring?

cosmin a �crit: ... I guess the weaker players will make the winner.

Assuming player A is better than the other players, then it can be demonstrated without too much suffering that the other players are weaker than player A. So, you are right, the weakers make the winner... ;)  There are also some stories about bottles half-filled or half-emptied... :D
 
I offer again my idea of evaluating the vi-players for problem solving. Apart the O-ring already described, for which the second player always wins, there is also the checker board (always draw, but that can be tricky...)
XX..
XX..
..OO
..OO
 
The S-fence :(the second win or draw)
X..O
X..O
X..O
....
 
The A-fence (the second win or draw)
X...
X..O
X..O
...O
 
The Vee (always draw)
X..O
XO.
OX.
....
 
Some scores :       CC-ref(1) / KP-2a(2)
O-ring                   100 / 
Checker board            200 / 0
A-fence                  100 / 100
B-fence                  100 / 100
Vee                      100 / 100

And of course, the tab bug striked again, and then the 5000 chars limit swallowed my post... >:(
 
Bah, on y verra plus clair demain !
 

Scoring is an issue that remains to be settled.  Right now, I think I will play each player against the others 100 times each as X and 100 times as O.  For ties, I will probably run eacb player against the random player a million times or so.  If there is still a tie, I will run a player against itself a million times or so and calculate its average playing time, and the fastest player will win.
 
Bruce

The fastest player.
:D
Sorry for the confusion CC.
I'm ... humm...  There's a delay in my posts...  It refers to older posts..    I'm stuck in a time-warp, and my guess is that this reply is not helping, either.
 
So let me try again...  
I'll start with Christian:  When playing against him, we always draw.  Regardless of who is first.   There seem to be few patterns emerging from the contest, the X & O's pretty much start off the same way (predicatable).
CC:  I am still using your baseline.  I added a feature to minotor cheating.  It's included in the original vi tester.  The reason for the illegal move was an error on my part.  I forgot to change the numeric reference when switching first player...  oops!! :o
I will "test" some approaches using the original baselines from you & Christian.  I will post a baseline if (hopefully when) I loose more often..   However, you beat me to the punch when considering loosing strategies...  I will be considering two approaches: defensive (blocking other player's anticipated moves) & offensive (trying to force player to a move). 
JLV
 

Altenbach,
I must apologize: after JLV last post, I have understood that I also made a mistake while using your 001.vi. I probablyI forgot to wire something, and your vi just aligned always 4 pieces in the first row, whatever was played by its opponent !:D
In the context, I thought that it was just a pleasant joke, able to entertain the community, which in turn gave me the Deep Toe idea. Sorry ! :)
Thanks to JLV for returning me to the right track.

altenbach wrote:
<img src="http://forums.ni.com/ni/i/icon_rating_5.gif">  Now take a break and listen to <a href="http://www.dukesofted.com/" target="_blank"> The Dukes of Ted! </a><img src="http://forums.ni.com/ni/i/icon_rating_5.gif"> 


I guess they are fans of Bill &amp; Ted's Excellent Adventure.
Excellent! :smileyvery-happy:

Ask about the tall one in the back.
 
Ben

Ben wrote:

Ask about the tall one in the back.


O.K.
Is the tall one in the back Mirco? And who is Mirco, actually? A son? A nephew? A brother?
P.S. I like what I heard so far.
P.P.S. Bruce, sorry for hijacking the thread, but I haven't had time to examine the VIs and I can't really understand anything from the posts, so it's really rather boring. :smileywink:

tst wrote:And who is Mirco, actually? A son? A nephew? A brother?


(He's my youngest son. :))
Now, to stay on topic here, I have to convince them to write a LabVIEW and tic toc toe based song. :D
Refrain:tic.. the FOR loop spinstac... the data flowstoe.. you loose!

altenbach wrote:
(He's my youngest son. :))

Yes, the hair is a dead giveaway :smileyvery-happy: .

Seems that the excitement is decreasing. Are the thread and challenge already dead ?
Just to entertain you, here is a new random player. Bruce's was pretty dumb ;). I mean it never hesitated to align 4 spots. This one avoid suicide until forced to. I learned a lot from it.
 


TTT better random player1.vi:
http://forums.ni.com/attachments/ni/170/184243/1/TTT better random player1.vi

From my end it is always the same thing.... lack of time...  :|
---work--work--work--work--work--work---  ---sigh--- :(
I even read the postings @ every 2nd line..  YIKES!!  (ok, it shows!)
 

Re: Shane's "Ultraconservative", never-lose-as-O player.
 
I was doing just a little bit of playing around with a test program that allowed me to change players in the middle of a game, or start the board off in a pre-set pattern.  My basic goal was to detect scenarios that led to my own player (KP2a) getting forced into 4-in-a-Row, and to trace through the play history to try to figure out which turn led me astray.  Then I'd also put the other players in that scenario and observe them trying to avoid a forced 4-in-a-Row.
 
So anyway, there were some fairly early board scenarios that made Shane's "Ultracon" player do very poorly as O.   So poorly that it was forced into 4-in-a-row EVERY TIME, which was even worse than the Random player.  On the other hand, when Ultracon played the entire match, I never saw it forced into 4-in-a-row.  Strategic lesson: staking out a good early position can be crucial to an algorithm's success.
 
BTW, I noticed that I made a mistake implementing KP2a.  The actual results of my evaluation function weren't what I had intended on paper.  Turns out that what I intended performs considerably worse! :smileyvery-happy:  A bunch of other little tweaks I've tried that seemed intuitively like good ideas have also turned out worse.  So much for Murphy's Law...
 
 
-Kevin P.

chilly charly wrote:

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


It is very well alive. I have a couple of very interesting things in the oven but at the moment I am busy with real work.
Still, I am very proud to say that I have fully analyzed the 0x0, 1x1 and 2x2 boards. :D

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.

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.
 

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

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.

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!):

- Checker board (100% draw)
 
- S-Fence (100% draw)
 
- A-Fence (100% draw)
 
- 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).
<img src="http://forums.ni.com/attachments/ni/170/184759/1/DeepestToePlayer.png"> Message Edited by altenbach on 05-14-2006  09:59 AM


DeepestToePlayer.png:
http://forums.ni.com/attachments/ni/170/184759/1/DeepestToePlayer.png


TTT_Altenbach.zip:
http://forums.ni.com/attachments/ni/170/184759/2/TTT_Altenbach.zip

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..  :o  But this is definetly an interesting challenge and fun to read the postings!!  :)
JLV

Seems that Altenbach designed the optimal player. Thumb up. :) >:( :D
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.

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. :D So who can make the fastest and smallest! :o

- 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??

I can't resist :


altenbach a �crit: ... Since we know that all boards with up to five pieces are a draw...


WRONG  ! There is one situation where X lose at his third move...Therefore "all boards with up to four  pieces are a draw" ;):D

CC & Altenbach have w-a-y too much (free) time on their hands....  ;)
sigh :| 

Chilly, I guess I am missing your point.  It takes four marks in a row to "win" the game, so how can the game be over after the third move?
I won't change the template for the official competition.  Nothing says you have to use all the inputs provided, though.  They just need to be there so they fit into the tester template.
I do like the idea of having to start from random positions.  Even with the first one or two moves given as a random starting place, it would test the ability of the algorithms to recover from a stupid move.  I won't change the original method of play, but perhaps this could be incorporated as a tie breaker instead of fastest player.
Bruce

CC
 
You mean to tell me that there is a position containg two Xs and two Os that is a forced loss for X under the rules of the challenge?
 
Can you loose it against Deepest Toe (set to play to loose)?
 
If this is true, maybe my DT has some serious athletes foot (I did some cuts late in the development so it is possible that a bug snuck in). ;)

altenbach a �crit: You mean to tell me that there is a position containg two Xs and two Os that is a forced loss for X under the rules of the challenge ?



Sorry ! I mixed the relative moves. You are right, only the sixth move (for O) can lead to a loss ! That's the sort of mistakes you do while far from the board. Seems that I'm poor at mental TTT. I should stay with mental chess...
I apologize sincerely. How can I make up for this silly error ? I'm so disturbed now ! How terrible... That's all my fault !!!... Now were did I put that rope ?...

CC wrote
"Now were did I put that rope ?..."
Would you like to borrow mine?*
Ben
Sorry could not resist. 
*Credits: The above is variation on an old Saturday Night Live skit where Eddy Haskle replies to Beever lamenting over not having a gun to shoot himself.
 

chilly charly wrote:



Sorry ! I mixed the relative moves. You are right, only the sixth move (for O) can lead to a loss ! That's the sort of mistakes you do while far from the board. Seems that I'm poor at mental TTT. I should stay with mental chess.

Maybe one of the next challenges will be a LabVIEW based chess player, so this will come in handy. :D


chilly charly wrote:



I apologize sincerely. How can I make up for this silly error ? I'm so disturbed now ! How terrible... That's all my fault !!!... Now were did I put that rope ?...


And I was pretty sure you were just trying to mess with my mind.. ;)
Instead of a rope, you could just use a wire, there should be a spool in the tools palette. (Unfortunaltely, it does not allow you to make any wire loops).

Many thanks to all of you for helping me to solve definitively my shame problem.
So here my method, using only standard LabVIEW objects :
- a tree
- a strong wire
- a loop.
You will notice that the stop button has been suppressed. Of course, when I press the run button, LabVIEW... hangs !
 
Errrkkk...
 
<img src="http://forums.ni.com/attachments/ni/170/185333/1/Hang%20on.png"> 
&nbsp;Message Edit� par chilly charly le 05-17-2006  12:14 PM


Hang on.png:
http://forums.ni.com/attachments/ni/170/185333/1/Hang on.png

Hey Losers,
Just read the challenge and here is my first attempt.
Have only tested it on CC. There is works well.
It is big,fat, slow and coded with extreme haste. Thought I would drop it off so you guys could destroy it.
As far as I know it does not Cheat (No Deep Toe lurking).
I am sure I am going to regret this.
Enjoy!!!!!
J 
 
 
 


Bad Loser.vi:
http://forums.ni.com/attachments/ni/170/188473/1/Bad Loser.vi

ohw313
Nice to to have some fresh air in here. Unfortunately, you forgot to include some subvi(s) and your player can't be tested.

Duh,
oops. Sorry.
Well, At least it would never win then.
Here is complete set.
J


Bad Loser.vi:
http://forums.ni.com/attachments/ni/170/188648/1/Bad Loser.vi


ScoreUS.vi:
http://forums.ni.com/attachments/ni/170/188648/2/ScoreUS.vi

Welcome!
You should probably post your VI in 8.0. If needed somebody with more experience can convert it down to 7.1, just in case you use some fancy 8.0 only features ;)


Daklu wrote:General rules question: Is it legal to retain a history of moves an opponent makes during all games to try and determine what their strategy is? (I don't know if this is even possible...)


I would think this is allowed, but in the competition your player must "play to loose" against opponents he has never seen, so this strategy would not make much sense. ;).

It is unclear whether you have programming experience or not (the source code question, and yes, that it the right term in LV as well. Look <a href="http://www.ni.com/labview/power.htm#3" target="_blank">here</a> for some details), but I'm not entirely sure starting on a relatively large project is the best move. Anyway, you seem to be intelligent, so I assume you'll be able to tell yourself whether this is more than you can handle or not.  
I normally give the following paragraph as a standard reply to newbies -
To learn more about LabVIEW, I suggest you try searching this site and google for LabVIEW tutorials. <a href="http://cnx.rice.edu/content/col10241/latest/" target="_blank">Here</a>, <a href="http://zone.ni.com/devzone/learningcenter.nsf/03f7c60f17aad210862567a90054a26c/55974411828f779086256ce9007504bd" target="_blank">here</a>, <a href="http://www.iit.edu/~labview/Dummies.html" target="_blank">here</a> and <a href="http://www.upscale.utoronto.ca/GeneralInterest/LabView.html" target="_blank">here</a> are a few you can start with and <a href="http://www.fafiles.com/" target="_blank">here</a> are some tutorial videos. You can also contact your local NI office and join one of their courses. In addition, I suggest you read <a href="http://zone.ni.com/devzone/conceptd.nsf/webmain/CB5E46406090C61C86256A7000559B66" target="_blank">the LabVIEW style guide</a> and the LabVIEW user manual (Help&gt;&gt;Search the LabVIEW Bookshelf). 
and it would be nice to have feedback whether those tutorials are actually worth anything.
Anyway, G is a great language and you can find a lot of stuff online, so just start digging, and if you get good at it, come and help at the forums.
P.S. For some fun, go to the <a href="http://forums.ni.com/ni/board?board.id=BreakPoint" target="_blank">BreakPoint</a>.

Daklu wrote:So with that glowing introduction, here's my initial attempt at Labview programming... TOE JAM! 

What kind of file format is this?

I use <a href="http://www.iceows.com/" target="_blank">ICEOWS</a>&nbsp;: free, lightweight and unobtrusive. :) 
Opens ICE,ARJ, ZIP, GZIP, TAR, MS-CAB, RAR, ACE, Quake 3 compressed files, Internet Mail files (Mime, UUE, XXE, B64, HQX), Java Archive (JAR, EAR, WAR), LZS, LZH, LHA, IMP, BZ2, (but unfortunately no 7z).

Daklu wrote:Thanks for the links tst, they look very good. One of the difficulties I have with searching online is that it is a bit hard to find answers to specific questions. Sure I can take it step by step and work through all the tutorials (and I will soon), but it's way more fun to jump in the deep end of the pool and see if I can swim. ;)


Well, as I said, it would be nice to hear whether they're actually worth anything once you go through them.
One of the coolest things about LV is that it's so "easy" that it will allow you to jump using the grownups diving board. Unfortunately, you may find out too late that you can't swim and that the pool cleaning robot is out to get you! :smileyvery-happy: Since you have some programming experience and you don't seem to have trouble with the paradigm shift, you should probably be fine and avoid making most of the stupid mistakes.



Given the size and number of my vi's, I'm willing to bet that my implementation is much, MUCH more complex than it needs to be. C'est la vie. 


100K doesn't look like too much to me. I can't see your code, but too complex is not terrible. Your problem is that you have Altenbach here, who's the master of making things efficient and compact and will probably modify your code beyond recognition just to show you "how it could be done". :smileyhappy:



 My source is there for all the world to see (and mock.)


We would never... :smileywink:

jasonhill wrote:

In my day everyone used .rar because .zip did not support disk spanning.  Do you remember disk spanning? 


Yes, and I also think I remember PKZIP supporting disk spanning on DOS. 
Or are you talking earlier than that?

jasonhill wrote: 
<mode grouch="tech geek">Darn kids. In my day everyone used .rar because .zip did not support disk spanning.  Do you remember disk spanning?  Gaining popularity.  PAH!  Regaining, more like. Fetch me my cane! (and some coffee)</mode grouch="tech geek">


 
Eh, it's a matter of semantics.
 
If something is "regaining" popularity, it is also "gaining" popularity.  Once, again it's a matter of semantics.  In fact, I have indeed used disk spanning with rar, and its disk spanning (well, mainly by file splitting) is still being used today.Message Edited by agill on 06-26-2006  11:13 AM

Daklu wrote:tst, I've gone through the tutorials (mostly skimmed with periodic in depth reading) and the Connexions tutorial is easily the best. It has a good table of contents making it simple to quickly go to the section of interest. The NI tutorial is pretty good too.


In that case, I'll just leave it in its current order. I'll leave the others in just in case real newbies want more tutorials. BTW, if you'll look at the title page of the cnx tutorial, you'll see it was written by NI.
Anyway, your code was almost fully saved (player.ctl wasn't). To save for a previous version, it's probably best to just open the top level VI and perform a save for previous. It should save all dependencies. No need to save it again.
I really don't think anyone would mock your code. I only gave it a quick look, but I can tell you that it looks very good, appears to be relatively well documented, has coooool icons (don't underestimate that, a lot of us would probably prefer spending most of our development time designing cool icons) and appears to be well structured. I can't comment on functionality, but that's already up to you. 
3 points I will make is that those 2 "unstraight" wires in the top level VI really stand out like a clown's nose, that you'd be better off setting the diagram terminals not to appear as icons and that for controls used in more than one VI it would usually be wise to create a typedef.
P.S. Have you seen <a href="http://forums.ni.com/ni/board?board.id=BreakPoint" target="_blank">the BreakPoint</a>? I think you'll like it.

A typedef is a control, not an entire VI. An example of this would be player.ctl, which is a picture ring typedef (I hope). If you wanted to add another kind of player, you would only need to do it once. If it was a regular control (which it might be, I haven't checked) then you would have to go and change it at each place it's used. 
Typedefs make it very easy to work with data through different VIs, because you can keep changing the structure of your data. Enums and clusters work very good with this. Note, however, that if you delete or move stuff in a typedef, LV will try to fix it for you, not always with desirable results and you may not be alerted to it, so you should try sticking to only adding stuff to typedefs, unless you're ready to go through your entire code and make sure it's still OK.

I ran each player 500 times as X and 500 times as O against each of the other players.  I did two runs, one with the random players and one without.  The scores are:
 
No Random Players:9906 ohw3139894 Dan Marlow9888 Toe Jam9776 CC ref9612 KP2a9598 Ammons9127 Opus 16656 Shane6543 Altenbach001
With Random Players:13745 ohw31313617 Dan Marlow13548 CC Ref13410 Toe Jam13405 Ammons13042 KP2a11489 Opus 19113 Altenbach0018820 Shane6312 CC Random4499 AE Random
Perhaps this will get the discussion going again.  Right now, I would say the lead is clear enough to not require a tie breaker.  For the final scoring, I will increase the number of times the game is played against each player.
 
Bruce

HI Bruce,
Thanks for the results.
Just a little unsure of what the score is. You say each players plays 500 times against all others as X and then 500 times as O.
So, with 9 players each player should play against 8 opponents(I.e. 8000 matches)
Is the score then the amount of times the player wins or loses?
Sorry for the confusion.
 

ohw313 a �crit:
...Maybe they are holding back until the closing date and not show all their cards to early...

:)

Trust me, I am just as surprised as you.
I always want to take the time to write something good for a Challenge but never find the time.What I sent it was a off the top of the head idea coded with "extreme haste".Only tested it with random players and there it worked well. 
 
I really expected the likes of Albenbach and Shane to destroy it.I am truely baffled.
Maybe they are holding back until the closing date and not show all their cards to early.
 
I am busy rewriting my code and making improvements.I expect the final result will be a reversal of fortunes.
 

ohw313 wrote:
I really expected the likes of Albenbach and Shane to destroy it.


The only Al...bach entry that Bruce currently has is my first instant sketch with code roughtly the size of a postage stamp and virtually no strategy. ;)
I'm so proud of my baby because it did not make any illegal moves so far! :o It's also blazingly fast!
 
Bruce, I wonder if you have any speed statistics on all the entries? I wonder how slow the top entries actually are. How about total code size?
 
 

I could provide details for every match between players, but I am reluctant to provide them.  For the final results after the competition, I will gladly provide everything in a spreadsheet.
 
I will say that for a majority of the matches, it was 100% draw (or win/loss).  Only the players with random components made a difference.  If I narrowed it down to the top players and reran the scoring, it would most likely be 100% draw and I would have to go with a tie breaker.  I prefer the current scoring since I don't have to do a tie breaker.  I feel the ability to play against the players with random components is an adequate score differentiator.
 
I am looking forward to seeing new and improved routines to see how things change in the final scoring.
 
Bruce

Since players with random components are precious for evalution, here is an another one. It's only an optimized version of the CCref player, with a tuned evaluation function. Should be as fast (means faster than Altenbach player...;)), but I probably made some mistake while converting it to LV7.1. I'll check that later.
 
On average, it scores 162 over 200 against the original CCref. On Bruce scale, I think it should rank first.
 
I felt it would not be fair to hide it from the community. So now you have some time left before the 12th to improve your own player.
 
Enjoy !
 


Tic Tac Toe CC ref2 Folder.zip:
http://forums.ni.com/attachments/ni/170/193373/1/Tic Tac Toe CC ref2 Folder.zip

Hi all, 
I send here a software wich you can use to challenge other player algorithms
Have Fun


TicTacToe.zip:
http://forums.ni.com/attachments/ni/170/194868/1/TicTacToe.zip

Everybody,
Remember there are only&nbsp;a couple of days left to submit your solutions.&nbsp; The deadline is midnight Friday!&nbsp; You can email them to me (<a href="mailto:tictactoe@ammonsengineering.com" target="_blank">tictactoe@ammonsengineering.com</a>) or post them here. 
Thanks,
Bruce

Ahh these stupid deadlines! Why does it always have to be Friday night, robbing us of a nice relaxed weekend of tinkering? ;)
 
I don't have time to do anything beyond of what I already have, so I just need to package it up and send it to you. Basically the core of "Deepest Toe" with a few tweaks will probably be my entry.

I would be fine extending the deadline to Sunday night.  Everybody gets one last weekend to tinker!
Bruce

Kevin,
 
That's exactly what my ref players do. No wonder that they were on a par when playing against each other. I guess a majority of submissions have adopted a similar strategy. I'm waiting eagerly to see how Christian's player, whith it's fully deterministic approach, is doing against all the "advanced" random players.

Sorry CC, I have to disappoint you because I could not get my entry in. I probably needed about one quiet quality hour over the weekend to consolidate my code, but we had a huge BBQ with about 30 people at my house and I had to man the grill, do lots of shopping on Saturday and do all the logistics.
LabVIEW wise, I am busy preparing for NI-Week, so this has priority. :)
However, my code is radically different to what we've seen so far and I am actually quite proud of some of the routines and optimizations. For example I was able to reduce the time for the exhaustive recursive scoring of all possible positions from initially about 40 minutes to well under one minute. I think my latest version took about 40 seconds on my old laptop to generate all possible legal unique positions from scratch and score them recursively. Also all the bit-level operations and symmetry tranformations seemed quite efficient at the time. :)
The main slowdown was caused by "search array" on the huge database for each lookup. Of course it can be replaced by much more efficient code if you know that the array is sorted. :)
Maybe we can revisit this in a few weeks.
The basic player would do the following:
It might do the scoring database on the first call, or include it in a diagram constant. It's only a few MB.
Now generate all posssible moves in the current position and score them as follows:

- If there is a move that forces a loss, play it. (or pick the quickest if there is more than one).

- if the best is a draw, pick all drawn positions and move such that if all remaining empty fields were ocupied by the opponent, we have the largest number of potential win positions for the oppenent. (Just invert the board containing my own pieces and count the rows of four). Statistically, we give the opponent more ways to win!

- (we don't have to worry about a position where we are forced to win, because It can never happen if we follow 1&2).

The position is held in a single U32, with each 16 bit half the white and black position, respectively. All transformations (rotate, mirror) and the bit counting are in 16bit lookup tables, generated on the fly on first call.
For example for the unique transform, it generates the 8 possible versions, then picks the one with the highest U32 value (See image). This is the only position that is kept in the scoring table.
<img src="http://forums.ni.com/attachments/ni/170/196084/1/TTT-transformLookup.png"> 
&nbsp;Message Edited by altenbach on 07-18-2006  09:22 AM


TTT-transformLookup.png:
http://forums.ni.com/attachments/ni/170/196084/1/TTT-transformLookup.png

Christian
 
Talking about strategy, I tried to develop my own "absolute" player. With a somehow different idea in mind : since my advanced random player was quite good in solving say 99 % of the positions, and quite rapid at that (3 times faster than your provisionnal player ;)) I thought that only a quite short exception table would help it solving the remaining 1%. So the challenge was to build a table with all the possible wining or losing moves, then to delete all the positions correctly analysed by the player. My estimate was that a 100 kbytes array would be large enough. This would garantee a fast search. I also had the positions coded on a U32, but I choosed to keep the lowest values !...  The rotate and symetry were replaced by 4 transpose and symetry operations. 
Additionnally I thought that the games where a win was obtained before the last move were not worth studying, since these situations were typical of a weak opponent, already easily handled by my own player. I ended with 3 arrays, containing 688 even positions, 332 O wins and only 67 X wins, and proceeded to generate my data base...
 
Then my "ideal" player would do the following:
 
1- Search the data base and see if the position has been recorded.
If so :
1a- If there is a move that forces a loss, play it. (or pick the quickest if there is more than one).
1b - If there is a move that forces a loss, avoid it and proceed using the "advanced random" player guess
2- If not, proceed using the "advanced random" player.
 
Nice plans...
 
However, my code to recursively select the win/lose/even moves failed lamentably ! :( :D
 
If you leave me some time, I'll probably try to find the bug and finish the job. Some time means several weeks, since I'll be again out for a few weeks, starting next monday (rambling in the Pyrenees again... :)). So you have plenty of time to sharpen your own player...
 
So, my official entry to the challenge is a player slightly better than the CC ref2 in the worst case, and probably perfect player in the best case. Even in the worst situation, it always win as X against ohw313 :)
 
Of course I'll discuss the idea of worst and best situations later. ;)
 

chilly charly wrote: 
... and quite rapid at that (3 times faster than your provisionnal player ;)) 


Well, my provisional player is slow because it operates on the original board array, not on a U32 representation of the board and does real multiplications on arrays!
Just for kicks, here's Altenbach001 without password (LabVIEW 7.0). It is really dumb. Basically it gives itself an exponential penalty based on the total number of 1, 2, 3 in a row, nothing more, nothing less. It does not even look at the position of the opponent. :D
My database is really stripped down and only contains positions that can actually occur in a game AND that are decisive. All drawn positions are left out. I was also playing with the thought of only keeping "difficult" positions in the table and let the rest be handled with a simple algorithm.
 Message Edited by altenbach on 07-18-2006  03:07 PM


TTTAltenbach001.vi:
http://forums.ni.com/attachments/ni/170/196181/2/TTTAltenbach001.vi

jasonhill wrote:That does have a password. :robottongue:

Try again! :D

RESULTS!!!!!
I finished analyzing the results, and it was very, very close.  Each match was played 1000 times, and I ran the test several times.  Each time the results varied slightly, but the order was always the same.
The official winner of the tic tac toe challenge is Chilly Charly with his CC ref 2 player!!!
In second place is Adrien LeMeur.  Adrien's score is only 0.07% behind first place.  If I could declare two winners, I would.
The next few places go to Dan, ohw313, and Kevin Price, all with scores in the 39000 range.
Here is the score breakdown:
39970 CC ref Player 239939 LeMeur Adrien39735 TTT Dan39106 ohw31339088 Kevin Price 2b38254 Ammons37668 CC Aikido Player37545 Toe Jam37462 Kevin Price 2a35986 CC ref Player33258 Opus 126149 TTTAltenbach00125618 Shane Oneill15943 cosmin15626 CC better Random10653 BAA Random
Happily, everybody beat the random player as well as Charly's random player.
I have attached an Excel spreadsheet with all the scoring details for each match.
Good job everyone!  We had a lot of fun with this challenge.  Look for the next challenge coming soon.
BruceMessage Edited by Bruce Ammons on 07-19-2006  11:21 AM


Score Details.xls:
http://forums.ni.com/attachments/ni/170/196350/1/Score Details.xls

Cosmin,
May be you could publish your vi so others could test it :)

Hi,
Bruce ideea is excellent, so anyone can see the mystakes that were made, maybe i made some mystakes with my tester (when i get some time, i will lookk again in it). Since Bruce will post all entries, i will not post my sol.
 
cosmin

hi,
god damm a found the error?????????????, it's in my player, i have a vi with is called my recursion, ttc_recursion3.vi, but in the code in the Open VI Reference.vi, the path is wired ttc_recursion.vi, so is not working (in the rush of things is apparent i put the number 3 at the end of the name?????). Bruce , please test my player by open the ttc_recursion3.vi and put the number 3 at the end of input to Open VI Reference.vi and browse again to the same vi in the input type specifier (not to get the connector pane error).
cosmin


ttc_recursion3.vi:
http://forums.ni.com/attachments/ni/170/196943/1/ttc_recursion3.vi

Hi all, I'm adrien
I send here my bruce submission wich you can use into your tester.
In your tester use RoxallMain.vi
bye


LeMeurAdrienSubmission.zip:
http://forums.ni.com/attachments/ni/170/196944/1/LeMeurAdrienSubmission.zip

Adrien
 
Thanks for making your vi public. 
Remember to adopt the reference connector pane provided by Bruce, otherwise your player can't be tested automatically.
 
Now I can further optimize my own player... ;)
 

Attached is the player (LV 7.1) I used to develop all my different players. I hope the comments will be enough to exposed the adopted strategy.
Open the CC test globals to play with the evaluation grid settings.
I suppose a better optimized grid will be developped once all the players have been disclosed, 
 Message Edit� par chilly charly le 07-23-2006  04:10 PM


CC test player.zip:
http://forums.ni.com/attachments/ni/170/196954/1/CC test player.zip


CC test player.zip:
http://forums.ni.com/attachments/ni/170/196954/2/CC test player.zip

Cosmin,
I tried the fixed version of your program.  It runs much, much slower but it would have won.  It even beat Charly's fixed Aikido player.  I only ran 10 matches against each player, but your player scored 425.  Charly's fixed Aikido player was second with 420.  I'm not sure if this is a large enough sample, but I didn't want to wait any longer.
Sorry that your bug wasn't found before the competition officially ended.  I guess you will just have to be happy with the knowledge that it would have won.
Bruce

Bruce,
From now on, I will read my yahoo mail every day, you dicovered that is something wrong with my player immediately.
cosmin

Guys,
 
I noticed that I never showed my code of the TTT trainer that I only provide as an executable long ago.
 
<a href="http://forums.ni.com/ni/board/message?board.id=170&amp;message.id=184759#M184759" target="_blank">http://forums.ni.com/ni/board/message?board.id=170&amp;message.id=184759#M184759</a> 
&nbsp;
<img src="http://forums.ni.com/attachments/ni/170/184759/1/DeepestToePlayer.png"> 
&nbsp;
For those who are interested, here's one of the latest incarnations from last August. It is still in LabVIEW 7.1. Unfortunatly, I no longer have 7.1 installed, else I would have added a few comments for those interested.&nbsp;(I don't need them because the code is pretty obvious to me ;))
&nbsp;
Of course the scoring tables were generated elsewhere and only show as diagram constant.
&nbsp;
Enjoy! :)
&nbsp;
(I am sure it is still&nbsp;buggier than an ant farm. Try to find all the bugs ;))
&nbsp;


TTT-Trainer3.zip:
http://forums.ni.com/attachments/ni/170/247044/1/TTT-Trainer3.zip