? users online
  • Logout
    • Open hangout
    • Open chat for current file
<div class="notebook">

<div class="nb-cell markdown" name="md1">
# Wumpus World - Improvements
  - Alexandre Dietrich
  - Patrick Chabelski
  - Rodolfo Vasconcelos

SCS 3547 – Intelligent Agents &amp; Reinforcement Learning

UNIVERSITY OF TORONTO - SCHOOL OF CONTINUING STUDIES

Instructor: Larry Simon

July, 5th, 2020

GitHub: https://github.com/ravasconcelos/wumpus_world/

# About the Project
This Prolog implementation of Wumpus World has some improvements afer the analysis made on the original code.

More details can be found in this other Notebook: https://swish.swi-prolog.org/p/Wumpus%20World%20-%20Explained.swinb

The original code is implemented by Richard O. Legendi and can be found at https://github.com/rlegendi/wumpus-prolog/

# Main changes:
1. Change the gold location as per [Fig. 7.2](https://raw.githubusercontent.com/ravasconcelos/wumpus_world/master/images/figure_7_2.png)
1. Remove unused code
1. Create a KB for nodes that are "OK", which can be safely trasversed
1. Ask_KB:
	1. Consult preffered moves
	1. Let to revisit a location
	1. Check for adjacent cells
</div>

<div class="nb-cell query" name="q1">
start.
</div>

<div class="nb-cell program" data-background="true" name="p1">
%------------------------------------------------------------------------------
% A Prolog Implementation of the Wumpus World based on the 
% work developed by Richard O. Legendi
% https://github.com/rlegendi/wumpus-prolog/
% 
% - Alexandre Dietrich
% - Patrick Chabelski
% - Rodolfo Vasconcelos
%
% SCS 3547 – Intelligent Agents &amp; Reinforcement Learning
%
% UNIVERSITY OF TORONTO - SCHOOL OF CONTINUING STUDIES
%
% Instructor: Larry Simon
% 
% July, 5th, 2020
% 
% Usage:
% consult this file
% ?-start.
%
%------------------------------------------------------------------------------


%------------------------------------------------------------------------------
% Declaring dynamic methods

:- dynamic ([
	     agent_location/1,
	     gold_location/1,
	     pit_location/1,
	     time_taken/1,
	     score/1,
	     visited_cells/1,
	     world_size/1,
	     wumpus_location/1,
         isPit/2,
         isWumpus/2,
         isGold/2,
         isOK/2
	    ]).


%------------------------------------------------------------------------------
% To start the game

start :-
    format('Initializing started...~n', []),
    init, 
    format('Let the game begin!~n', []),
    take_steps([]).

%------------------------------------------------------------------------------
% Scheduling simulation:

step_pre(VisitedList) :-
    agent_location(AL),
    gold_location(GL),
    wumpus_location(WL),
    pit_location(PL),
    score(S),
    time_taken(T),

    ( AL=GL -&gt; writeln('WON!'), format('Score: ~p,~n Time: ~p', [S,T])
    ; AL=WL -&gt; format('Lost: Wumpus eats you!~n', []), 
               format('Score: ~p,~n Time: ~p', [S,T])
    ; AL=PL -&gt; format('Lost: you fell into the pit!~n', []), 
               format('Score: ~p,~n Time: ~p', [S,T])
    ; take_steps(VisitedList)
    ).

take_steps(VisitedList) :-
    format('~n~n~n', []),
    agent_location(AL),
    format('New Round: I am at ~p and I have visieted ~p~n', [AL,VisitedList]),

    retractall( isOK(_, AL) ),
    assert( isOK(yes, AL) ),
    retractall( isPit(_, AL) ),
    assert( isPit(no, AL) ),
    retractall( isWumpus(_, AL) ),
    assert( isWumpus(no, AL) ),
    retractall( isGold(_, AL) ),
    assert( isGold(no, AL) ),

    make_percept_sentence(Perception),
    format('I\'m in ~p, seeing: ~p~n', [AL,Perception]),

    update_KB(Perception, VisitedList),
    VL = [AL|VisitedList],
    ask_KB(VisitedList, Action),
    format('I\'m going to: ~p~n', [Action]),
    
    update_time,
    update_score,

    format('VisitedList = ~p~n', [VL]),
    standing,
    step_pre(VL).

%------------------------------------------------------------------------------
% Updating states

update_time :-
    time_taken(T),
    NewTime is T+1,
    retractall( time_taken(_) ),
    assert( time_taken(NewTime) ),
    format('New time: ~p~n', [NewTime]).

update_score :-
    agent_location(AL),
    gold_location(GL),
    wumpus_location(WL),
    update_score(AL, GL, WL).

update_score(P) :-
    score(S),
    NewScore is S+P,
    retractall( score(_) ),
    assert( score(NewScore) ),
    format('New score: ~p~n', [NewScore]).

update_score(AL, AL, _) :-
    update_score(1000).

update_score(_,_,_) :-
    update_score(-1).

update_agent_location(NewAL) :-
    retractall( agent_location(_) ),
    assert( agent_location(NewAL) ),
    format('New Agent Location: ~p~n', [NewAL]).

is_pit(no,  X) :-
    \+ pit_location(X).
is_pit(yes, X) :-
    pit_location(X).

%------------------------------------------------------------------------------
% Display standings

standing :-
    wumpus_location(WL),
    gold_location(GL),
    agent_location(AL),

    ( is_pit(yes, AL) -&gt; format('Agent was fallen into a pit!~n', []),
      fail
    ; stnd(AL, GL, WL)
    ).

stnd(AL, AL, _) :-
    format('AGENT FOUND THE GOLD!!', []),
    true.

stnd(AL, _, AL) :-
    format('YIKES! You\'re eaten by the wumpus!', []),
    fail. 

stnd(_, _, _) :-
    format('There\'s still something to do...~n', []). 

%------------------------------------------------------------------------------
% Perceptotion
make_percept_sentence([Stench,Bleeze,Glitter]) :-
    format('make_percept_sentence... ~p,~p,~p ~n', [Stench,Bleeze,Glitter]),
	smelly(Stench),
    format('Stench... ~p ~n', [Stench]),
	bleezy(Bleeze),
	glittering(Glitter).

%------------------------------------------------------------------------------
% Initializing

init :-
    init_game,
    init_land_fig72,
    init_agent,
    init_wumpus,
    init_kb.

init_game :-
    retractall( time_taken(_) ),
    assert( time_taken(0) ),

    retractall( score(_) ),
    assert( score(0) ),

    retractall( isWumpus(_,_) ),
    retractall( isGold(_,_) ),

    retractall( visited_cells(_) ),
    assert( visited_cells([]) ).

% To set the situation described in Russel-Norvig's book (2nd Ed.),
% according to Figure 7.2
init_land_fig72 :-
    
    retractall( isPit(_, _) ),
    assert( isPit(maybe,[1,3]) ),

    retractall( world_size(_) ),
    assert( world_size(4) ),

    retractall( gold_location(_) ),
    assert( gold_location([3,2]) ),

    retractall( pit_location(_) ),
    assert( pit_location([4,4]) ),
    assert( pit_location([3,3]) ),
    assert( pit_location([1,3]) ).

init_kb :-
    retractall(isOK(_,_)).

init_agent :-
    retractall( agent_location(_) ),
    assert( agent_location([1,1]) ).

init_wumpus :-
    retractall( wumpus_location(_) ),
    assert( wumpus_location([3,1]) ).

%------------------------------------------------------------------------------
% Perceptors

adj(1,2).
adj(2,1).
adj(2,3).
adj(3,2).
adj(3,4).
adj(4,3).

adjacent( [X1, Y1], [X2, Y2] ) :-
    ( X1 = X2, adj( Y1, Y2 )
    ; Y1 = Y2, adj( X1, X2 )
    ).

isSmelly(Ls1) :-
    wumpus_location( Ls2 ),
    adjacent( Ls1, Ls2 ).

isBleezy(Ls1) :-
    pit_location( Ls2 ),
    adjacent( Ls1, Ls2 ).

isGlittering( [X1, Y1] ) :-
    gold_location( [X2, Y2] ),
    X1 = X2,
    Y1 = Y2.

bleezy(yes) :-
    agent_location(AL),
    isBleezy(AL).
bleezy(no).

smelly(yes) :-
    agent_location(AL),
    isSmelly(AL),
    format('smelly=yes ~n', []).
smelly(no) :-
    format('smelly=no ~n', []).

glittering(yes) :-
    agent_location(AL),
    isGlittering(AL).
glittering(no).

%------------------------------------------------------------------------------
% Knowledge Base:

update_KB( [Stench,Bleeze,Glitter], VisitedList ) :-
    format('update_KB ~p~n', [[Stench,Bleeze,Glitter]]),  
    add_wumpus_KB(Stench,VisitedList),
    add_pit_KB(Bleeze,VisitedList),
    add_gold_KB(Glitter),
    add_ok_KB([Stench, Bleeze], VisitedList).

add_ok_KB([Stench,Bleeze], VisitedList) :- 
    format('add_ok_KB ~p,~p~n', [Stench,Bleeze]),
	agent_location([X,Y]),
    ( not_member([X,Y], VisitedList) -&gt;  
	    format('Not visited before= ~p~n', [[X,Y]]),
        Z1 is Y+1,
      	Z2 is Y-1,
      	Z3 is X+1,
      	Z4 is X-1,
      	add_ok_KB_item([X,Z1]),
      	add_ok_KB_item([X,Z2]),
      	add_ok_KB_item([Z3,Y]),
      	add_ok_KB_item([Z4,Y])
    ;   
    format('Already visited before= ~p~n', [[X,Y]])
    ).
    
add_ok_KB_item(L) :-
	format('add_ok_KB_item ~p~n', [L]),
    (	permitted(L) -&gt; 
    	isWumpus(IS_WUMPUS,L),
    	isPit(IS_PIT,L),
        assume_ok(IS_WUMPUS,IS_PIT,L) 
    ;
    	format('~p is not permitted~n', [L])	
	).

add_wumpus_KB(Stench,VisitedList) :-
    format('add_wumpus_KB ~p~n', [Stench]),
	agent_location([X,Y]),
    ( not_member([X,Y], VisitedList) -&gt;  
	    format('Not visited before= ~p~n', [[X,Y]]),
        Z1 is Y+1,
      	Z2 is Y-1,
      	Z3 is X+1,
      	Z4 is X-1,
      	(	permitted([X,Z1]) -&gt; (assume_wumpus(Stench,[X,Z1])) ;format('~p is not permitted~n', [[X,Z1]])	),
      	(	permitted([X,Z2]) -&gt; (assume_wumpus(Stench,[X,Z2])) ;format('~p is not permitted~n', [[X,Z2]])	),
      	(	permitted([Z3,Y]) -&gt; (assume_wumpus(Stench,[Z3,Y])) ;format('~p is not permitted~n', [[Z3,Y]])	),
      	(	permitted([Z4,Y]) -&gt; (assume_wumpus(Stench,[Z4,Y])) ;format('~p is not permitted~n', [[Z4,Y]])	)
    ;   
    format('Already visited before= ~p~n', [[X,Y]])
    ).

add_pit_KB(Bleeze,VisitedList) :-
    format('add_pit_KB ~p~n', [Bleeze]),
	agent_location([X,Y]),
    ( not_member([X,Y], VisitedList) -&gt;  
	    format('Not visited before= ~p~n', [[X,Y]]),
        Z1 is Y+1,
      	Z2 is Y-1,
      	Z3 is X+1,
      	Z4 is X-1,
      	(	permitted([X,Z1]) -&gt; (assume_pit(Bleeze,[X,Z1])) ;format('~p is not permitted~n', [[X,Z1]])	),
      	(	permitted([X,Z2]) -&gt; (assume_pit(Bleeze,[X,Z2])) ;format('~p is not permitted~n', [[X,Z2]])	),
      	(	permitted([Z3,Y]) -&gt; (assume_pit(Bleeze,[Z3,Y])) ;format('~p is not permitted~n', [[Z3,Y]])	),
      	(	permitted([Z4,Y]) -&gt; (assume_pit(Bleeze,[Z4,Y])) ;format('~p is not permitted~n', [[Z4,Y]])	)
    ;   
    format('Already visited before= ~p~n', [[X,Y]])
    ).

add_gold_KB(Glitter) :-
    format('add_gold_KB ~p~n', [Glitter]),
    assume_gold(Glitter).

assume_wumpus(no, L) :-
    retractall( isWumpus(_, L) ),
    assert( isWumpus(no, L) ),
    format('KB learn ~p - no Wumpus there!~n', [L]).

assume_wumpus(yes, L) :-
	format('KB learn ~p - is it a Wumpus?~n', [L]),
    ( isWumpus(no, L) -&gt; 
    	format('I know there is no Wumpus at ~p!~n',[L])
    ;
    	retractall( isWumpus(_, L) ),
    	assert( isWumpus(maybe, L) ),
    	format('KB learn ~p - maybe there is a Wumpus!~n', [L])
    ).

assume_pit(no, L) :-
    retractall( isPit(_, L) ),
    assert( isPit(no, L) ),
    format('KB learn ~p - there\'s no Pit there!~n', [L]).

assume_pit(yes, L) :-
	format('KB learn ~p - is it a Pit?~n', [L]),
    ( isPit(no, L) -&gt; 
    	format('I know there is no Pit at ~p!~n',[L])
    ;
    	retractall( isPit(_, L) ),
    	assert( isPit(maybe, L) ),
    	format('KB learn ~p - maybe there is a Pit!~n', [L])
    ).

assume_gold(no) :-
    agent_location(L),
    retractall( isGold(_, L) ),
    assert( isGold(no, L) ),
    format('KB learn ~p - there\'s no gold here!~n', [L]).

assume_gold(yes) :-
    agent_location(L),
    retractall( isGold(_, L) ),
    assert( isGold(yes, L) ),
    format('KB learn ~p - GOT THE GOLD!!!~n', [L]).

assume_ok(no,no,L) :-
    format('assume_ok(no,no,L) ~p~n', [L]),
    retractall( isOK(_, L) ),
    assert( isOK(yes, L) ),
    format('KB learn ~p is OK~n', [L]).

assume_ok(maybe,no,L) :-
    format('assume_ok(maybe,no,L) ~p~n', [L]),
	( not(isOK(yes, L)) -&gt;  
    retractall( isOK(_, L) ),
    assert( isOK(no, L) ),
    format('KB learn ~p is NOT OK~n', [L])
    ;   
    format('KB learn ~p is OK~n', [L])).

assume_ok(no,maybe,L) :-     
    format('assume_ok(no,maybe,L) ~p~n', [L]),
	( not(isOK(yes, L)) -&gt;  
    retractall( isOK(_, L) ),
    assert( isOK(no, L) ),
    format('KB learn ~p is NOT OK~n', [L])
    ;   
    format('KB learn ~p is OK~n', [L])).

assume_ok(maybe,maybe,L) :-
    format('assume_ok(maybe,maybe,L) ~p~n', [L]),
	( not(isOK(yes, L)) -&gt;  
    retractall( isOK(_, L) ),
    assert( isOK(no, L) ),
    format('KB learn ~p is NOT OK~n', [L])
    ;   
    format('KB learn ~p is OK~n', [L])).

permitted([X,Y]) :-
    world_size(WS),
    0 &lt; X, X &lt; WS+1,
    0 &lt; Y, Y &lt; WS+1.

ask_KB(VisitedList, Action) :-
    format('ask_KB VisitedList=~p - Action=~p~n', [VisitedList,Action]),
    agent_location(AL),
    format('agent_location=~p~n', [AL]),
    preferred_move(IS_PREFERRED,VisitedList, L),
    format('Let\'s see if ~p is OK~n', [L]),
    (yes=IS_PREFERRED -&gt; format('~p is the preffered move~n', [L])
    ; format('~p is NOT the preffered mov~n', [L])
    ),
    adjacent(L, AL),
    format('L=~p is adjacent to AL_=~p~n', [L,AL]),
    not(nextto(L,AL,VisitedList)), 
    format('There is no loop~n', []),
    update_agent_location(L),
    format('Assume L as the new location= ~p~n', [L]),
    Action = L.

preferred_move(yes,VisitedList, L) :-
    isOK(yes,L),
    format('preferred_move - Let\'s see if ~p is OK~n', [L]),
    not_member(L,VisitedList),
    format('preferred_move - L was not visited before= ~p~n', [L]).

preferred_move(no,_, L):-
    isOK(yes,L),
    format('preferred_move - Let\'s see if ~p is OK~n', [L]).

%------------------------------------------------------------------------------
% Utils

not_member(_, []).
not_member([X,Y], [[U,V]|Ys]) :-
    ( X=U,Y=V -&gt; fail
    ; not_member([X,Y], Ys)
    ).
</div>

</div>