Frontier Software

Robert Laing's programing notes

Tic Tac Toe

By Robert Laing

  getmoves:getlegals(GGPDict, JStart, Legals),
  
  bestmove:makemove(GGPDict, State, Move, Next),
  
  getmoves:get_state(GGPDict, Next, _Id, Goal),
  
  getmoves:get_move(GGPDict, Move, MID),
  
  bestmove(GGPDict, TimeLimit, State, Bestmove),
DROP TABLE tictactoe_states CASCADE;
DROP TABLE tictactoe_moves CASCADE;
DROP TABLE tictactoe_graph CASCADE;

CREATE TABLE IF NOT EXISTS tictactoe_states 
    (    id              SERIAL PRIMARY KEY
    ,    state           JSONB UNIQUE
    ,    goal            JSONB  -- NULL for non-terminal states
    );

CREATE TABLE IF NOT EXISTS tictactoe_moves
    (    id            SERIAL PRIMARY KEY
    ,    move          JSONB UNIQUE
    );

CREATE TABLE IF NOT EXISTS tictactoe_graph 
    (    init_id      INTEGER REFERENCES tictactoe_states(id)
    ,    move_id      INTEGER REFERENCES tictactoe_moves(id)
    ,    next_id      INTEGER REFERENCES tictactoe_states(id)
    ,    utility      JSONB
    ,    mobility     JSONB
    ,    visits       INTEGER DEFAULT 0
    ,    total        JSONB
    ,    PRIMARY KEY  (init_id, move_id)
    );

rewrite valmoves to use the difference between values sum goals, adding player goal values and subtracting opponent goal values this means winning moves remain 100, but losing moves are -100 instead of zero

http://games.ggp.org/stanford/games/tictactoe3/rulesheet.kif

Dynamic Programming

Focus on mobility Needs to work through layers of tree until player’s turn again

Pick minimums of opponent moves, with maximum own moves a tie breaker

[ mob(6, ‘[[“does”, “white”, [“mark”, 3, 3]], [“does”, “black”, “noop”]]'), mob(6, ‘[[“does”, “white”, [“mark”, 3, 2]], [“does”, “black”, “noop”]]'), mob(6, ‘[[“does”, “white”, [“mark”, 3, 1]], [“does”, “black”, “noop”]]'), % WRONG mob(6, ‘[[“does”, “white”, [“mark”, 2, 3]], [“does”, “black”, “noop”]]'), mob(1, ‘[[“does”, “white”, [“mark”, 2, 1]], [“does”, “black”, “noop”]]'), mob(6, ‘[[“does”, “white”, [“mark”, 1, 3]], [“does”, “black”, “noop”]]'), % WRONG mob(1, ‘[[“does”, “white”, [“mark”, 1, 2]], [“does”, “black”, “noop”]]')]

pick_max(Dict, State, ValMoves, Bestmove) :-
  json_terms(State, Terms),
  member(control(Player), Terms),
  getaverages(Dict, Player, State, ValMoves, [], Averages),
  sort(1, @>=, Averages, Sorted),
  [avg(Max, _, _)|_] = Sorted,
  findall(UMaxMove, member(avg(Max, 0, UMaxMove), Sorted), UMaxMoves),
  (   UMaxMoves == []
  ->  (  findall(MaxMove, member(avg(Max, _, MaxMove), Sorted), MaxMoves),
         random_member(Bestmove, MaxMoves)
      )
  ;   random_member(Bestmove, UMaxMoves)
  ).
with recursive
  Ancestor(a,d) as (select init_id as a, next_id as d from tictactoe_graph
                    union
                    select Ancestor.a, tictactoe_graph.next_id as d
                    from Ancestor, tictactoe_graph
                    where Ancestor.d = tictactoe_graph.init_id)
select a from Ancestor where d = 6;

with recursive
  Ancestor(a,d) as (select init_id as a, next_id as d from tictactoe_graph
                    union
                    select Ancestor.a, tictactoe_graph.next_id as d
                    from Ancestor, tictactoe_graph
                    where Ancestor.d = tictactoe_graph.init_id)
select a from Ancestor where d = 8;
ancestor(Parent, Child) :-
    parentof(Parent, Child).

ancestor(Ancestor, Child) :-
    parentof(Descendent, Child),
    ancestor(Ancestor, Descendent).
ancestor(Parent, Child) :-
    parentof(Parent, Child).

ancestor(Ancestor, Child) :-
    parentof(Ancestor, Descendent), 
    ancestor(Descendent, Child).

[ avg(66.66666666666667, 3, ‘[[“does”, “white”, [“mark”, 3, 3]], [“does”, “black”, “noop”]]'), avg(50, 0, ‘[[“does”, “white”, [“mark”, 3, 2]], [“does”, “black”, “noop”]]'), avg(50, 0, ‘[[“does”, “white”, [“mark”, 3, 1]], [“does”, “black”, “noop”]]'), avg(50, 0, ‘[[“does”, “white”, [“mark”, 2, 3]], [“does”, “black”, “noop”]]'), avg(0, 1, ‘[[“does”, “white”, [“mark”, 2, 1]], [“does”, “black”, “noop”]]'), avg(50, 1, ‘[[“does”, “white”, [“mark”, 1, 3]], [“does”, “black”, “noop”]]'), avg(50, 0, ‘[[“does”, “white”, [“mark”, 1, 2]], [“does”, “black”, “noop”]]')] .

kif

https://www.postgresql.org/docs/13/functions-json.html

https://levelup.gitconnected.com/working-with-a-jsonb-array-of-objects-in-postgresql-d2b7e7f4db87

bug when terminals share parents

id = 3 [[“control”, “black”], [“cell”, 1, 1, “x”], [“cell”, 1, 2, “b”], [“cell”, 1, 3, “x”], [“cell”, 2, 1, “b”], [“cell”, 2, 2, “o”], [“cell”, 2, 3, “b”], [“cell”, 3, 1, “b”], [“cell”, 3, 2, “b”], [“cell”, 3, 3, “b”]]

id = 15 [[“control”, “white”], [“cell”, 1, 1, “x”], [“cell”, 1, 2, “o”], [“cell”, 1, 3, “x”], [“cell”, 2, 1, “b”], [“cell”, 2, 2, “o”], [“cell”, 2, 3, “b”], [“cell”, 3, 1, “b”], [“cell”, 3, 2, “b”], [“cell”, 3, 3, “b”]]

id = 16 [[“control”, “white”], [“cell”, 1, 1, “x”], [“cell”, 1, 2, “b”], [“cell”, 1, 3, “x”], [“cell”, 2, 1, “o”], [“cell”, 2, 2, “o”], [“cell”, 2, 3, “b”], [“cell”, 3, 1, “b”], [“cell”, 3, 2, “b”], [“cell”, 3, 3, “b”]]

id = 56 [[“control”, “black”], [“cell”, 1, 1, “x”], [“cell”, 1, 2, “x”], [“cell”, 1, 3, “x”], [“cell”, 2, 1, “o”], [“cell”, 2, 2, “o”], [“cell”, 2, 3, “b”], [“cell”, 3, 1, “b”], [“cell”, 3, 2, “b”], [“cell”, 3, 3, “b”]]

Last updated on 12 Jan 2021
Published on 12 Jan 2021

Content Footer