The perils of unground variables in logic

General
1

I managed to resolve a bug in a program today which was obvious in retrospect, but raised my Prolog enlightenment quite a bit.

The problem starts with a chess program written as part of Stanford University’s General Game Playing course which I discovered via Coursera a few years ago. (The course is still available at General Game Playing - Notes).

I really enjoyed the course, and I think General Game Playing would have got a lot more traction if the instructor, Professor Michael Genesereth, had simply used Prolog instead of his own invented Lisp-style language called kif.

I was under the impression one could simply transliterate kif into prolog, leading me into the following trap.

The original kif predicate to say a player could move a piece to block a checking move by a queen or a rook (the exact same problem cropped up in the queen or bishop predicate) looked like this:

; Block rook threat (rook or queen)
(<= (legal ?player (move ?piece ?u ?v ?x ?y))
    (true (control ?player))
    (or (true (check ?player rook ?tx ?ty))
        (true (check ?player queen ?tx ?ty)))
    (not (occupied_by_player ?x ?y ?player))
    (piece_owner_type ?piece ?player ?ptype)
    (distinct ?ptype king)
    (piece_owner_type ?king ?player king)
    (true (cell ?kx ?ky ?king))
    (legal2 ?player (move ?piece ?u ?v ?x ?y))
    (blocks_rook_threat ?x ?y ?tx ?ty ?kx ?ky)
    (not (threatened_with_capture ?player ?tx ?ty ?kx ?ky ?u ?v))	; (u,v) is location moved from -- ignore it
    )

My “interpreter” tansliterated it into this:

% Block rook threat (rook or queen)
legal(Player, move(Piece, U, V, X, Y)) :- 
  true(control(Player)), 
  (true(check(Player, rook, Tx, Ty)) ; true(check(Player, queen, Tx, Ty))), 
  \+occupied_by_player(X, Y, Player),
  piece_owner_type(Piece, Player, Ptype), 
  dif(Ptype, king), 
  piece_owner_type(King, Player, king), 
  true(cell(Kx, Ky, King)), 
  legal2(Player, move(Piece, U, V, X, Y)), 
  blocks_rook_threat(X, Y, Tx, Ty, Kx, Ky), 
  \+threatened_with_capture(Player, Tx, Ty, Kx, Ky, U, V).

It took me a couple of hours to figure out why my game player using the mechanically translated kif rules would not allow players to make blocking moves.

Fixing this simply involved moving one line of code. I’ll leave that here as a chess puzzle for readers.

3

The solution here was not deletion, but re-ordering. It’s example of how Prolog is hypothetically a declarative language, but in practice the order of clauses matters a lot.

5

True. The basic problem is the occupied_by_player predicate always fails because X and Y are only instantiated by the legal2 clause which follows it. The thing I learnt was if you ask if an unground variable is false, it is.

Basic rule of thumb is clauses which set variables need to go at the top, and those that test them at the bottom.

6

I’m curious if you could have avoided re-ordering by using freeze/2 or the more general when/2.

7

Prolog is a language with a subset that has the same semantics regardless of the ordering. Ordering still affects termination and performance, even in this subset. You use \+ though, which is is not part of this subset. You can extend this subset using constraints (you already use dif/2) and tabling. Be aware though that neither play well with committing to a choice (!, ->, \+). In the very latest version (8.1.6), tabling comes with (one form of) sound negation by means of tnot/1.

2 Likes
9

“Prolog is different, but it’s not that different.” – Richard O’ Keefe

1 Like
10

Generate-and-test can be very slow if there are a lot of possibilities. A faster way can be to use delayed-test-and-generate, using either freeze/2 (or when/2) or tnot/1. This can short-circuit some of the generating, when a test is sufficiently ground to be decidable as having failed. (See also “constraints”)

11

Thanks Peter. At some stage I’d like to write an interpreter for the library of General Game Playing rules created by Stanford and Dresden universities which would automatically avoid bugs like this. I’ve little experience with the clauses you mention, so will look into them.