% glogic02.pl --- a logic programming for perfect information games.
% created: 22 Aug 2003. (was: glogic.pl, 10 July 2003).
% modified: 14,17 Sep 2003.(glogic01.pl)
% modified: 10-14 Dec 2003.  perfect information cases.
% modified: 20 Dec 2003.  is_rational_play/4. new variable A-->B in the findall.
% References:
% [1] S. Muto (2001). Gemu Riron Nyuumon. Nikkei Bunko.
% [2] Fudenberg and Tirole (1991). Game Theory.MIT Press.


%------------------------------------------
%  modeling perfect information game theory : (i.e., extensive form or game tree)
%------------------------------------------

:- dynamic player_type/1.
:- dynamic game_model/1.


game_models(
  [g10,g11,g12,g51(weak),g51(tough),g60,g70,centipade,ctpd1]
).
%game_model(g51(weak)).
game_model(g51(tough)).
%game_model(g60).


% auto-transformed model from the db of predicates game/4.

player(J):-
   game_model(G),
   game(G,players,N,_),
   member(J,N).

/*player_type(T):-
   game_model(G),
   game(G,player_types,Types,_),
   member(T,Types).*/

payoff(Z,J,V):-
   game_model(G),
   game(G, players(N), acts(A), payoffs(U)),
   nth1(K,N,J),
   nth1(K,U,V),
   reverse(A,Z).

terminal(Z):-
   game_model(G),
   game(G, players(_), acts(A), payoffs(_)),
   reverse(A,Z).


% player's information (player,name,path)

players_information(J,H,P):-
   game_model(G),
   game(G, information(H), player(J), path(Q)),
   reverse(Q,P).

% an illustrative example of the transformation.
% game(G, information(h2), player(2), path([exit]))
% -->  players_information(2,h3,[exit])

possible_act(H,J,A):-
   players_information(J,H,Q),
   players_information(_I,_H1,[A|Q]).

possible_act(H,J,A):-
   players_information(J,H,Q),
   terminal([A|Q]).



% prototype model 
%------------------------------------------

/*

player(1).
player(2).

% payoff lists are of reversed orderings of the players. 
terminal([c,a]).
terminal([d,a]).
%terminal([b]).
terminal([e,b]).
terminal([f,b]).

% payoff (play_history,player,payoff).
payoff([c,a],1,0).
payoff([d,a],1,2).
%payoff([b],1,1).
payoff([e,b],1,4).
payoff([f,b],1,1).

payoff([c,a],2,3).
payoff([d,a],2,2).
%payoff([b],2,0).
payoff([e,b],2,3).
payoff([f,b],2,4).

players_information(1,h1,[]).
players_information(2,h2,[a]).
players_information(2,h3,[b]).

% possible act at information set(name,player,act) 
possible_act(h1,1,a).
possible_act(h1,1,b).
possible_act(h2,2,c).
possible_act(h2,2,d).
possible_act(h3,2,e).
possible_act(h3,2,f).

*/


% nodes : but they are not substatively used in this model.
%----------------------------------------------

node(terminal,Y):-
   terminal(Y).

node(players_information(J,H),Y):-
   players_information(J,H,Y).



% a game play simulator --- not always rational one
%----------------------------------------------

generate_play_history([],[]).
generate_play_history([J|P],[A|Y]):-
   players_information(J,H,Y),
   possible_act(H,J,A),
   generate_play_history(P,Y).

% rational play model  ---- backward induction
% for perfect information games.
%----------------------------------------------
modified: 20 Dec 2003.

is_rational_play(J,A,H,Y):-
   players_information(J,H,Y),
   findall((B,U),
    max(U,inductive_payoff(_,[B|Y],J,U)),
   W),
   sort(W,W1),
   member((A,U),W1).

inductive_payoff([],Y,J,U):-
   payoff(Y,J,U).

inductive_payoff([A|Z],Y,J,U):-
   is_rational_play(_J1,A,_H,Y),
   inductive_payoff(Z,[A|Y],J,U).

inductive_payoff_vectors(Js,Y,U):-
   setof(Y,
     J^U^(
      inductive_payoff(Y,[],J,U)
     ),
   W),
   member(Y,W),
   game_model(G),
   game(G, players(Js), acts(Y), payoffs(U)).



%==============
% utilities
%==============

% maximal solution for given goal clause : a naive solver 
%---------------------------------------------------------

max(X,Goal):-
  % X: the objective variable,
  % Goal: the objective function and constraints,
  setof((X,Goal),Goal,Z),
  member((X,Goal),Z),
  \+ (
    member((Y,_),Z),
    Y > X
  ).



% a cui in order to switch models.
%---------------------------------------------------------

change_model(Y):-
   game_models(GMs),
   (
    (
     (\+ var(Y), U=Y)
      ;
     (nl, write('input a game model:'),read(U),\+ var(U)),
     member(U,GMs)
    )
     ->
      (abolish(game_model/1),Y=U,assert(game_model(Y)))
     ;
      (
       nl, 
       write('please select from : '), 
       write(GMs),change_model(Y)
      )
   ).

:- change_model(_).



%---------------------------------------------------
% game model db and some experimental results 
%---------------------------------------------------


% two simple perfect information games
%-------------------------------------
% See ref. [2], p.85, Figure 3.8 and p.91, Figure 3.14.

game(g10, players([1, 2]), acts([up, left]), payoffs([2, 1])).
game(g10, players([1, 2]), acts([up, right]), payoffs([0, 0])).
game(g10, players([1, 2]), acts([down, left]), payoffs([-1, 1])).
game(g10, players([1, 2]), acts([down, right]), payoffs([3, 2])).

game(g10,players,[1,2],2).
game(g10,information(h1),player(1),path([])).
game(g10,information(h2),player(2),path([up])).
game(g10,information(h3),player(2),path([down])).

/*

?- inductive_payoff_vectors(A,B,C).

A = [1, 2]
B = [down, right]
C = [3, 2] ;

No
?- 

*/

game(g11, players([1, 2]), acts([up]), payoffs([2, 2])).
%game(g11, players([1, 2]), acts([up, _left_or_right]), payoffs([2, 2])).
game(g11, players([1, 2]), acts([down, left]), payoffs([3, 1])).
game(g11, players([1, 2]), acts([down, right]), payoffs([0, 0])).

game(g11,players,[1,2],2).
game(g11,information(h1),player(1),path([])).
game(g11,information(h2),player(2),path([up])).
game(g11,information(h3),player(2),path([down])).

/*

?- inductive_payoff_vectors(A,B,C).

A = [1, 2]
B = [down, left]
C = [3, 1] ;

No

*/

% perfect/imperfect information game model
%-------------------------------------
% An entrant-monopolist type model by van Damme. 
% See ref. [2], p.438, figure 11.1.

game(g12, players([e]), acts([exit]), payoffs([2,2])).
game(g12, players([e,e,m]), acts([enter,tough, fight]), payoffs([0,0])).
game(g12, players([e,e,m]), acts([enter,tough, coop]), payoffs([3,1])).
game(g12, players([e,e,m]), acts([enter,weak, fight]), payoffs([1,3])).
game(g12, players([e,e,m]), acts([enter,weak, coop]), payoffs([0,0])).

game(g12,players,[e,m],2).
game(g12,information(h1),player(e),path([])).
game(g12,information(h2),player(e),path([tough])).
game(g12,information(h3),player(e),path([weak])).
game(g12,information(h4),player(m),path([fight,tough])).
game(g12,information(h5),player(m),path([coop,tough])).
game(g12,information(h6),player(m),path([fight,weak])).
game(g12,information(h7),player(m),path([coop,weak])).


/*
% case of the perfect information.

?- inductive_payoff_vectors(A,C,D).

A = [e]
C = [exit]
D = [2, 2] ;

No
?- 
*/

% Another entrant-monopolist type model by Kreps-Wilson-Milgrom-Roberts.
% See ref. [1], p.127, figure 4-3.

% tough entrant
game(g51(tough), players([1, 2]), acts([exit, deter]), payoffs([0, 5])).
game(g51(tough), players([1, 2]), acts([exit, coop]), payoffs([0, 5])).
game(g51(tough), players([1, 2]), acts([enter, deter]), payoffs([1, 1])).
game(g51(tough), players([1, 2]), acts([enter, coop]), payoffs([0, 3])).

% weak entrant
% --- Loss of market share is relatively small when enter and coop. 
%     and the entrant incurrs a large loss if he has detered.
game(g51(weak), players([1, 2]), acts([exit, deter]), payoffs([0, 5])).
game(g51(weak), players([1, 2]), acts([exit, coop]), payoffs([0, 5])).
game(g51(weak), players([1, 2]), acts([enter, deter]), payoffs([-2, 1])).
game(g51(weak), players([1, 2]), acts([enter, coop]), payoffs([2, 3])).

game(g51(T),players,[1,2],2):-member(T,[tough,weak]).
game(g51(T),information(h1),player(1),path([])):-member(T,[tough,weak]).
game(g51(T),information(h2),player(2),path([enter])):-member(T,[tough,weak]).
game(g51(T),information(h3),player(2),path([exit])):-member(T,[tough,weak]).


/*

?- [glogic02].

input a game model:g51(weak).
% glogic02 compiled 0.06 sec, 0 bytes

Yes
?- inductive_payoff_vectors(A,B,C).

A = [1, 2]
B = [enter, coop]
C = [2, 3] ;

No
?- [glogic02].

input a game model:g51(tough).
% glogic02 compiled 0.23 sec, 12 bytes

Yes
?- inductive_payoff_vectors(A,B,C).

A = [1, 2]
B = [enter, coop]
C = [0, 3] ;

A = [1, 2]
B = [exit, coop]
C = [0, 5] ;

A = [1, 2]
B = [exit, deter]
C = [0, 5] ;

No
?- 
*/


% expected payoffs of randomized strategies
%---------------------------------------------------------




% a perfect inormation game of three players
%------------------------------------------
% See ref. [1], p.88, figure 3-9 above.

game(g60, players([1,2,3]), acts(A), payoffs(U)):-
   game(g60,payoff,A,U).

game(g60,payoff,[a1,a2,a3],[5,2,3]).
game(g60,payoff,[a1,a2,b3],[3,5,2]).
game(g60,payoff,[a1,b2,a3],[3,3,4]).
game(g60,payoff,[a1,b2,b3],[6,3,1]).
game(g60,payoff,[b1,a2,a3],[4,3,4]).
game(g60,payoff,[b1,a2,b3],[2,5,3]).
game(g60,payoff,[b1,b2,a3],[2,6,2]).
game(g60,payoff,[b1,b2,b3],[5,1,4]).

game(g60,players,[1,2,3],3).

game(g60,information(h1),player(1),path([])).
game(g60,information(h2),player(2),path([a1])).
game(g60,information(h3),player(2),path([b1])).
game(g60,information(h4),player(3),path([a1,a2])).
game(g60,information(h5),player(3),path([a1,b2])).
game(g60,information(h6),player(3),path([b1,a2])).
game(g60,information(h7),player(3),path([b1,b2])).

/*
?- inductive_payoff_vectors(A,B,C).

A = [1, 2, 3]
B = [b1, a2, a3]
C = [4, 3, 4] ;

No
?- 
*/

% a perfect inormation game of four players
%------------------------------------------
% See ref. [1], p.97, figure 3-11.

game(g70, players([x,m,y,m]), acts(A), payoffs(U)):-
   game(g70,payoff,A,U).

% note: payoff list may be sorted independently to the act or player profile. 
game(g70,payoff,[ox,X,iy,d],[B,A,C,A]):-[A,B,C]=[6,0,-2],member(X,[a,d]).
game(g70,payoff,[ox,X,iy,a],[B,A,C,A]):-[A,B,C]=[8,0,2],member(X,[a,d]).
game(g70,payoff,[ox,X,oy,Y],[B,A,C,A]):-[A,B,C]=[10,0,0],member(X,[a,d]),member(Y,[a,d]).
%
game(g70,payoff,[ix,d,iy,d],[B,A,C,A]):-[A,B,C]=[2,-2,-2].
game(g70,payoff,[ix,d,iy,a],[B,A,C,A]):-[A,B,C]=[4,-2,2].
game(g70,payoff,[ix,d,oy,X],[B,A,C,A]):-[A,B,C]=[6,-2,0],member(X,[a,d]).
game(g70,payoff,[ix,a,iy,d],[B,A,C,A]):-[A,B,C]=[4,2,-2].
game(g70,payoff,[ix,a,iy,a],[B,A,C,A]):-[A,B,C]=[6,2,2].
game(g70,payoff,[ix,a,oy,X],[B,A,C,A]):-[A,B,C]=[8,2,0],member(X,[a,d]).

game(g70,players,[x,m,y,m],4).

game(g70,information(h(W)),player(J),path(X)):-
   game(g70,players,JS,N),
   nth1(N,JS,J),
   game(g70,payoff,Y,_),
   reverse(Y,[_|W]),
   reverse(W,X).
  % nl,write(reverse(W,X)).

game(g70,information(h(Y)),player(J),path(P)):-
   game(g70,players,JS,N),
   reverse(JS,[_|JSR]),
   nth1(K,JSR,J),
   L is N - K,
   length([X|Y],L),
   findall(Y,
    game(g70,information(h([X|Y])),player(_J1),path(_Q)),
   W),
   sort(W,W1),
   member(Y,W1),
   reverse(Y,P).

/*

?- change_model(g70).

Yes
?- inductive_payoff_vectors(A,B,C).

A = [x, m1, y, m2]
B = [ix, a, iy, a]
C = [2, 6, 2, 6] ;

No

*/


% a model of Rosentahl's centipade game(*) with counterfactual plays 
%------------------------------------------------------------
% (*) See ref. [2], p.98, Figure 3.19.

game(centipade, players,[1,2,1,2,1],2).

game(centipade, players([1,2,1,2,1]),acts([d,A,B,C,D]),payoffs([1,0,1,0,1])):-
   member(A,[a,d]),member(B,[a,d]),member(C,[a,d]),member(D,[a,d]).
game(centipade, players([1,2,1,2,1]),acts([a,d,B,C,D]),payoffs([0,1,0,1,0])):-
   member(B,[a,d]),member(C,[a,d]),member(D,[a,d]).
game(centipade, players([1,2,1,2,1]),acts([a,a,d,C,D]),payoffs([3,0,3,0,3])):-
   member(C,[a,d]),member(D,[a,d]).
game(centipade, players([1,2,1,2,1]),acts([a,a,a,d,D]),payoffs([2,4,2,4,2])):-
   member(D,[a,d]).
game(centipade, players([1,2,1,2,1]),acts([a,a,a,a,d]),payoffs([6,3,6,3,6])).
game(centipade, players([1,2,1,2,1]),acts([a,a,a,a,a]),payoffs([5,5,5,5,5])).

game(centipade,information(h([])),player(1),path([])).
game(centipade,information(h([A|P])),player(J),path([A|P])):-
   member(N,[1,2,3,4]),
   length([A|P],N),
   game(centipade,information(h(P)),player(J0),path(P)),
   member((J,J0),[(1,2),(2,1)]),
   member(A,[a,d]).

/*

?- inductive_payoff_vectors(A,B,C).

A = [1, 2, 1, 2, 1]
B = [d, a, a, a, a]
C = [1, 0, 1, 0, 1] ;

A = [1, 2, 1, 2, 1]
B = [d, a, a, a, d]
C = [1, 0, 1, 0, 1] ;

A = [1, 2, 1, 2, 1]
B = [d, a, a, d, a]
C = [1, 0, 1, 0, 1] ;

(...)

A = [1, 2, 1, 2, 1]
B = [d, d, d, a, d]
C = [1, 0, 1, 0, 1] ;

A = [1, 2, 1, 2, 1]
B = [d, d, d, d, a]
C = [1, 0, 1, 0, 1] ;

A = [1, 2, 1, 2, 1]
B = [d, d, d, d, d]
C = [1, 0, 1, 0, 1] ;

No
?- is_rational_play(A,B,C,[a,a,a,a]).

A = 1
B = d
C = h([a, a, a, a]) ;

No

(...)

?- is_rational_play(A,B,C,[a]).

A = 2
B = d
C = h([a]) ;

No
?- is_rational_play(A,B,C,[]).

A = 1
B = d
C = h([]) ;

No
?- 

*/


% simplified version of the centipade game
%------------------------------------------

game(ctpd1, players,[1,2],2).

game(ctpd1, players([1]),acts([d]),payoffs([1,0])).
game(ctpd1, players([1,2]),acts([a,d]),payoffs([0,1])).
game(ctpd1, players([1,2,1]),acts([a,a,d]),payoffs([3,0])).
game(ctpd1, players([1,2,1,2]),acts([a,a,a,d]),payoffs([2,4])).
game(ctpd1, players([1,2,1,2,1]),acts([a,a,a,a,d]),payoffs([6,3])).
game(ctpd1, players([1,2,1,2,1]),acts([a,a,a,a,a]),payoffs([5,5])).

game(ctpd1,information(h([])),player(1),path([])).
game(ctpd1,information(h([A|P])),player(J),path([A|P])):-
   member(N,[1,2,3,4]),
   length([A|P],N),
   game(ctpd1,information(h(P)),player(J0),path(P)),
   member((J,J0),[(1,2),(2,1)]),
   member(A,[a,d]).

/*

?- inductive_payoff_vectors(A,C,D).

A = [1]
C = [d]
D = [1, 0] ;

No
?- is_rational_play(J,A,H,Y).

J = 1
A = d
H = h([])
Y = [] ;

J = 2
A = d
H = h([a])
Y = [a] ;

J = 1
A = d
H = h([a, a])
Y = [a, a] ;

J = 2
A = d
H = h([a, a, a])
Y = [a, a, a] ;

J = 1
A = d
H = h([a, a, a, a])
Y = [a, a, a, a] ;

No
?- 
*/



%=====================
% end of program
%=====================

return to front page.