Tic Tac Toe Coding Challenge

[altenbach]

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:

1. If there is a move that forces a loss, play it. (or pick the quickest if there is more than one).
2. 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!
3. (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.

Message Edited by altenbach on 07-18-2006 09:22 AM

[chilly_charly]

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 ! 😞 😄

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

[altenbach]

---

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

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

[jasonhill]

tease.

That does have a password.

[altenbach]

---

@jasonhill wrote:
That does have a password.

---

Try again! 😄

[Daklu]

My ideas for 'Toe Nail' were very much along the same lines as altenbach and cc. Same as you two, I encoded the board as a 32 bit number, except I think I used an I32. Also, I wasn't clever enough to split the I32 into two 16 bit board positions. I rigged up a trinary (3 state) encoding system instead of using binary (2 state) encoding.

I had worked out all the transformation sub VIs because I wasn't smart enough to think of a lookup table. My overall plan was -

1. If there is a path to a forced loss, chose it.
2. In all other cases, choose the path that has the highest percentage of forced losses to maximize the opponent's chance of winning.

Unfortunately I ran into a brick wall when I was trying to figure out how to recursively create a search tree in memory. I have no illusions that my program would have been fast enough to be usable had I been able to finish it, but I would have liked to have learned how to do it.

Message Edited by Daklu on 07-18-2006 08:21 PM

Message Edited by Daklu on 07-18-2006 08:21 PM

[BruceAmmons]

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 2
39939 LeMeur Adrien
39735 TTT Dan
39106 ohw313
39088 Kevin Price 2b
38254 Ammons
37668 CC Aikido Player
37545 Toe Jam
37462 Kevin Price 2a
35986 CC ref Player
33258 Opus 1
26149 TTTAltenbach001
25618 Shane Oneill
15943 cosmin
15626 CC better Random
10653 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.

Bruce

Message Edited by Bruce Ammons on 07-19-2006 11:21 AM

[cosmin]

the results puzzles me, maybe in the rush of things I made some mistakes with my tester, I got totally different scores with random, altenbach001, cc ref, cc ref2 and kp players??

cosmin

[chilly_charly]

Cosmin,

May be you could publish your vi so others could test it 🙂

[BruceAmmons]

I am thinking I will publish my tester and all the entries as a single zip file, so people can investigate the results as they please and take a look at other people's strategies.

I did change the names on some routines to facilitate testing, and I think that might have confused one or two entries.

If anybody objects to their entry being published, speak up now.  If you put a password on your entry (Charly, other entries posted on web), please help me remove the password so other people can view your code.

Thanks,

Bruce