Just over a month ago, I wrote1 So now I've exhausted all the goals that I originally wanted from a Prolog interpreter. It can solve the following queries (or parse the statements), each of which exercises a different part of the syntax as well as including goals that include multiple clauses. Of course, about a day later, I was adding more functionality to the interpreter.
Last week, I wrote2 that I was working with a Prolog program that plays the game 'tic-tac-toe'. The game at first was irrelevant; the program contained a few constructs that my interpreter could not handle. So once again CoPilot and I started adding what was missing: most of this was simple (for example, the i/o functions write/1, nl/0 and read/1) but one was extremely difficult.
It turns out that the simple comma has two different functions in Prolog. Until now, the comma separated arguments to a predicate; for example, the comma in the clause 'parent (noam, netta)' separates the two arguments to the 'parent' fact. But in another context, the comma behaves differently: this is when there is a list of goals to be solved. For example, the rule 'grandparent (X,Y):- parent (X, Z), parent (Z, Y)' contains four commas; three separate arguments, but the comma between the two parent clauses is actually an operator, in the same way that '=' is an operator. If this comma were not an infix operator, the body of the rule would be written as , (parent (X, Z), parent (Z, Y). It took a great deal of time to get the parser to parse an expression of this kind successfully. A casual user would be completely unaware of this problem.
Of course, after the parser succeeded in parsing the expression, the interpreter could no longer solve the rules; when solving, that compound statement has to be turned back into two separate clauses. This is similar to the manipulation performed on the goal list in order to implement the 'arg' predicate. This, at least, was relatively simple compared to the challenge of parsing the two conjoined clauses.
Now the tic-tac-toe program could load and I could get the computer to play itself. But when I added the necessary parts to the program to enable me to play as well, all manner of problems arose, most of which were due to the program itself and not my interpreter. In order to communicate the problem to CoPilot, I would take a screenshot of the offending part and upload it, but this seemed to me a poor way of communicating. Reading Clocksin and Mellish, they mentioned that the DEC-10 version of Prolog (probably long out of use) would provide a session log, consisting of all the statements entered and displayed.
I thought this a good idea, and during a dog walk, I considered ways of implementing this. When I put it to CoPilot, it had a better idea: create modified versions of write/writeln and readln, and use these instead of the normal procedures. My private procedures write both to the screen and to the session log; very simple to implement, and very useful. Now I could upload complete sessions to CoPilot for analysis.
Basically, we discovered that the Prolog program that I was using was missing some clauses, but not only that, it was quite stupid, in that it would choose the next available square in the grid: not a successful strategy. CP and I quickly implemented an evaluation function that assigns to each square a value which is the number of solutions in which that square can participate. On a 3x3 grid, each corner can participate in three solutions whereas each middle square can participate in only two; the middle square is the most valuable as it can participate in four solutions. I also wanted that the computer would announce its moves, instead of having to look at the grid and figure out what had changed.
Work finished on late Friday afternoon: it seemed that the program was tantalisingly close to completion but I had run out of time. On Saturday morning, I ran the program and saw that it was 99% complete, so with a few additions, we now had a Prolog version of tic-tac-toe that works quite well (the result is always a draw) as well as a much improved Prolog interpreter. Here's the session log for the final run:
> ?- consult (ttt). ttt consulted Yes. > ?- playo. You play X by entering integer positions followed by a period. [1, 2, 3] [4, 5, 6] [7, 8, 9] |: 1. [x, b, b] [b, b, b] [b, b, b] I play 2 [x, o, b] [b, b, b] [b, b, b] |: 5. [x, o, b] [b, x, b] [b, b, b] I play 9 [x, o, b] [b, x, b] [b, b, o] |: 3. [x, o, x] [b, x, b] [b, b, o] I play 7 [x, o, x] [b, x, b] [o, b, o] |: 8. [x, o, x] [b, x, b] [o, x, o] I play 4 [x, o, x] [o, x, b] [o, x, o] |: 6. [x, o, x] [o, x, x] [o, x, o] Cats game! Yes. > quit.
Incidentally, I didn't know what the expression "Cat's game" was supposed to mean. Could it be that someone whose nickname was Cat wrote the program and that this was her way of immortalising herself? No, says CoPilot. “Cat’s game” does mean something. It’s an old American expression for a tic‑tac‑toe draw. The idea is that when neither X nor O can win, the game is “for the cats” — meaning worthless, unwinnable, a stalemate. No cats were involved in the writing of your Prolog code. I would have known this had I read the Wikipedia article more thoroughly.
I ran a new game: normally I would start with square 5 but just to keep things interesting, I decided to start with square 1 instead. The computer choosing square 2 was not clever; this probably means that the simple rule that chooses the next available square appears before the rule that used the evaluation function. As rules are evaluated in a top-down order, the position of a rule can be critical. After thinking about this, I rearranged the 'moves' rule so that they would appear according to their value; thus the first rule would cause the computer to choose square 5, then square 1, etc. When I ran the program with the rearranged rules, the computer played much better. Again, I chose to start with square 1 deliberately to see what the computer would do; it chose square 5. I then chose square 3, so the computer had to choose square 2, otherwise I would win with my next move. In doing so, the computer had set up the 2-5-8 combination, so of course I had to chose square 8. The computer then chose square 7 - this doesn't contribute anything, but it shows that the computer is playing according to the order of the moves: 5,1,3,7,9,2,4,6,8. As squares 5, 1 and 3 were occupied, the next unoccupied square according to the precedence was 7.
So once again I wonder, have I completed the Prolog interpreter?
Internal links
[1] 2047
[2] 2059
| Title | Tags | ||
|---|---|---|---|
| 230 | Keith Tippett Group – "Dedicated to you, but you weren't listening" | King Crimson | |
| 538 | Nic Potter RIP | Obituary, Van der Graaf Generator, RIP | |
| 918 | MP3 headphones (2) / The scientific method | Programming, MP3 | |
| 1370 | Covid-19 vaccination (3) | Covid-19 |
No comments:
Post a Comment