The Geeks Shall Inherit the Earth

Personal Ramblings of the Techhouse Admin

Skip to: Content | Sidebar | Footer

A Quick A.I. Overview

4 May, 2010 (21:20) | Erlang | By: Brian

For my Erlang exercises, I had to review a couple of software algorithms for searching. I did a quick brush-up on the concepts so that I could understand the old code I wrote, and translate it into the new code. So a couple of quick definitions.

  • Depth-First Search: DFS is the search algorithm I mentioned in the previous post. You keep going down a path until you find what you are looking for or hit a dead-end. Then you back up to your most recent decision and try another path. It’s the opposite of Breadth-First Search, which means to generate all the next steps and check each of those first, then take one of those steps and check all of its next steps.
  • Depth-Limited-Search: A kind of depth-first search where you start with some initial limit of how many steps you want to take. If you hit that number of steps before finding a solution, you back up. This is a great way to avoid problems that can loop on themselves, like chess pieces or our train yard. But what if we don’t know how deep to look?
  • Iterative deepening depth-first search: After creating a depth-limited search, you wrap that search in a process that keeps running that depth-limited-search at increasing depths until you find a solution. So you start at depth 1, if you don’t find anything, go to depth 2, then 3, then 4, and so on, until you find something. If you know something more about your search space, you might decide to start at a higher number, or increase the change in depth by more than one. But this is the basic idea.

The assignment’s next problem is to write a blind search algorithm, (i.e. – one that doesn’t do any analyzing before deciding where to go) to solve the simpler train yards. I chose IIDFS because it’s fairly simple to write and is guaranteed to find the shortest solution, or one of the shortest solutions if there are multiple solutions at the same minimal depth. It’s also pretty good on space and time.

To do this I created a solution state structure and some helper methods for it.

%%% solution state
-record(solution_state, {state = #state{}, moves, depth}).

new_solution(Problem) ->
#solution_state{state = Problem#problem.init_state,
moves = [], depth = 0} .

update_solution(Solution_state, Move) ->
#solution_state{
state = apply_move(Move, Solution_state#solution_state.state),
moves = [Move] ++ Solution_state#solution_state.moves,
depth = Solution_state#solution_state.depth + 1} .

%%print the path of moves that lead from the initial state to the current one in this solution step
print_solution_path(Problem, Solution_state) ->
io:format("Solution state at depth: ~w~n", [Solution_state#solution_state.depth]),
io:format("To go from ~w to~n", [Problem#problem.init_state]),
io:format("~w~n", [Solution_state#solution_state.state]),

io:format("Apply: ~w~n", [lists:reverse(Solution_state#solution_state.moves)]).

And, of course, I created some tests that mostly generate some objects and print them out.

SState1 = new_solution(Yard3),
    SState2 = update_solution(SState1, {left, t2, t1}),
    SState3 = update_solution(SState2, {left, t3, t1}),
    print_solution_path(Yard3, SState3),

Here’s my current work-in-progress on the depth limited search.

%first try to match the goal state
dls_recursive(
    #problem{goal_state = Goal},
    #solution_state{state = Goal} = SState,
    _Limit) ->
    io:format("Goals match: ~w~n", [Goal] ),
    {found, SState};
%then see if we hit bottom
dls_recursive(_Problem,
    #solution_state{depth = Depth}, Limit) when Depth >= Limit ->
    {not_found, max_depth_reached};
%else generate the next possible states and iterate through them
dls_recursive(Problem,
    #solution_state{depth = Depth} = State, Limit) ->
    %expand the solution with all possible moves and go deeper
    New_SStates = expand_solution(Problem, State),
    %get possible states from here
    %try each one until it passes
    dls_recursive(Problem, State, Limit).

%% expand solution
expand_solution(Problem, Solution_State) ->
    lists:map(fun(Move) -> update_solution(Solution_State, Move) end,
        possible_moves(Problem#problem.yard, Solution_State#solution_state.state) ).

I’m still missing the vital chunk that iterates through the list of next steps. The reason that it’s not just a simple map function is that if we hit the solution we want to return that immediately, but if you get a not_found, you keep looking through the list. I’m still trying to figure out what the best way to do a short-circuit/cut-off control is in Erlang.

Iterative deepening depth-first search

Write a comment

You need to login to post comments!