07-18-2006 11:21 AM - edited 07-18-2006 11:21 AM
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:
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
07-18-2006 03:09 PM
07-18-2006 05:02 PM - edited 07-18-2006 05:02 PM
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
07-18-2006 05:05 PM
07-18-2006 05:09 PM
07-18-2006 07:49 PM - edited 07-18-2006 07:49 PM
Message Edited by Daklu on 07-18-2006 08:21 PM
Message Edited by Daklu on 07-18-2006 08:21 PM
07-19-2006 10:21 AM - edited 07-19-2006 10:21 AM
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
07-22-2006 03:40 AM
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
07-22-2006 04:23 AM
Cosmin,
May be you could publish your vi so others could test it 🙂
07-22-2006 10:01 AM
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