Toggle navigation
?
users online
Logout
Open hangout
Open chat for current file
:- dynamic true/1, does/2, bestval/1. role(robot). base(cell(M, N, P)) :- row(M), col(N), piece(P). base(captures(M)) :- scoremap(M, _N). base(step(N)) :- between(1, 16, N). input(robot, move(M1, N1, M2, N2)) :- row(M1), col(N1), knightmove(M1, N1, M2, N2). row(1). row(2). row(3). row(4). row(5). col(1). col(2). col(3). piece(knight). piece(pawn). piece(blank). init(cell(1, 1, knight)). init(cell(1, 2, pawn)). init(cell(1, 3, pawn)). init(cell(2, 1, pawn)). init(cell(2, 2, pawn)). init(cell(2, 3, pawn)). init(cell(3, 1, pawn)). init(cell(3, 2, pawn)). init(cell(3, 3, pawn)). init(cell(4, 1, pawn)). init(cell(4, 2, pawn)). init(cell(4, 3, pawn)). init(cell(5, 1, pawn)). init(cell(5, 2, pawn)). init(cell(5, 3, pawn)). init(captures(0)). init(step(1)). legal(robot, move(M1, N1, M2, N2)) :- true(cell(M1, N1, knight)), knightmove(M1, N1, M2, N2). next(cell(M2, N2, knight)) :- does(robot, move(_M1, _N1, M2, N2)). next(cell(M1, N1, blank)) :- does(robot, move(M1, N1, _M2, _N2)). next(cell(U, V, pawn)) :- true(cell(U, V, pawn)), does(robot, move(_M1, _N1, M2, _N2)), U \== M2. next(cell(U, V, pawn)) :- true(cell(U, V, pawn)), does(robot, move(_M1, _N1, _M2, N2)), V \== N2. next(cell(U, V, blank)) :- true(cell(U, V, blank)), does(robot, move(_M1, _N1, M2, _N2)), U \== M2. next(cell(U, V, blank)) :- true(cell(U, V, blank)), does(robot, move(_M1, _N1, _M2, N2)), V \== N2. next(captures(Old)) :- does(robot, move(_M1, _N1, M2, N2)), true(cell(M2, N2, blank)), true(captures(Old)). next(captures(New)) :- does(robot, move(_M1, _N1, M2, N2)), true(cell(M2, N2, pawn)), true(captures(Old)), succ(Old, New). next(step(New)) :- true(step(Old)), succ(Old, New). goal(robot, Goal) :- true(captures(Count)), scoremap(Count, Goal). terminal :- true(step(16)). knightmove(M1, N1, M2, N2) :- add1row(M1, M2), add2col(N1, N2). knightmove(M1, N1, M2, N2) :- add1row(M1, M2), add2col(N2, N1). knightmove(M1, N1, M2, N2) :- add1row(M2, M1), add2col(N1, N2). knightmove(M1, N1, M2, N2) :- add1row(M2, M1), add2col(N2, N1). knightmove(M1, N1, M2, N2) :- add2row(M1, M2), add1col(N1, N2). knightmove(M1, N1, M2, N2) :- add2row(M1, M2), add1col(N2, N1). knightmove(M1, N1, M2, N2) :- add2row(M2, M1), add1col(N1, N2). knightmove(M1, N1, M2, N2) :- add2row(M2, M1), add1col(N2, N1). add1row(1, 2). add1row(2, 3). add1row(3, 4). add1row(4, 5). add2row(1, 3). add2row(2, 4). add2row(3, 5). add1col(1, 2). add1col(2, 3). add2col(1, 3). scoremap(0, 0). scoremap(1, 1). scoremap(2, 3). scoremap(3, 7). scoremap(4, 11). scoremap(5, 16). scoremap(6, 22). scoremap(7, 29). scoremap(8, 37). scoremap(9, 45). scoremap(10, 54). scoremap(11, 64). scoremap(12, 75). scoremap(13, 87). scoremap(14, 100). findinits(Start) :- findall(Base, init(Base), Unsorted), sort(Unsorted, Start). update_state(State) :- retractall(true(_)), forall(member(Base, State), assertz(true(Base))). update_does(Player, Action) :- retractall(does(Player, _)), assertz(does(Player, Action)). findlegals(Role, Legals) :- findall(legal(Role, Action), legal(Role, Action), Unsorted), sort(Unsorted, Legals). findnext(legal(Role, Action), Next) :- update_does(Role, Action), findall(Base, next(Base), Unsorted), sort(Unsorted, Next). update_bestval(Val) :- (bestval(Best); Best = 0), ( Val > Best -> retractall(bestval(_)), assertz(bestval(Val)) ; true ). findreward(Role, State, goal(Role, Reward)) :- update_state(State), goal(Role, Reward), update_bestval(Reward). combinelists(_, [], [], [], []). combinelists(State, [legal(Player, Action)|Legals], [Next|Nexts], [Goal|Goals], [move(State, does(Player, Action), Next, Goal)|Moves]) :- combinelists(State, Legals, Nexts, Goals, Moves). generatemoves_(_, []) :- terminal. generatemoves_(Parent, Moves) :- \+terminal, role(Player), findlegals(Player, Legals), maplist(findnext, Legals, Nexts), maplist(findreward(Player), Nexts, Rewards), combinelists(Parent, Legals, Nexts, Rewards, Moves). generatemoves(Parent, Moves) :- update_state(Parent), generatemoves_(Parent, Moves), !. remove_culdesacs([], Graph, Graph). remove_culdesacs([move(Parent, _, _, _)|DeadEnds], GraphIn, Acc) :- findall(move(Grandparent, Action, Parent, Goal), ( member(move(Grandparent, Action, Parent, Goal), GraphIn), \+memberchk(move(Parent, _, _, _), GraphIn) ), Ps), subtract(GraphIn, Ps, GraphOut), append(Ps, DeadEnds, Unsorted), sort(Unsorted, NewDeadEnds), remove_culdesacs(NewDeadEnds, GraphOut, Acc). removestep(move(Parent, _, _, _), NoStep) :- select(step(_), Parent, NoStep). deadleaf(move(_Parent, _, Child, goal(_, Value))) :- Value < 100, update_state(Child), terminal. cycle(NoSteps, move(_Parent, _, Child, _)) :- select(step(_), Child, NoStep), memberchk(NoStep, NoSteps). badval(move(Parent, _, _, goal(_, Val))) :- memberchk(step(M), Parent), succ(N, M), scoremap(N, Score), Val < Score. deadstate(Limit, NoSteps, move(Parent, Action, Child, Goal)) :- memberchk(step(Limit), Parent), ( deadleaf(move(Parent, Action, Child, Goal)) ; cycle(NoSteps, move(Parent, Action, Child, Goal)) ; badval(move(Parent, Action, Child, Goal)) ). childless(M, Graph, move(Parent, _, Child, _)) :- succ(N, M), member(step(N), Parent), \+memberchk(move(Child, _, _, _), Graph). prune(Limit, Unpruned, Pruned) :- maplist(removestep, Unpruned, NoSteps), exclude(deadstate(Limit, NoSteps), Unpruned, G3), partition(childless(Limit, G3), G3, Childless, G4), remove_culdesacs(Childless, G4, Pruned). getchildren(Parent, Visited, Children) :- generatemoves(Parent, Moves), findall(Move, (member(Move, Moves), \+memberchk(Move, Visited)), NoDuplicates), sort(NoDuplicates, Children). depthfirst(_, [], RGraph, Graph) :- reverse(RGraph, Graph). depthfirst(Limit, [move(Parent, Action, Child, Goal)|Frontier], Visited, Acc) :- memberchk(step(Depth), Child), Depth \== Limit, depthfirst(Limit, Frontier, [move(Parent, Action, Child, Goal)|Visited], Acc). depthfirst(Limit, [move(Parent, Action, Child, Goal)|Frontier], Visited, Acc) :- memberchk(step(Limit), Child), getchildren(Child, Visited, GrandChildren), append(GrandChildren, Frontier, NewFrontier), depthfirst(Limit, NewFrontier, [move(Parent, Action, Child, Goal)|Visited], Acc). iterative_deepening(_, Graph, Graph, 100) :- memberchk(move(_, _, _, goal(_, 100)), Graph). iterative_deepening(Depth, GraphIn, Acc, Best) :- \+memberchk(move(_, _, _, goal(_, 100)), GraphIn), depthfirst(Depth, GraphIn, [], Unpruned), ( Unpruned \== GraphIn -> prune(Depth, Unpruned, GraphOut), succ(Depth, Limit), iterative_deepening(Limit, GraphOut, Acc, Best) ; bestval(Best), Acc = GraphIn ). getactions(Start, Graph, [Node|_], Actions, [Action|Actions]) :- member(move(Start, Action, Node, _), Graph). getactions(Start, Graph, [Child|Path], Actions, Acc) :- member(move(Parent, Action, Child, _), Graph), Parent \== Start, getactions(Start, Graph, [Parent, Child|Path], [Action|Actions], Acc). route(Actions) :- retractall(bestval(_)), assertz(bestval(0)), findinits(Start), getchildren(Start, [], G1), prune(1, G1, G2), iterative_deepening(2, G2, G3, Best), member(move(_, _, End, goal(_, Best)), G3), getactions(Start, G3, [End], [], Actions).