1

One can search the full tic tac toe game tree, using only fail fast optimization of negation as failure, in less that 100ms. Thats what this solution does using a holistic representation of the game state as a single Prolog term:

?- time((init(X), best(X, x, _))).
% 92,055 inferences, 0.031 CPU in 0.031 seconds (99% CPU, 2984342 Lips)
false.

The above solution uses a single term for the board, here is an example from the code:

init([[-, -, -], [-, -, -], [-, -, -]]).

Are there any Prolog means around to solve the problem differently. Instead of using a single term that represents the state, use a set of facts to represent the state like here in a game representation from the Stanford General Game Playing.

(init (cell 1 1 b))
(init (cell 1 2 b))
(init (cell 1 3 b))
(init (cell 2 1 b))
(init (cell 2 2 b))
(init (cell 2 3 b))
(init (cell 3 1 b))
(init (cell 3 2 b))
(init (cell 3 3 b))

Was thinking about CHR: Constraint Handling Rules, since it can add and remove facts, but I dont know whether its suitable for adversarial search.

logi-kal
  • 7,107
  • 6
  • 31
  • 43

1 Answers1

0

You would use assert:

:- dynamic play/2. % declare as dynamic (that is, assert is permitted)

% initial state
cell(1, 1, b). cell(1, 2, b). cell(1, 3, b).
cell(2, 1, b). cell(2, 2, b). cell(3, 3, b).
cell(3, 1, b). cell(3, 2, b). cell(3, 3, b).

% play/2: use to mark the cells.
play(Player,Row-Col) :-
   retract(cell(Row,Col,b)), % if retract fails, the cell is not blank
   assertz(cell(Row,Col,Player)).

% test of play/2
:- play(white,2-2).

assert adds a fact to the database that can be queried after. assertz adds it to the end of the database, and asserta to the start. retract removes the first fact that matches the data.

Edit: following comments, an alternative is to have no facts when a player has not marked a cell. In that case the play rule would need to check that the cell isn't already played:

play(Player,Row-Col) :-
   \+ cell(Row,Col,_)), % check the cell is not already taken
   assertz(cell(Row,Col,Player)).
boisvert
  • 3,679
  • 2
  • 27
  • 53
  • @MostowskiCollapse and a is anatoly, the first one. OK, I'll standardise, it's an opportunity to say more of dynamic predicates. But IMO you have the information you wanted. – boisvert Jan 23 '21 at 22:44
  • Yes, that's an option. A blank cell is absent from the facts database. – boisvert Jan 23 '21 at 22:55