OneStep solved with Clingo ASP to solve 2-player game

Lars Ericson
Junior Member

Posts: 67

OneStep solved with Clingo ASP to solve 2-player game Jul 25, 2015 19:14:29 GMT -8

Quote

Post by Lars Ericson on Jul 25, 2015 19:14:29 GMT -8

OneStep required some tweaks to my Python translator from KIF to LP, versus Best Buttons & Lights. This gives a solution to OneStep. Obviously since it is a 2-player game there may be many solutions. I think the trick will be to gather as many solutions as possible in the time limit, then pick the opening move that occurs most frequently among solutions, i.e. the move with the most "outs". Here is the working LP for OneStep for role "white":

role(white).

role(black).

true(o1,1).

legal(white,a,T) :- time(T).

legal(white,b,T) :- time(T).

legal(black,a,T) :- time(T).

true(o2,T+1) :- time(T), does(white,a,T), true(o1,T).

true(o3,T+1) :- time(T), does(white,b,T), true(o1,T).

goal(white,0,T) :- time(T), true(o1,T).

goal(white,10,T) :- time(T), true(o2,T).

goal(white,90,T) :- time(T), true(o3,T).

goal(black,0,T) :- time(T), true(o1,T).

goal(black,90,T) :- time(T), true(o2,T).

goal(black,10,T) :- time(T), true(o3,T).

terminal(T) :- time(T), true(o2,T).

terminal(T) :- time(T), true(o3,T).

1{ does(R,M,T) }1 :- role(R), time(T), legal(R,M,T).

:- does(R,M,T), not legal(R,M,T).

:- 0{ terminal(T) : time(T) }0.

:- terminal(T), role(white), not goal(white,90,T).

time(1..2).

and here is the Clingo solution, obtained in 0.000s:

clingo version 4.5.1

Reading from onestep_white.lp

Solving...

Answer: 1

role(white) role(black) true(o1,1) time(1) time(2) legal(white,a,1) legal(white,a,2) legal(white,b,1) legal(white,b,2) legal(black,a,1) legal(black,a,2) true(o2,2) does(white,a,1) true(o3,2) does(white,b,1) goal(white,0,1) goal(white,10,2) goal(white,90,2) goal(black,0,1) goal(black,90,2) goal(black,10,2) terminal(2) does(white,a,2) does(white,b,2) does(black,a,1) does(black,a,2)

SATISFIABLE

Models : 1

Calls : 1

Time : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)

CPU Time : 0.000s

Jarrod Torriero New Member Posts: 11	OneStep solved with Clingo ASP to solve 2-player game Jul 25, 2015 21:31:04 GMT -8 Quote Select Post Deselect Post Link to Post Member Give Gift Back to Top Post by Jarrod Torriero on Jul 25, 2015 21:31:04 GMT -8 What's the difference between the trick you propose and a pure Monte Carlo approach that rounds non-maximum scores to 0?

Lars Ericson
Junior Member

Posts: 67

OneStep solved with Clingo ASP to solve 2-player game Jul 26, 2015 8:14:52 GMT -8 via mobile

Quote

Post by Lars Ericson on Jul 26, 2015 8:14:52 GMT -8

The Clingo solver operates on the rules of the game to find a solution. MC operates on a function of the game (set of paths of game). In general I don't think you can infer the rules of the game from playouts of the game, but you can make playouts of the game from the rules. So Clingo is operating from more information than MC. Clingo also has a lot of research behind it on how to find models of sets of propositions. MC has a single idea and fewer improvements.

Jarrod Torriero
New Member

Posts: 11

OneStep solved with Clingo ASP to solve 2-player game Jul 26, 2015 18:26:02 GMT -8

Quote

Post by Jarrod Torriero on Jul 26, 2015 18:26:02 GMT -8

Sure, but those are all internal details. In terms of output (final move selection), though, is there a difference?

EDIT: To be clear, I'm only asking about the trick you posted ('gather as many solutions as possible in the time limit, then pick the opening move that occurs most frequently among solutions'). I'm sure you can get all sorts of useful outputs from Clingo that you couldn't get from pure MC.

Last Edit: Jul 26, 2015 18:35:59 GMT -8 by Jarrod Torriero

Lars Ericson
Junior Member

Posts: 67

OneStep solved with Clingo ASP to solve 2-player game Jul 27, 2015 10:09:38 GMT -8

Quote

Post by Lars Ericson on Jul 27, 2015 10:09:38 GMT -8

I haven't actually got that far, but that trick is same as what you would do in Monte Carlo, which is weight more frequent paths leading to a high-scoring terminal state higher than paths where there are fewer ways to get to a different high-scoring state. This is on the intuition that if there are more ways to get to a particular final state, you will have more outs if you pick a move towards that state than towards one that you've observed fewer paths toward.

I am currently stuck on Untwisty Corridor. The translation to ASP is unsatisfiable under Clingo and I'm not sure why yet. I read the game and I think if you just go "hhhhhhhh" then you get 100, so it should have a solution.

Lars Ericson
Junior Member

Posts: 67

OneStep solved with Clingo ASP to solve 2-player game Jul 27, 2015 20:18:34 GMT -8

Quote

Post by Lars Ericson on Jul 27, 2015 20:18:34 GMT -8

I have updated my kif to lp parser. Note that the LP above for OneStep leads to a model where each role performs multiple actions for both steps. The following translation eliminates this problem:

role(white).

role(black).

true(o1,1).

legal(white,a,T) :- time(T), not terminal(T).

input(white,a).

legal(white,b,T) :- time(T), not terminal(T).

input(white,b).

legal(black,a,T) :- time(T), not terminal(T).

input(black,a).

true(o2,T+1) :- time(T), does(white,a,T), true(o1,T).

true(o3,T+1) :- time(T), does(white,b,T), true(o1,T).

goal(white,0,T) :- time(T), true(o1,T).

goal(white,10,T) :- time(T), true(o2,T).

goal(white,90,T) :- time(T), true(o3,T).

goal(black,0,T) :- time(T), true(o1,T).

goal(black,90,T) :- time(T), true(o2,T).

goal(black,10,T) :- time(T), true(o3,T).

terminal(T) :- time(T), true(o2,T).

terminal(T) :- time(T), true(o3,T).

1{ does(R,M,T) : input(R,M) }1 :- role(R), time(T), legal(R,M,T).

:- does(R,M,T), not legal(R,M,T).

:- 0{ terminal(T) : time(T) }0.

:- terminal(T), role(white), not goal(white,90,T).

time(1..2).

The differences from my initial post are as follows:

1. legal(R,M) gets translated to

legal(R,M,T) :- time(T), not terminal(T).

input(R,M).

before it was just translated to

legal(R,M,T) :- time(T).

This eliminates the problem of moves on time step 2 which is terminal.

2. Because we add an "input" rule for each top-level "legal" rule ("inputs" are missing from onestep.kif), instead of outputting

1{ does(R,M,T) }1 :- role(R), time(T), legal(R,M,T).

we output

1{ does(R,M,T) : input(R,M) }1 :- role(R), time(T), legal(R,M,T).

This eliminates the problem of multiple moves per timestep.

The resulting model is then:

clingo version 4.5.1

Reading from onestep_white.lp

Solving...

Answer: 1

role(white) role(black) true(o1,1) input(white,a) input(white,b) input(black,a) time(1) time(2) legal(white,a,1) terminal(2) legal(white,b,1) legal(black,a,1) true(o2,2) does(white,a,1) true(o3,2) does(white,b,1) goal(white,0,1) goal(white,10,2) goal(white,90,2) goal(black,0,1) goal(black,90,2) goal(black,10,2) does(black,a,1)

SATISFIABLE

Models : 1

Calls : 1

Time : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)

CPU Time : 0.016s

General Game Playing

OneStep solved with Clingo ASP to solve 2-player game

Post by Lars Ericson on Jul 25, 2015 19:14:29 GMT -8

Post by Jarrod Torriero on Jul 25, 2015 21:31:04 GMT -8

Post by Lars Ericson on Jul 26, 2015 8:14:52 GMT -8

Post by Jarrod Torriero on Jul 26, 2015 18:26:02 GMT -8

Post by Lars Ericson on Jul 27, 2015 10:09:38 GMT -8

Post by Lars Ericson on Jul 27, 2015 20:18:34 GMT -8

Quick Reply