/* Boxes game in Picat v3. Inspired by the Prolog code from "Thinking in Computation", page 225. The problem is as follows: """ There are eight dots aligned as in the diagram, * * * * * * * * making the outline of three squares. At each turn, a player draws one of the undrawn horizontal or vertical edges of a square by connecting two adjacent dots. If this happens to be the last undrawn edge of a square, the player owns the square, and may optionally move again. The first player to own two squares wins. (There are no ties.) """ The lines: * --- 1 --- * --- 2 --- * | | | 3 4 5 | | | * --- 6 --- * --- 7 --- * | | 8 9 | | * -- 10 --- * Square 1 has lines 1,3,4,6 Square 2 has lines 2,4,5,7 Square 3 has lines 6,8,9,10 This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import util. % import cp. import gameplayer_v3. main => go. /* Some experiments with winning moves from certain positions. The first player is max and the initial state is [] Player max chooses move [1] and the new state is [draw(max,1)] Player min chooses move [3] and the new state is [draw(max,1),draw(min,3)] Player max chooses move [4] and the new state is [draw(max,1),draw(min,3),draw(max,4)] Player min chooses move [6] and the new state is [draw(max,1),draw(min,3),draw(max,4),draw(min,6)] Player max chooses move [2] and the new state is [draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,2)] Player min chooses move [8] and the new state is [draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,2),draw(min,8)] Player max chooses move [5] and the new state is [draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,2),draw(min,8),draw(max,5)] Player min chooses move [7] and the new state is [draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,2),draw(min,8),draw(max,5),draw(min,7)] -------- The winner is min CPU time 30.174 seconds. */ go ?=> play_user(nobody), nl, % fail, nl. go => true. /* The winning moves for max are: (Note the duplications of some of the solutions.) [p = max,move = [7]] [p = max,move = [7]] [p = max,move = [7,9]] [p = max,move = [7,9]] [p = max,move = [7,10]] [p = max,move = [7,10]] [p = min,move = [7]] CPU time 0.001 seconds. */ go2 ?=> win_move($[draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,2),draw(min,8),draw(max,5)],P,Move), println([p=P,move=Move]), fail, nl. go2 => true. /* Winning moves for min: [p = min,move = [8]] [p = min,move = [9]] [p = min,move = [10]] CPU time 0.002 seconds. */ go3 ?=> win_move($[draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,2)],min,Move), println([p=min,move=Move]), fail, nl. go3 => true. /* If max starts with 1, then min has a winning move: [p = min,move = [3]] CPU time 2.084 seconds. */ go4 ?=> win_move($[draw(max,1)],min,Move), println([p=min,move=Move]), fail, nl. go4 => true. /* If max starts with 1, min counters with 3, has max any change to win? Nope! This is found in 0.479s */ go5 ?=> win_move($[draw(max,1),draw(min,3)],max,Move), println([p=max,move=Move]), fail, nl. go5 => true. /* If min happens to play 2 in its first move (instead of 3), what can player max do to win? [p = max,move = [4]] [p = max,move = [6]] [p = max,move = [4]] [p = max,move = [6]] CPU time 0.768 seconds. */ go6 ?=> win_move($[draw(max,1),draw(min,2)],max,Move), println([p=max,move=Move]), fail, nl. go6 => true. /* There is no (provable) winning move from [] for max. It takes about 16s to find this. */ go7 ?=> win_move([],max,Move), println(move=Move), fail, nl. go7 => true. /* No tie move. So min loses from here. CPU time 0.007 seconds. */ go8 ?=> tie_move($[draw(max,10),draw(min,2),draw(max,4),draw(min,9),draw(max,1) ], min, Move), println(move=Move), fail, nl. go8 => true. /* Min can tie with the following moves: move = [2] move = [5] move = [7] CPU time 4.28 seconds. */ go9 ?=> tie_move($[draw(max,10)], min, Move), println(move=Move), fail, nl. go9 => true. /* max start with 10. what will min do? The first player is min and the initial state is [draw(max,10)] Player min chooses move [2] and the new state is [draw(max,10),draw(min,2)] Player max chooses move [1] and the new state is [draw(max,10),draw(min,2),draw(max,1)] Player min chooses move [3] and the new state is [draw(max,10),draw(min,2),draw(max,1),draw(min,3)] Player max chooses move [4] and the new state is [draw(max,10),draw(min,2),draw(max,1),draw(min,3),draw(max,4)] Player min chooses move [6] and the new state is [draw(max,10),draw(min,2),draw(max,1),draw(min,3),draw(max,4),draw(min,6)] Player max chooses move [5] and the new state is [draw(max,10),draw(min,2),draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,5)] Player min chooses move [7] and the new state is [draw(max,10),draw(min,2),draw(max,1),draw(min,3),draw(max,4),draw(min,6),draw(max,5),draw(min,7)] -------- The winner is min CPU time 3.542 seconds. Backtracks: 0 */ go10 ?=> cl_facts($[initial_state([draw(max,10)],min)]), play_user(nobody), nl. go10 => true. % This is the Boxes game. player(max). player(min). % table square_lines(sq1,[1,3,4,6]). % Lines for square 1 square_lines(sq2,[2,4,5,7]). % Lines for square 2 square_lines(sq3,[6,8,9,10]). % Lines for square 3 initial_state([],max). % Initially no lines are drawn. % table game_over(St,_,W) :- % Winner W owns two squares. owns(W,Sq1,St), owns(W,Sq2,St), Sq1 != Sq2. % Player P owns Sq if just drew last line or owned Sq before. % table owns(P,Sq,[draw(P,L)|St]) :- last_avail_line(L,Sq,St). owns(P,Sq,[_|St]) :- owns(P,Sq,St). % Line L is available and is the last of square not yet drawn. % table last_avail_line(L,Sq,St) :- avail_line(L,Sq,St), not avail_line(_,Sq,[$draw(_,L)|St]). % Line L is from Sq and not yet drawn in state St. % table avail_line(L,Sq,St) :- square_lines(Sq,Ls), member(L,Ls), not member($draw(_,L),St). % The legal moves % table legal_move(St,P,[L],[draw(P,L)|St]) :- % println($legal_move1(st=St,p=P,l1=L1,st2=St2)), % Draw a line and stop. avail_line(L,_,St). legal_move(St,P,[L|Rest],New) :- % Draw a line and go on. % println($legal_move2(st=St,p=P,lrest=LRest,new=New)), last_avail_line(L,_,St), legal_move([$draw(P,L)|St],P,Rest,New). write_state(S) => nl, print(" "), print(S.reverse), nl.