 |
 |
 |
 |
 |
 |
||||
|
|
|
|
|
|
||||
I submitted two versions. This document was written just after I had submitted the first version. I will append some notes on how version 2 is different.
I first solved the game by retrograde analysis (1.3 million positions). The game is a draw with perfect play. Solving the game takes just over a half-hour's worth of CPU time on a 486DX2-66. Since the contest time limit is one minute CPU, this program is not viable for the contest.
The limit on static data for the contest was about 30K, so storing the table was not feasible unless I did some pretty aggressive compression!
There are two different ways to play perfectly:
So I did both. Analyzing the retrograde solution, I compressed about 2/3 of the legal positions into a move table of 720 bytes.
What this means is, given the last digit of the two player's positions and the last move, the table gives a move that is always good regardless of the value of the tens digit. For instance, if the last move was a "2" (or equivalently a "7"), you index the player's positions in table "always2". If the player to move has a 3 and the opponent has a 6, then the table says moving "1" is always correct: It wins if a win is possible, and draws if a draw is the best possible.
Similarly, "alwaysonhoop" gives perfect moves for when the opponent is on a hoop: You index the value the opponent needs with the last digit of the number you are on in the table. For example, if your opponent needs 2 and you are on an odd digit, the best move is always to move "2".
For positions where the particular hoop (ten's digit) that the players are at matters, these tables give no result: The first table returns a negative number to indicate this, and the second returns a zero.
To deal with this, I chose the "most important" portion of the remaining positions, and stored the values of those positions in a 6,240 byte table. "Most Important" meaning positions where both players have passed the same number of hoops---in perfect play, such positions occur at least every third or fourth move. Roughly speaking, these are the positions where the players are "tied". On top of this information, I placed a standard alpha-beta search, with extensions: The move tables are used to extend the search until it reaches a position not in the move table.
In summary:
How good is the program?
[Note---this was written before the contest results were known]
The program appears to play perfectly. Against perfect play, out of hundreds of trials, I've never seen the search fail to return the drawing move within two ply (the search is a hard-coded six-ply search, which takes less than one second CPU total for all moves of a game (on a 486DX2-66).
Against mistaken play, the program does not do as well. This is harder to test---just what is a "good mistake"? It's easy for a single mistake to blow the entire game. With the search extensions, the program is sometimes capable of seeing 80-ply winning sequences.
A good "mistake" might be the sub-optimal move with the longest time to loss, followed by playing the moves that defer the loss as long as possible on all subsequent moves til the end of the game.
Unfortunately, I don't have "distance to win/loss" in my retrograde solution. Such a table would likely take several hours of CPU to construct, and wasn't necessary for solving this game, which is monotonic.
And even if I had distance to win/loss information, "longest distance to loss" isn't the same as "best defence". Some of the longer ways of losing (eg. being on 10 and needing 2 to get off) are also the easiest for the opponent to play.
The search has never been observed to fail, but it doesn't give me a warm fuzzy feeling. Given a winning position as input, the chosen best move regularly wobbles between different values, and the search usually does not see that the position is winnable. I suspect the real reason it hasn't lost is that I haven't constructed a "imperfect, but competent" player. For a sparring partner, I've been using the perfect-play program after a randomly-chosen mistake, but given a lost position as input, the perfect-play program just plays randomly.
Why is it harder to play well against mistakes? This is hardly intuitive. The problem is that against perfect play, the program is doing searches among "almost tied" psoitions---which are what is in the score table. Typically one or two ply suffices to find the drawing move.
If the opponent makes a mistake, the root position is no longer tied, and the search rarely hits the score table for values. Except when the search finds a long forcing sequence, it has no real idea which positions are good or bad.
I had hoped to submit a program which played perfectly. The submitted version is doubly annoying, in that if it loses a game, it will be because the *opponent* made the first mistake. :-(
MAIN CONCERNS:
(2) I don't have access to the target compiler (Borland C) nor was a test-harness provided. If the program is inconsistent with the ambiguous specification for the interface, it will forfeit the tournament.
This would be an annoying way to lose.
The program has deliberately been written conservatively. The declared arrays are small, there is no dynamic allocation, no header files are included and no external library functions are called. Very conservative assumptions about the types of "int" and "char" were made.
(3) The specification of the rules contain some ambiguities. Again, a test harness would have resolved this issue (a move being legal if the harness accepts it). If I have mis-interpreted the rules, the retrograde analysis will be wrong, and the entire program basically bogus.
(4) Bugs. Always a problem in a program that must work right the first time. All reachable positions have been tested against the move tables and the value tables (which uncovered some interesting bugs), and the program now appears correct.
Testing the search against all reachable positions is probably prohitive, and it isn't clear what it would accomplish... I'm sure it occassionally fails, but it's not obvious that having an example of such a failure would indicate the solution.
Statistics:
Lines
of
Code bytes filename
----- ----- ------------------
132 2717 WriteRetro.c [Solves the game and writes the database]
801 19305 anal.c [Analyzes the database for winning strategies]
154 3147 croquar.c [A user-interface to the database]
478 10862 encode.c [Encoding scheme used to store positions]
1093 40454 submit.c [The submitted code]
650 27478 test.c [Validation of submit.c]
207 4782 util.c [Assorted other stuff]
67 1799 common.h [The header file inlined in move.c]
104 3423 croquar.h [Header stuff used in other routines]
________________________________
3686 15255 113967 total
Still some time before the deadline!Each person is allowed to submit two versions. I'm hoping that the organizers will have time to compile & test my program, and if there are any lethal mistakes I will have time to correct.
[Note: There was a lethal mistake with the second version, which I was able to correct in time]
Regardless of whether I hear back, I may submit a second version.
Stuff I might try to squeeze in: More data in the score table. Total static allocations are less than 7K at the moment. Storing positions where the hoops crossed differ by exactly one would add 18K of data, still within the 30K limit.
Or I could use a more efficient encoding scheme to halve the storage.
Or I could write a more sophisticated search, that checked the time remaining---using less than 1/60th of the available time is excessively conservative. A deeper search might help.
Or I could improve the evaluation function... but how? To me all positions look the same. :-(
A routine, KnownValue, tries to expand this one bit into exact won/loss/draw information.
Positions where either player is on a hoop, or past a hoop invalidly, are still not included in the tables and must be handled by the search.
In summary, the second version knows about more positions, but knows less about the positions the first knew about perfectly.
This version was not well tested, and when submitted did not compile at first. Thanks to the organizers for pointing this out soon enough for me to fix the problem and resubmit.
Back to CROQUAR-95 Index Page