Tutorial Prolog Tic-Tac-Toe in the Browser

The Dogelog runtime performs well enough to provide an interactive board game. We use consult/1 to load the Prolog text of the game. At the end we can play Tic-Tac-Toe in the browser:

In the following we will give a glimpse how the game was realized. At the end one finds also a link to a GitHub repository which provides the Dogelog runtime and the example source code.

Game Board

The board is a div element with a couple of child button elements. Foreign functions allow to access and modify the board from within Prolog. Each of the 3x3 child buttons gets a different background image depending on a label. This is done via a CSS style sheet that is embedded in the HTML page. The CSS style sheet has the following rules:

        [aria-label="x"] {
            background-image: url('first.svg');
        }
        [aria-label="o"] {
            background-image: url('second.svg');
        }

The Prolog atom '-' serves as an indicator that one of the players has not yet marked a board cell. We do disable a board cell as soon as a player marked it. The Dogelog runtime offers a JavaScript call to register foreign functions. Besides the JavaScript function set_button(), we also register JavaScript functions get_button() and set_complete():

    register("get_button", 2, get_button, FFI_FUNC);
    register("set_button", 2, set_button, 0);
    register("set_complete", 0, set_complete, 0);

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 with the values ​​-1, 0 and 1. 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.

Game Play

The game play first checks the board. If the game is not yet complete, it calls best/3, which succeeds non-deterministically with new boards. A more elaborate solution would then randomly pick a solution. For simplicity we only pick the fir , which is done by placing a Prolog cut !/0. The game play then checks the board again.

looser(X) :- win(X, x), !, write('you win.'), nl, set_complete.
looser(X) :- tie(X, o), !, write('nobody won.'), nl, set_complete.
looser(X) :- best(X, o, Y), !, set_board(Y), winner(Y).
looser(_) :- write('I give up.'), nl, set_complete.

The HTML page also defines some output call back. We simply carried over the approach from the sandbox example and write into a DOM element. In the above, the status line is then populated by invoking the standard Prolog write/1 and nl/0. More advanced solutions might combine it with audio feedback or other visual cues.

Conclusions

The example has been uploaded to the following URL for quick exploration:

ㅋㅋㅋ xぉg. ch

We benchmarked a full game tree search and found, timing in ms:


Platform, Browser
C 0.9.2


Windows 10, Chrome
276

Apple MacBook, Safari Prev
269

Android Tablet, Chrome
1'422

Apple iPad, Safari
312


Because there will be already a move when the game search kicks in, the game search will need 2-4 times less time than a full game search tree from the beginning. This means that on most platform and browser combinations the response time will be below 100ms, preventing that the end-user might get frustrated, annoyed or even angry.

Dogelog Runtime - GitHub Repository
ht tp : // 기대 b. 코 m / j 부 r 세 / 도게 ぉ g도