aimacode/aima-pseudocode

Pseudocode descriptions of the algorithms from Russell And Norvig's "Artificial Intelligence - A Modern Approach"

aima-pseudocode's Issues

Variable player initialized but not used in mini-max and alpha-beta in aima4e-algorithms.pdf

In the pdf document for the pseudocodes for 4th edition, in the description for Minimax and Alpha-Beta, the variable player is initialized but not used. I think this is a bug, unless the intention is that this variable be treated as global to be used later within Max-Value and Min-Value, but then, the same could have been done with the variables game and state, that are used within the sub-functions but are not modified.

About the format, the variable player, in its initialization, is not in italic like the rest of the variables. This could be also a bug, unless the intention is that the different format was to indicate the variable is global, but then it should not be in italic within the sub-functions.

Also, in the function Minimax-Search the description of the return value is in italics, and it seems that this format is reserved for variables (in the Alpha-Beta-Search, the description of the return value "an action" is not in italics).

Search Algorithms: Changes as of 12 March 2019

We've gone through several drafts of new algorithms for search. After some student-testing and comments from reviewers, we have a new version, as shown in aima4e-algorithms.pdf and in https://github.com/aimacode/aima-python/blob/master/search4e.ipynb

This version tested better than previous ones, so this is what we're going with, it will require some changes to the 3e version, and even to some work that some of you did earlier on changes to 4e. (Sorry to give you extra work.)

Asymmetric reproduce function in Genetic algorithm

I know this is pedantic, but shouldn't c range from 0 to n instead of 1 to n. Else we would have more of x on average compared to y.
In our application x and y are picked randomly from the same distribution so it won't make a difference, but still it would be nice to have it unaffected by order of arguments.
Genetic algorithm

Suggested modification to Tree-CSP-Solver (aima3e Figure 6.11)

Change the X argument to be csp instead, in the call to TOPOLOGICALSORT, giving :

TOPOLOGICALSORT(csp, root)

As at a minimum information about the constraints the variables are involved with are required to perform the sort.

In addition, add csp as an argument to MAKE-ARC-CONSISTENT, i.e.:

MAKE-ARC-CONSISTENT(csp, PARENT(X_j), X_j)

As again, its necessary to have all of the information on the CSP to determine consistency.

Simulated Annealing returns a Node instead of a state

Figure 4.5 - SIMULATED-ANNEALING describes an optimization algorithm that is supposed to return a state, as per the first line of the function declaration. The rest of the implementation, however, goes on to return a Node instead of its state.

I think the pseudocode should change to match the function declaration (and the standard format of returning states, like other optimisation functions in the book, such as HILL-CLIMBING). Alternatively, however, the function declaration could be amended to return a Node, or/and HILL-CLIMBING could be changed.

is Utility-Based-Agent not implemented ?

Unable to find utility-based-agent. does it have another name here or it has not been implemented yet.

Suggested modifications to Genetic-Algorithm (aima3e Figure 4.8)

It would be helpful if the book described two additional pieces of information related to genetic-algorithms:

1. The default equality semantics between individuals in the population.
2. The default population size across successive generations (static or dynamic).

This would help better clarify what the pseudocode should be. Currently, the existing pseudocode implies set semantics be used for the new_population variable, i.e.:

new_population ← empty set
for i = 1 to SIZE(population) do

which can cause the size of successive generations to decrease due to duplicates being removed. However, it is normal in Genetic Algorithms to keep the size of the population static across generations. The current Python and Java implementations essentially do this by using lists instead of sets, which would imply the pseudocode would be better represented as:

new_population ← []

However, this setup gives rise to giving too much weight to identical children the next time round (i.e. as soon as duplicates are introduced the population will more than likely become dominated by duplicates over successive generations, reducing the actual search space being explored in parallel).

An alternative change to the pseudocode to address this would be:

new_population ← empty set
repeat
  x ← RANDOM-SELECTION(population,FITNESS-FN)
  y ← RANDOM-SELECTION(population,FITNESS-FN)
  child ← REPRODUCE(x,y)
  if (small random probability) then child ← MUTATE(child)
  add child to new_population
until SIZE(new_population) = SIZE(population)

Addition to BREADTH-FIRST-SEARCH algorithm AIMA4e

The current function only returns true or false depending on whether the path to the goal state is found or not.
I propose to add an improvement to return the complete path from the initial state to the goal state if it exists otherwise return None.

Cross Validation

I am posting a link to a previous discussion here to keep all things pseudocode in one place.

Cross-Validation

I am closing the above issue, so any further discussion can happen here.

3rd Edition Algorithm: A-STAR Search

I couldn't see any pseudocode for it. Please verify it if it is not mentioned then, I am willing to commit.

Normalize for HITS algorithm

In the pseudocode for HITS, normalize is defined to divide each page’s score by the sum of the squares of all pages’ scores. The standard definition of normaliztion divides a value by the norm of the vector that contains it. In our case shouldn't we divide by square root of sum of squares as opposed to just the sum of squares.

4th Edition Algorithm: Random Forests

We will implement random forests for 4th edition: see https://en.wikipedia.org/wiki/Random_forest

Alternative pseudocode for priority queue based graph search (related to Uniform-Cost-Search description - aima3e Figure 3.14)

The following is an alternative version of priority queue graph search pseudocode as described in the Uniform-Cost-Search description in AIMA3e, based on code developed by Ruediger Lunde (on the aima-java AIMA3e branch):

AIMA4e

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
 node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
 frontier ← a priority queue ordered by PATH-COST, with node as the only element
 explored ← an empty set
 loop do
   repeat
     if EMPTY?(frontier) then return failure
     node ← POP(frontier) /* chooses the lowest-cost node in frontier /
   until node.STATE not in explored / ensures not already visited by lower cost node */
   if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
   add node.STATE to explored
   for each action in problem.ACTIONS(node.STATE) do
     child ← CHILD-NODE(problem,node,action)
     if child.STATE is not in explored then
       frontier ← INSERT(child, frontier)

The advantages of this version over the current one as described in AIMA3e, is that it is no longer necessary to perform the containment and replacement functionality on the frontier (which can be expensive and tricky to implement), i.e.:

AIMA3e fragment

if child.STATE is not in explored or frontier then
  frontier ← INSERT(child,frontier)
else if child.STATE is in frontier with higher PATH-COST then
  replace that frontier node with child

Instead duplicate states are dropped when popped off the frontier if they exist in the explored set. Due to being a priority queue the lower cost node will be processed first. The main perceived disadvantage is that the frontier will be larger during processing in the case where you encounter duplicate states before you explore them.

Suggested modifications to Breadth-First-Search (aima3e Figure 3.11)

1. Drop 'PATH-COST=0' from the line:
   node <- a node with STATE= problem.INTITIAL-STATE, PATH-COST = 0
   as it is not actually referenced explicitly anywhere else in the algorithm.
2. Rename the algorithm to Breadth-First-Graph-Search (this suggestion applies to several other of the algorithms in Chapter 3 where the pseudo-code depicts a graph based version only of a more general concept).

Suggested modification to Minimax-Decision (aima3e Figure 5.3)

Rename the argument s in the following three lines of pseudocode:
…
return arg max _{a ∈ ACTIONS(s)} MIN-VALUE(RESULT(state, a))
…
v ← MAX(v, MIN-VALUE(RESULT(s, a)))
…
v ← MIN(v, MAX-VALUE(RESULT(s, a)))
…

to state:
…
return arg max _{a ∈ ACTIONS(state)} MIN-VALUE(RESULT(state, a))
…
v ← MAX(v, MIN-VALUE(RESULT(state, a)))
…
v ← MIN(v, MAX-VALUE(RESULT(state, a)))
…

due to state being the name of the argument passed to the relevant functions.

adding math symbols in github flavoured markdown

It seems we cannot add math symbols like pi, sigma, alpha in github markdown. Any workaround?

After adding and modifying these markdown files, are we gonna use them in 4th edition of the book? If so, we should figure out a way to put these math symbols.

This says we can't do this in GFM: github/markup#274

Suggested modification to Online-DFS-Agent (aima3e Figure 4.21)

To avoid cycles in the DFS traversal, modifying the following conditional from:

…
if s is not null then
  result[s, a] ← s'
  add s to front of unbacktracked[s']
…

to:

if s is not null and s′ ≠ result[s, a] then
  result[s, a] ← s'
  add s to front of unbacktracked[s']
…

without this additional check it is very easy to end up cycling between states, depending on the order of the actions that are tried from each state. Both the current aima-java and aima-python reference implementations contain this additional check.

Is SMA* available?

Section 5.5.5 of the fourth edition mentions that SMA* is available:

The complete algorithm is described in the online code repository accompanying this book. There is one subtlety worth mentioning. We said that SMA∗ expands the best leaf and deletes the worst leaf. 

But I can’t find it.

Suggested modificatin to AC-3 (aima3e Figure 6.3)

In the paragraph before section 6.2.1, leading up to the AC-3 algorithm's description, it states 'If we treat each variable as a node in a graph (see Figure 6.1(b)) and each binary constraint as an arc...' implies there is a one to one mapping between arcs and binary constraints. However, arcs as described in the original paper (http://www.cs.ubc.ca/~mack/Publications/AI77.pdf) are directional while the constraints/relations are un-directed (requiring two arcs for each binary constraint to be considered in the logic). This distinction is important as without it, if arcs for each direction of a binary constraint are not added, the AC-3 algorithm will fail to make the whole CSP arc-consistent.

Figure numbers are slightly off from the third edition

For example, Table driven agent is Figure 2.7 in third edition I own, but it is Figure 2.3 in the PDF. We need to change the PDF file.

@norvig, any idea how to make a new PDF file of modify the current one?

Add figures showing dry-run of search algorithms

Version Space Learning Problem

I have a question regarding the Version Space Learning pseudocode. In particular, I am not sure I understand how the version updating subfunction works.

I have implemented the algorithm and run some tests, and it almost never returns a solution. There might be something wrong with my implementation, but after a quick amendment to the algorithm it works fine. I will give an example to help understand my doubts.

Say we have a version space V with two hypotheses:

H1 = A(True), B(True)
H2 = A(True), B(False)

Our examples:

E1 = A(True), B(True), Target(True)
E2 = A(True), B(False), Target(True)

First we update V on E1:

• E1 is consistent with H1 (predicted value == Target == True).
• E1 is not consistent with H2. H2 predicts a value of False for E1, while it is True. We have a False Negative. Since H2 is not consistent with E1, as per the pseudocode, we remove it. So V now only contains H1.

We move on to E2:

• E2 is not consistent with H1, so we remove H1 from V. Now V is empty.

We are left with an empty V, so we cannot continue. But the initial V is in fact a perfectly good solution. Both E1 and E2 would have been consistent with at least one hypothesis in the initial V which is the desired outcome, but as is the algorithm fails to find a solution.

---

I may have misunderstood the algorithm, but nevertheless after some thinking I found a solution to this and implemented it with great results.

When an example is True, we don't remove hypotheses from V. We just check if there is at least one hypothesis that is consistent with the example and move on. Since the hypotheses are strung together by disjunctions, it doesn't make a difference to True examples if we remove hypotheses that are not consistent. True examples need just one consistent hypothesis. For False examples, work as the pseudocode suggests, since they need to be assigned False values from all hypotheses.

That way we will certainly be left with a set of hypotheses that are consistent with all the examples (if such a set exists).

---

Please let me know if I have not understood the algorithm correctly, or if my thinking is correct.

Inconsistency in Online DFS AGENT(aima3e Fig.4.21) pseudocode and python implementation

The pseudocode for Online DFS Agent contains line else a ← an action b such that result[s', b] = POP(unbacktracked[s']). I see that it is not consistent with python implementation here.

else:
                    # else a <- an action b such that result[s', b] = POP(unbacktracked[s'])
                    unbacktracked_pop = self.unbacktracked.pop(s1)
                    for (s, b) in self.result.keys():
                        if self.result[(s, b)] == unbacktracked_pop:
                            self.a = b
                            break

which implies we are getting an action where result[s,b](result of s instead of s') =POP(unbacktracked[s'])

Bug In CYK PseudoCode [READY TO CLOSE]

Steps to Replicate:

1. Implement the CYK loop structure in Java 1.7+
2. run the code

Expected Output:
Successful exit

Actual Output:
NullPointerException

Reason For Bug:
when length = 2 (first iteration of outer loop), start = N-1 (last iteration of middle loop), and len1 = N-1 (last iteration of inner loop),
second index of the reference to P which is start + len1 equals
2*N - 2, that is out of the array bounds for N > 1

Solution:
Fixed in #31

Suggested modification to Bactracking-Search (aima3e Figure 6.5)

Threee main changes to the pseudocode are suggested:

1. SELECT-UNASSIGNED-VARIABLE, should include the assignment value as an argument, otherwise it has no information on what assignments have already been made.
2. INFERENCE, should include the assignment value as an argument, otherwise it has no information on what assignments have already been made, for e.g. when trying to perform forward checking.
3. The removal of inferences from assignment to be broken into two separate statements that are only to be called if they are relevant.

NOTE: There is some conflation of what an assignment is in the pseudocode with respect to how it was described earlier in the text (end opening paragraph of section 6.1), which relates it solely to a set of variable values. In the pseudocode this is expanded to implicitly include the tracking of domain removals during the INFERENCE() call so that they can be reversed at a later point during backtracking if necessary.

Complete updated pseudocode with changes:

function BACKTRACKING-SEARCH(csp) returns a solution, or failure
 return BACKTRACK({}, csp)

function BACKTRACK(assignment, csp) returns a solution, or failure
 if assignment is complete then return assignment
 var ← SELECT-UNASSIGNED-VARIABLE(assignment, csp)
 for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
   if value is consistent with assignment then
     add {var = value} to assignment
     inferences ← INFERENCE(csp, assignment, var, value)
     if inferences ≠ failure then
      add inferences to assignment
      result ← BACKTRACK(assignment, csp)
      if result ≠ failure then
       return result
      remove inferences from assignment
     remove {var = value} from assignment
 return failure

Problem with algorithms.pdf

Is there a problem with the algorithms.pdf file? Is anyone else having a problem with opening it?
I am just asking this to find if there is a problem with the pdf file itself or with my computer. I can't seem to open it using any PDF viewer on either Linux or Windows.

AIMA 4th Edition Algorithm File

Hello. I new here. I see there is AIMA 3th Edition Algorithm File. When I see in aima-java, in there have issue wants to add implementation of 4th edition Algorithm. Are 4th edition released? If yes, how about added 4th edition into this repo?

Are the Figure Numbers for 3.13-3.24 incorrect?

I was writing a GSoC proposal and I was looking at the Uniform Cost Search pseudocode. However the figure numbers for it and onward are one less than they are in my 3rd Edition textbook (3.24 is actually two less) and in the aima-python docstrings. Were figures removed in a different printing or were they transcribed incorrectly?

Either way, I'm going to submit a PR to fix the Figure numbers.

Suggested modifications to Uniform-Cost-Search description (aima3e Figure 3.14)

In summary

The suggestion is to update Breadth-first-search to note the need for efficient containment checking of states and for the Uniform-cost-search algorithm to additionally mention the need for efficient replacement of nodes based on node cost.

Why

The description in aima3e for Uniform-cost-search beneath the pseudo-code states:

" The data structure for frontier needs to support efficient membership testing, so it should combine the capabilities of a priority queue and a hash table."

This also applies, in part, to the earlier described algorithm Breadth-First-Search (aima3e Figure 3.11):

"if child.STATE is not in explored or frontier then"

in that it is a queue of nodes but you need to efficiently check for state containment within the FIFO queue as well.

This contains check is also in Uniform-cost-search but it also has the additional requirement:

"else if child.STATE is in frontier with higher PATH-COST then replace that frontier node with child"

which, in addition to requiring efficient containment checking also requires efficient replacement functionality.

Clearer alpha-beta cut conditions

In aima4e-algorithms.pdf, in the pseudocode for Alpha-Beta-Search, the conditions for stopping the search in Max-Value and Min-Value are:

• if v >= beta then return v, move
• if v <= alpha then return v, move

There is nothing wrong with that, but I think it would be easier to understand using the conditions:

• if alpha >= beta then return v, move
• if beta <= alpha then return v, move

Unless, there is some subtlety that I am not seeing that makes these conditions different.

Possible error in AngelicSearch

The last two lines of the angelicSearch algorithm appear a bit incorrect.

for each sequence in REFINEMENTS(hla, outcome, hierarchy) do
   frontier ← INSERT(APPEND(prefix, sequence, suffix), frontier)

1. There is no state defined as outcome in the entire algorithm.
2. We cannot apply the refinements function to a single state as under the angelic semantics we consider an entire set of reachable states.
3. The refinements function should be modified to accept a set of possible states and it should return all those HLAs which are applicable in at least one of the states in the set.

@norvig Please have a look at this. Please correct me if I am wrong.

Indent Error in Monte Carlo Localization

The "update cycle" is included in the if statement for "initialization phase"
Monte Carlo Localization

4th Edition Algorithm: Singular Value Decomposition

We will implement SVD, see for example http://stats.stackexchange.com/questions/159325/what-fast-algorithms-exist-for-computing-truncated-svd

Use of Typing Hints

Typing Hints are available from Python >= 3.6.
Should we use them in the implementations of the Algorithms?
for example,

def function(a: int, b: int) -> float:
    return float(a + b)

This function is expected to take 2 int types and return float type.

Suggested modification to Alpha-Beta-Search (aima3e Figure 5.7)

Rename the argument s in the following two lines of pseudocode:
…
v ← MAX(v, MIN-VALUE(RESULT(s, a), α, β))
…
v ← MIN(v, MAX-VALUE(RESULT(s, a), α, β))
…

to state:
…
v ← MAX(v, MIN-VALUE(RESULT(state, a), α, β))
…
v ← MIN(v, MAX-VALUE(RESULT(state, a), α, β))
…

due to state being the name of the argument passed to the relevant functions.

Generic-Search

After a suggestion by Rob Holte, I'm considering changes to the generic search pseudocode
at https://github.com/aimacode/aima-pseudocode/blob/master/md/Tree-Search-and-Graph-Search.md

I'm trying to sort through the implementation choices for OPEN and CLOSED (which we currently call "frontier" and "explored").

We need to support three operations:
(1) check if a state has been encountered before in the interior of the search tree.
(2) check if a state is on the frontier, and if so, fetch the cost and path to it.
(3) pop the best path from the frontier.

Implementation Choice 1:

• explored is a set of states that have been expanded
• frontier is a priority queue of paths, and also a hashtable of {state: path} mappings.
• code: if x not in explored and (x not in frontier or cost(x) < cost(frontier[x]): frontier.add(x)

Note: "path" and "node" are synonyms.

Implementation Choice 2:

• reached is a hash table of {state: path}
• frontier is a priority queue of paths
• code: if x not in reached or cost(x) < cost(reached[x]): frontier.add(x)

It looks like Choice 2 is simpler. Is reached the best name? Maybe best_path?

What do you think @ctjoreilly @MrDupin @redblobgames ?

4th Edition Algorithm: Bidirectional Search

I will be introducing new algorithms for the fourth edition here, in aima-pseudocode, and they can then be moved over to aima-java, aima-python, etc. as people pick them up.

We will add an algorithm for bidirectional search that is guaranteed to meet in the middle, from this paper: https://webdocs.cs.ualberta.ca/~holte/Publications/MM-AAAI2016.pdf

I haven't re-written the pseudocode algorithm from that paper in the form that is consistent with the rest of the search algorithms; that should come.