|
| Bruce Incognito 21 July 2013 00:26:42
COMPUTER SCIENCE IN THE Q8 GAME
Introduction
In this section we will look at a few of the more interesting pieces of Computer Science that are employed in the Q8 game. Most of the Computer Science in the game revolve around giving Squiffy (the Alcoholic Artificial Intelligence) the ability
to play the Q8 game with an appropriate level of competence.
What are the Problems Facing Squiffy?In the game setting the player and Squiffy are both presented with an identical unsatisfying arrangement of the eight queens, each takes turns to move a single queen to an unoccupied square on the board (or exchange two columns on the board if playing in columns mode) until one or other reaches a satisfying arrangement. Squiffy needs to determine the "shortest path" measured in moves between the current arrangement and the "closest" satisfying arrangement. The "shortest path" part of the problem is trivial once he has found the "closest" satisfying arrangement, the "shortest path" is determined by the number of positions in the current arrangement that do not appear in the satisfying arrangement.
How Well Does Squiffy Perform?In "normal" playing mode we present Squiffy with 1,000,000 random unsatisfying arrangements and then see how many moves he takes to convert the arrangement to a satisfying arrangement with the following results.
| Moves | Trials | Percentage | | 8 | 7 | 0.007% | | 7 | 493 | 0.0493% | | 6 | 248,816 | 24.8816% | | 5 | 613,271 | 61.3271% | | 4 | 130,115 | 13.0115% | | 3 | 7,139 | 0.7139% | | 2 | 157 | 0.0157% | | 1 | 2 | 0.0002% | | 0 | 0 | 0.0000% | | | | | | | Mean = 5.1050 | |
Well, that looks pretty good. But hang on a second, the fact that we got 7 trials that resulted in 8 moves implies that there must be a square on the board that does not appear in any solution! That can't be right.
The table below shows the result of counting the hits on each square of the board for all 92 solutions.
| 4 | 8 | 16 | 18 | 18 | 16 | 8 | 4 | | 8 | 16 | 14 | 8 | 8 | 14 | 16 | 8 | | 16 | 14 | 4 | 12 | 12 | 4 | 14 | 16 | | 18 | 8 | 12 | 8 | 8 | 12 | 8 | 18 | | 18 | 8 | 12 | 8 | 8 | 12 | 8 | 18 | | 16 | 14 | 4 | 12 | 12 | 4 | 14 | 16 | | 8 | 16 | 14 | 8 | 8 | 14 | 16 | 8 | | 4 | 8 | 16 | 18 | 18 | 16 | 8 | 4 |
The table provides a hint about how to select an opponents queen to be fixed when playing in fix-one mode. The square with the lowest number of solutions should be chosen as it will minimise the number of possible solutions available to your
opponent.
As we can see there is clearly no square on the board that does not participate in any solution, so something is clearly wrong with the algorithm that Squiffy is using. Let us see if the great mind himself can shed any light on this anomaly.
TTY04: Squiffy, I notice that in the one million trials test you used eight moves in seven different trials, given that there are no squares on the board that do not participate in one or more valid solutions then it should never take you eight moves to complete a solution. Is there a flaw in the algorithm that you use for solving the problem?
SQUIFFY: Yes.
TTY04: Thank you for that no doubt accurate but perfectly unhelpful answer.
SQUIFFY: You are welcome.
TTY04: What is the nature of the flaw?
SQUIFFY: A transposition error was found in the terminal graph node evaluation algorithm.
TTY04: Why was the flaw not corrected?
SQUIFFY: You decided that the flaw should not be corrected as it only had a very small effect on the performance of the solver algorithm and you thought that it made me a little less predictable, a little more "human" as you insultingly referred to it.
TTY04: OK, thank you.
|
This illustrates a particular problem that needed to be overcome in the performance of the solver, it would be boring to play against an automated opponent that always performed to perfection and therefore always beat you. This is where Squiffys liking for alcohol comes to the rescue, the solver algorithm incorporates a number of bale-out points during the move evaluation. These bail-out points are influenced by the level of alcohol, an increased level increases the probability of an early bale-out during the move evaluation process. The effect of the early bale-out is equivalent to a loss of concentration while performing a complex task, resulting in a sub-optimal move being selected. Let us take a look at the effects of alcohol on Squiffys problem solving performance.
| % Drunk. | 0% | 10% | 20% | 30% | 40% | 50% | 60% | 70% | | Least moves. | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 2 | | Most moves. | 8 | 31 | 41 | 74 | 117 | 194 | 426 | 1,166 | | Mean moves. | 5.1050 | 6.1400 | 7.5707 | 9.7262 | 13.3656 | 20.1607 | 36.5312 | 92.0237 | | Median moves. | 5 | 6 | 7 | 9 | 12 | 17 | 27 | 74 |
We see a good exponential decay of capability with the increase in the intoxification level, this is just what we want.
How Well Does Squiffy Perform in Columns Mode?In the columns mode of play two queens exchange columns so a move in this mode in fact consists of two half moves, again we give Squiffy 1,000,000 random unsatisfying arrangements and then see how many moves he takes to convert the arrangement to a satisfying arrangement with the following results.
| Moves | Trials | Percentage | | 6 | 56 | 0.0056% | | 5 | 20,597 | 2.0597% | | 4 | 251,958 | 25.1958% | | 3 | 459,955 | 45.9955% | | 2 | 234,801 | 23.4801% | | 1 | 32,633 | 3.2633% | | 0 | 0 | 0.0000% | | | | | | | Mean = 2.9933 | |
Let us take a look at the effects of alcohol on Squiffys problem solving performance in Columns play mode.
| % Drunk. | 0% | 0% | 20% | 30% | 40% | 50% | 60% | 70% | | Least moves. | 1 | 1 | | 1 | 1 | 1 | 1 | 2 | | Most moves. | 6 | 56 | 69 | 91 | 123 | 184 | 255 | 466 | | Mean moves. | 2.9933 | 4.1836 | 5.3400 | 6.9801 | 9.2430 | 13.1543 | 19.6801 | 31.9909 | | Median moves. | 3 | 3 | 4 | 5 | 7 | 7 | 12 | 22 |
How Does Squiffy Test for a Satisfying Solution?Squiffy stores the current state of a board in an array of eight queens each element holding the Row and Column co-ordinates of a queen. To test if the solution satisfies all three constraints Squiffy uses the following method.
1. Clear an array of eight integers to zeroes.
2. Store the co-ordinates of each queen in the array element (Row - 1) is set equal to the Column co-ordinate.
3. Calculate the product of each element in the array. Test that the product equals eight factorial 8! (1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 = 40,320).
We now have a condensed array that satisfies constraints 1 and 2, i.e. no two queens are on the same row or column. If there were two queens on the same row then one element of the array would still contain zero and this would cause the product to be zero, if two queens were on the same column then the product would be something other than 8!.
The condensed array can then be tested for constraint 3 (no two queens on the same diagonal) using the same method that we used to generate and count the unique solutions. |
|
|
|
