Introduction to Artificial Intelligence -- Search Methods

Maze search -- Mouse intelligence

A mouse searches for an exit in depth-first manner.

- - - - - - - - - - - - - - - - - - -
| * |                           |   |  The mouse tries (up, right, down, 
|   |   _ _ _ _ _   |   _ _ _ _ |   |  left) in this order. It never 
|   |   |           |   |           |  goes to an already visited point.
|   |   |   _ _ _   |   |   _ _ _ _ |
|       |   |       |       |       |
| _ _ _ |   |   _ _ | _ _ _ |   _ _ |
|           |               |       |
|   _ _ _ _ | _ _ _ _ _ _ _ |   |   |
|   |       |               |   |   |
|   |   _ _ |   _ _ _ _ _   |   |   |
|   |   |       |           |   |   |
|       |   |   | _ _ _ _ _ _   |   |
| _ _   |   |   |               |   |
|       |   |   |     _ _ _ _ _ |   |
|   _   |   |   |   |           |   |
|   |   |   |   |   |   _   _ _ |   |
|   |       |       |   |           |
- - - - - - - - - - - - - - - - - - - exit


- - - - - - - - - - - - - - - - - - -
| * | * * * * * * * * * * * * * |   |   When it comes to a deadend,
| * | * _ _ _ _ _   |   _ _ _ _ |   |   
| * | * |           |   |           |
| * | * |   _ _ _   |   |   _ _ _ _ |
| * * * |   |       |       |       |
| _ _ _ |   |   _ _ | _ _ _ |   _ _ |
|           |               |       |
|   _ _ _ _ | _ _ _ _ _ _ _ |   |   |
|   |       |               |   |   |
|   |   _ _ |   _ _ _ _ _   |   |   |
|   |   |       |           |   |   |
|       |   |   | _ _ _ _ _ _   |   |
| _ _   |   |   |               |   |
|       |   |   |     _ _ _ _ _ |   |
|   _   |   |   |   |           |   |
|   |   |   |   |   |   _   _ _ |   |
|   |       |       |   |           |
- - - - - - - - - - - - - - - - - - - exit




- - - - - - - - - - - - - - - - - - -
| * | * * * * * * * * *         |   |  it goes back to the nearest
| * | * _ _ _ _ _   | * _ _ _ _ |   |  branching point, and goes down
| * | * |           | * |           |
| * | * |   _ _ _   | * |   _ _ _ _ |
| * * * |   |       |       |       |
| _ _ _ |   |   _ _ | _ _ _ |   _ _ |
|           |               |       |
|   _ _ _ _ | _ _ _ _ _ _ _ |   |   |
|   |       |               |   |   |
|   |   _ _ |   _ _ _ _ _   |   |   |
|   |   |       |           |   |   |
|       |   |   | _ _ _ _ _ _   |   |
| _ _   |   |   |               |   |
|       |   |   |     _ _ _ _ _ |   |
|   _   |   |   |   |           |   |
|   |   |   |   |   |   _   _ _ |   |
|   |       |       |   |           |
- - - - - - - - - - - - - - - - - - - exit



- - - - - - - - - - - - - - - - - - -
| * | * * * * * * *             |   |   Finally it finds the exit.
| * | * _ _ _ _ _ * |   _ _ _ _ |   |
| * | * | * * * * * |   |           |
| * | * | * _ _ _   |   |   _ _ _ _ |
| * * * | * |       |       |       |
| _ _ _ | * |   _ _ | _ _ _ |   _ _ |
| * * * * * |               | * * * |
| * _ _ _ _ | _ _ _ _ _ _ _ | * | * |
| * |       |               | * | * |
| * |   _ _ |   _ _ _ _ _   | * | * |
| * |   | * * * |           | * | * |
| * * * | * | * | _ _ _ _ _ | * | * |
| _ _ * | * | * | * * * * * * * | * |
|     * | * | * | * _ _ _ _ _ _ | * |
|   _ * | * | * | * |           | * |
|   | * | * | * | * |   _   _ _ | * |
|   | * * * | * * * |   |         * |
- - - - - - - - - - - - - - - - - - - exit


There is no concept of back tracking in the mouse intelligence.
The mouse program is listed below.

## This Python program tarces a maze search with symbol "*".
## The first part is the maze data in one-dim list c.
## The one-dim array is converted to two-dim list a.
## The depth-first seacrh is carried out by recursive calls
## to four directions (up, right, down, left).

c=[ 
"-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-",
"|"," ","|"," "," "," "," "," "," "," "," "," "," "," "," "," ","|"," ","|",
"|"," ","|"," ","_","_","_","_","_"," ","|"," ","_","_","_","_","|"," ","|",
"|"," ","|"," ","|"," "," "," "," "," ","|"," ","|"," "," "," "," "," ","|",
"|"," ","|"," ","|"," ","_","_","_"," ","|"," ","|"," ","_","_","_","_","|",
"|"," "," "," ","|"," ","|"," "," "," ","|"," "," "," ","|"," "," "," ","|",
"|","_","_","_","|"," ","|"," ","_","_","|","_","_","_","|"," ","_","_","|",
"|"," "," "," "," "," ","|"," "," "," "," "," "," "," ","|"," "," "," ","|",
"|"," ","_","_","_","_","|","_","_","_","_","_","_","_","|"," ","|"," ","|",
"|"," ","|"," "," "," ","|"," "," "," "," "," "," "," ","|"," ","|"," ","|",
"|"," ","|"," ","_","_","|"," ","_","_","_","_","_"," ","|"," ","|"," ","|",
"|"," ","|"," ","|"," "," "," ","|"," "," "," "," "," ","|"," ","|"," ","|",
"|"," "," "," ","|"," ","|"," ","|","_","_","_","_","_","|"," ","|"," ","|",
"|","_","_"," ","|"," ","|"," ","|"," "," "," "," "," "," "," ","|"," ","|",
"|"," "," "," ","|"," ","|"," ","|"," ","_","_","_","_","_","_","|"," ","|",
"|"," ","_"," ","|"," ","|"," ","|"," ","|"," "," "," "," "," ","|"," ","|",
"|"," ","|"," ","|"," ","|"," ","|"," ","|"," ","_"," ","_","_","|"," ","|",
"|"," ","|"," "," "," ","|"," "," "," ","|"," ","|"," "," "," "," "," "," ",
"-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-","-"];
n=19; ### size of maze is 19 by 19
a=[]
for i in range(0,n): 
  a1=[]
  for j in range(0,n):
    a1=a1+[c[i*n+j]]
  a=a+[a1]

for i in range(0,n): 
  for j in range(0,n):
    print a[i][j],
  print "\n",

def dfs(x, y):
  a[x][y]="*";
  print "\n" ;

  for i in range(0,n): 
    for j in range(0,n):
      print a[i][j] ,
    if(i<n-1): print  "\n", 
  print  "exit"  
  w=raw_input(" ");
  if((x==17) and (y==17)): ### (17, 17) is exit
    print "Congratulations!"
    exit();  

  if(b[x-1][y]==0):b[x-1][y]=1; dfs(x-1,y)  # going up
  if(b[x][y+1]==0):b[x][y+1]=1; dfs(x,y+1)  # going right
  if(b[x+1][y]==0):b[x+1][y]=1; dfs(x+1,y)  # going down
  if(b[x][y-1]==0):b[x][y-1]=1; dfs(x,y-1)  # going left
  a[x][y]=" ";

## create array b as a blocking array
b=[]
for i in range(0,n):
  b1=[]
  for j in range(0,n):
    b1=b1+[0]
  b=b+[b1]

## non-blank characters are regarded as blocking
for i in range(0,n) :
  for j in range(0,n):
    if (a[i][j]!=" "): b[i][j]=1 ## blocking 
    else: b[i][j]=0;             ## non-blocking

b[1][1]=1;
dfs(1,1);  ## search starts
print "\n"  


Four directions are tried by the four recursive calls in "dfs".
Array b is used to show no-go zones. Barriers are also no-go
zones. Since array b is always set to 1, not back to 0,
already visited places can not be visited again.

Hamilton path -- artificial intelligence

Suppose there are 24 rooms in a floor of a building.
They are squares in the following floor plan. One square
is occupied by a staircase.

----------------
|* |  |  |  |  |   starting point is upper left corner
----------------
||||  |  |  |  |   Is there any path that visits each room only once?
----------------   You can go into four neighbours if any. Also
|  |  |  |  |  |   you can finish in any room.
----------------
|  |  |  |  |  |
----------------
|  |  |  |  |  |
----------------

After you search for a path, you come to

- - - - - - -
| * * * * * |
| -       * |
|         * |
|           |
|           |
- - - - - - -
- - - - - - -
| * * * * * |
| -   * * * |
|     * * * |
|     * * * |
|       * * |
- - - - - - -

- - - - - - -   this situation
| * * * * * |
| - * * * * |
|   * * * * |
|   * * * * |
|   * * * * |
- - - - - - -

Then the mouse will finish with


- - - - - - -
| * * * * * |
| -   * * * |
| * * * * * |
| * * * * * |
|   * * * * |
- - - - - - -


- - - - - - -
| * * * * * |
| -   * * * |
| * * * * * |
| * * * * * |
| * * * * * |
- - - - - - -

The AI program with backtarcking will continue to search as shown
below.

- - - - - - -
| * * * * * |
| -   * * * |
|     * * * |
| * * * * * |
|   * * * * |
- - - - - - -


- - - - - - -
| * * * * * |
| -   * * * |
| *   * * * |
| * * * * * |
|   * * * * |
- - - - - - -

etc, etc, and finally report "there is no solution.


int success(){
  int t,i,j;
  t=1;
  for(i=1;i<=n; i++)
    for(j=1;j<=n; j++) t=t&&b[i][j];
  return t;
}
dfs(int x, int y)
{
  a[x][y]="*";
  if(s==1)out();
  c++;
  if(success()) {printf("success\n");exit(0); }
  if(b[x-1][y]==0){b[x-1][y]=1; dfs(x-1,y); b[x-1][y]=0;}
  if(b[x][y+1]==0){b[x][y+1]=1; dfs(x,y+1); b[x][y+1]=0;}
  if(b[x+1][y]==0){b[x+1][y]=1; dfs(x+1,y); b[x+1][y]=0;}
  if(b[x][y-1]==0){b[x][y-1]=1; dfs(x,y-1); b[x][y-1]=0;}
  a[x][y]=" ";
}

The main difference here from the previous mouse intelligence is
after "dfs", array b is reset to 0, and the "succsess" function
checks if all b valuses are 1, i.e., if all rooms are visited.
That is, the AI program has a global information of visit situation
and backtracking.

Human Intelligence

This Hamiltonian path problem is impossible.

Proof.

----------------
|X |  |X |  |X |  Draw balck and white like a chcker board
----------------  X is for black
||||X |  |X |  |
----------------  When you start from upper-left corner
|X |  |X |  |X |  you alternate balck and white
---------------
|  |X |  |X |  |  In order to have a Hamiltonian path,
----------------  the number of blacks and whites must be
|X |  |X |  |X|   different at most by 1.
---------------   In this example, blacks=13, whites=11

This proof method is know as the parity method, as the thory is
based on the parity of blacks and whites.
Can a computer invent this theory?