Game Search

The Game search uses Prolog terms to represent the board. Negation as failure the helps to find best move suggestions. We do a full game search, which means our game search does not have any parameter limiting the search depth. The game search requires that predicates such as move/3 and win/2 be defined.

The game search then uses backtracking to search a best move:

best(X, P, Y) :-
  move(X, P, Y),
  (win(Y, P) -> true;
    other(P, Q),
    \+ tie(Y, Q),
    \+ best(Y, Q, _)).

The above Prolog code corresponds to a min/max search. The predicate best/3 succeeds with a move where the opponent will move into a tie or where the current player will win. This corresponds to the values 0 and 1. The predicate fails if the opponent will win or the current player moves into a tie. This corresponds to the values -1 and 0.

The above Prolog code also implements a kind of alpha/beta pruning. The sub goal best/3 only needs to succeed once. The if-then-else means the parent calls best/3 only if it has not yet a direct winning move. To oppose an indirect winning move, only a single opponent winning move need to be found, the rest of the moves can be pruned.

Kommentare