Artificial Intelligence – Othello
The Problem
Video Discussion
Coming soon.
MATLAB Code
Coming soon.
Artificial Intelligence – Path Between Two URLs
The Problem
Write a program that will take as input two Web page URLs and find a path of links from one to the other. What is an appropriate search strategy? Is bidirectional search a good idea? Could a search engine be used to implement a predecessor function?
Video Discussion
Java Code – Forgive me for the formatting didn’t transfer well.
Java Code – PFApp.java
package Pathfinder;
import java.io.IOException;
import java.util.ArrayList;
public class PFApp
{
public static void main(String[] args) throws IOException
{
Problem problem = new Problem(“http://www.jsoup.org”, “http://jsoup.org/apidocs/org/jsoup/nodes/DataNode.html#setWholeData(java.lang.String)”);
URLPathfinder urlPathfinder = new URLPathfinder();
ArrayList<String> solution = urlPathfinder.iterativeDeepeningSearch(problem);
System.out.print(solution);
}
}
Java Code – Node.java
package Pathfinder;
import java.util.ArrayList;
public class Node
{
public Node(String state)
{
this.state = state;
stateHistory = new ArrayList<String>();
stateHistory.add(state);
}
public Node(Problem problem, Node node, String link)
{
this(node.getState());
state = link;
stateHistory = new ArrayList<String>(node.stateHistory);
stateHistory.add(state);
}
public String getState() { return state; }
public ArrayList<String> getStateHistory() { return stateHistory; }
private String state;
private ArrayList<String> stateHistory;
}
Java Code – Problem.java
public class Problem
{
public Problem(String initial, String goal)
{
initialState = initial;
goalState = goal;
}
public boolean goalTest(String nodeState)
{
return (goalState.equals(nodeState));
}
public List<String> actions(Node node) throws IOException
{
List<String> actionList = new ArrayList<String>();
// code for adding actions
Document site = Jsoup.connect(node.getState()).get();
Elements links = site.select(“a[href]”);
for (Element link : links)
{
if (!link.attr(“abs:href”).startsWith(“http://”) && !link.attr(“abs:href”).startsWith(“https://”))
continue;
boolean repeat = false;
for (String sites : node.getStateHistory())
{
if (link.attr(“abs:href”) == sites)
repeat = true;
}
if (!repeat)
actionList.add(link.attr(“abs:href”));
}
return actionList;
}
public String getInitialState() { return initialState; }
public String getGoalState() { return goalState; }
private String initialState;
private String goalState;
Java Code – URLPathfinder.java
package Pathfinder;
import java.io.IOException;
import java.util.*;
public class URLPathfinder
{
public URLPathfinder()
{
solution = new ArrayList<String>();
}
public ArrayList<String> iterativeDeepeningSearch(Problem problem) throws IOException
{
solution.add(problem.getInitialState());
for(depth = 0;;++depth)
{
solution = depthLimitedSearch(problem, depth);
if (solution.get(0) != “cutoff”)
return solution;
}
}
public long getDepth() { return depth; }
private ArrayList<String> depthLimitedSearch(Problem problem, long limit) throws IOException
{
return recursiveDLS(new Node(problem.getInitialState()), problem, limit);
}
private ArrayList<String> recursiveDLS(Node node, Problem problem, long limit) throws IOException
{
if (problem.goalTest(node.getState()))
return node.getStateHistory();
else if (limit == 0)
{
ArrayList<String> cutoff = new ArrayList<String>();
cutoff.add(“cutoff”);
return cutoff;
}
else
{
cutoffOccured = false;
for (String link : problem.actions(node))
{
Node child = new Node(problem, node, link);
solution = recursiveDLS(child, problem, limit – 1);
if (solution.get(0) == “cutoff”)
cutoffOccured = true;
else
return solution;
}
if (cutoffOccured)
return solution;
else
return solution;
}
}
private boolean cutoffOccured;
private long depth;
private ArrayList<String> solution;
Computer Organization and Architecture – ATTiny A simple processor
The Problem
We will be exploring a simple ISA arch. We will explore the use of the processor without interrupts, and when with interrupts. We will hook the processor up to a simple mems based temp sensor and display the temp in BDC on the leds.
Video Discussion
Coming soon.
Assembly Code
Coming soon.
Artificial Intelligence – Cannibals and Missionaries
The Problem
The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. This problem is famous in AI because it was the subject of the first paper that approached problem formulation from an analytical viewpoint.
Video Discussion
C# Code – Main.cs
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace Cannibals_and_Missionaries
{
public partial class Main : Form
{
public Form1()
{
InitializeComponent();
}
private void Main_Load(object sender, EventArgs e)
{
Cannibals_and_Missionaries canmis = new Cannibals_and_Missionaries();
Problem problem = new Problem(33000, 00133);
List<string> path = new List<string>();
path = canmis.breadthFirstSearch(problem);
listBox_Solution.DataSource = path;
}
}
}
C# Code – Node.cs
using System;
using System.Collections.Generic;
namespace Cannibals_and_Missionaries
{
class Node
{
public Node(int theState)
{
state = theState;
stateHistory = new List<int>();
stateHistory.Add(state);
actionHistory = new List<Action>();
}
public Node(Problem problem, Node node, Action action)
: this(node.getState())
{
// sets up child based off of action and parent
if (action == Action.L01)
state += 899;
else if (action == Action.L02)
state += 1898;
else if (action == Action.L10)
state += 9890;
else if (action == Action.L20)
state += 19880;
else if (action == Action.L11)
state += 10889;
else if (action == Action.R01)
state -= 899;
else if (action == Action.R02)
state -= 1898;
else if (action == Action.R10)
state -= 9890;
else if (action == Action.R20)
state -= 19880;
else if (action == Action.R11)
state -= 10889;
actionHistory = new List<Action>(node.actionHistory);
actionHistory.Add(action);
stateHistory = new List<int>(node.stateHistory);
stateHistory.Add(state);
}
public int getState() { return state; }
private int state;
private List<int> stateHistory;
private List<Action> actionHistory;
public List<int> getStateHistory() { return stateHistory; }
public List<Action> getActionHistory() { return actionHistory; }
}
}
C# Code – Problem.cs
using System;
using System.Collections.Generic;
namespace Cannibals_and_Missionaries
{
class Problem
{
public Problem(int initial, int goal)
{
initialState = initial;
goalState = goal;
}
public bool goalTest(int nodeState)
{
return (goalState == nodeState);
}
public List<Action> actions(int state)
{
List<Action> actionList = new List<Action>();
// Code to fill actionList goes here
if (isLegalAction(Action.L01, state))
actionList.Add(Action.L01);
if (isLegalAction(Action.L02, state))
actionList.Add(Action.L02);
if (isLegalAction(Action.L10, state))
actionList.Add(Action.L10);
if (isLegalAction(Action.L11, state))
actionList.Add(Action.L11);
if (isLegalAction(Action.L20, state))
actionList.Add(Action.L20);
if (isLegalAction(Action.R01, state))
actionList.Add(Action.R01);
if (isLegalAction(Action.R02, state))
actionList.Add(Action.R02);
if (isLegalAction(Action.R11, state))
actionList.Add(Action.R11);
if (isLegalAction(Action.R10, state))
actionList.Add(Action.R10);
if (isLegalAction(Action.R20, state))
actionList.Add(Action.R20);
return actionList;
}
public int getInitialState() { return initialState; }
private bool isLegalAction(Action move, int state)
{
// code to tell if action is a legal move or not
// this code takes my state information and makes it useful for comparisons
int lc = state / 10000;
int lm = (state - lc * 10000) / 1000;
int side = (state - lc * 10000 - lm * 1000) / 100;
int rc = (state - lc * 10000 - lm * 1000 - side * 100) / 10;
int rm = (state - lc * 10000 - lm * 1000 - side * 100 - rc * 10);
// boat on left side of river
if (side == 0)
{
if (move == Action.R01)
{ ++rm; --lm; }
else if (move == Action.R02)
{ rm += 2; lm -= 2; }
else if (move == Action.R10)
{ ++rc; --lc; }
else if (move == Action.R20)
{ rc += 2; lc -= 2; }
else if (move == Action.R11)
{ ++rm; ++rc; --lm; --lc; }
else
return false;
}
// boat on right side of river
else if (side == 1)
{
if (move == Action.L01)
{ ++lm; --rm; }
else if (move == Action.L02)
{ lm += 2; rm -= 2; }
else if (move == Action.L10)
{ ++lc; --rc; }
else if (move == Action.L20)
{ lc += 2; rc -= 2; }
else if (move == Action.L11)
{ ++lm; ++lc; --rm; --rc; }
else
return false;
}
else
return false;
if (lc < 0 || lm < 0 || rc < 0 || rm < 0 || lc > 3 || lm > 3 || rc > 3 || rm > 3)
return false;
else if (lm > 0 && lm < lc)
return false;
else if (rm > 0 && rm < rc)
return false;
else
return true;
} // end of isLegalAction()
private int initialState;
private int goalState;
}
}
C# Code – Cannibals_and_Missionaries.cs
using System;
using System.Collections.Generic;
namespace Cannibals_and_Missionaries
{
class Cannibals_and_Missionaries
{
public List <string> breadthFirstSearch(Problem problem)
{
Node node = new Node(problem.getInitialState());
if (problem.goalTest(node.getState()))
return solution(node);
// sets up my frontier
Queue<Node> frontier = new Queue<Node>();
frontier.Enqueue(node);
List<int> explored = new List<int>();
while (true)
{
// failure check
if (frontier.Count == 0)
return new List<string>{"Failure, no solution found"};
node = frontier.Dequeue();
explored.Add(node.getState());
foreach (Action action in problem.actions(node.getState()))
{
Node child = new Node(problem, node, action);
bool flag = false;
if (!explored.Contains(child.getState()))
{
foreach (Node n in frontier)
if (n.getState() == child.getState())
flag = true;
if (flag)
continue;
if (problem.goalTest(child.getState()))
return solution(child);
frontier.Enqueue(child);
}
} // foreach
} // while loop
} // method
private List<string> solution(Node node)
{
// not the prettiest, but it gets the job done.
List<string> path = new List<string>();
path.Add(" Left Side Right Side");
path.Add("---------------------------------------------------------------------------------------------------MOVE---------------------------------------------------------------------------------------------------------");
for (int i = node.getStateHistory().Count - 1; i >0; --i)
{
int state = node.getStateHistory()[node.getStateHistory().Count - i - 1];
int lc = state / 10000;
int lm = (state - lc * 10000) / 1000;
int side = (state - lc * 10000 - lm * 1000) / 100;
int rc = (state - lc * 10000 - lm * 1000 - side * 100) / 10;
int rm = (state - lc * 10000 - lm * 1000 - side * 100 - rc * 10);
path.Add(lc.ToString() + " Cannibals and " + lm.ToString() + " Missionaries " +
rc.ToString() + " Cannibals and " + rm.ToString() + " Missionaries");
if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.L01)
path.Add(" 1 Missionary to the left");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.L02)
path.Add(" 2 Missionaries to the left");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.L10)
path.Add(" 1 Cannibal to the left");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.L20)
path.Add(" 2 Cannibals to the left");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.L11)
path.Add(" 1 Missionary and 1 Cannibal to the left");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.R01)
path.Add(" 1 Missionary to the right");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.R02)
path.Add(" 2 Missionaries to the right");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.R10)
path.Add(" 1 Cannibal to the right");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.R20)
path.Add(" 2 Cannibals to the right");
else if (node.getActionHistory()[node.getStateHistory().Count - i - 1] == Action.R11)
path.Add(" 1 Missionary and 1 Cannibal to the right");
} // for loop
int s = node.getStateHistory()[node.getStateHistory().Count - 1];
int slc = s / 10000;
int slm = (s - slc * 10000) / 1000;
int sside = (s - slc * 10000 - slm * 1000) / 100;
int src = (s - slc * 10000 - slm * 1000 - sside * 100) / 10;
int srm = (s - slc * 10000 - slm * 1000 - sside * 100 - src * 10);
path.Add(slc.ToString() + " Cannibals and " + slm.ToString() + " Missionaries " +
src.ToString() + " Cannibals and " + srm.ToString() + " Missionaries");
return path;
} // method
} // class
enum Action
{
R10, R20, R11, R01, R02,
L10, L20, L11, L01, L02
}
}
Computer Organization and Architecture – Edsac Computer
The Problem
1) Download the simulator and documentation from http://www.dcs.warwick.ac.uk/~edsac/
2) Modify one of the demonstration programs (factorial for example) to add four numbers together and display the result.
Video Discussion
Edsac Code
[ADD FOUR] T123SE84SPSPSP10000SP1000SP100SP10SP1S QS#SA40S!S&S@SO43SO33SPSA46S T65ST129SA35ST34SE61ST48SA47ST65SA33SA40S T33SA48SS34SE55SA34SPST48ST33SA52SA4S U52SS42SG51SA117ST52S P1S[1st] P2S[2nd] P3S[3rd] P4S[4th] PSPSPSPSP1SO41ST129SO44SO45SA76S A77SA78SA79S A4SU76S T48SA83ST75SE49SZSO43SH76SV76SL64SL32S U77SS78ST79SA77SU78ST48SA80ST75SE49SO43SO43S A79ST48SA81ST75SE49SA35SA76SS82SG85SO41SZS
Artificial Intelligence – Simple Reflex (deterministic and stochastic)
The Problem
Use the provided matlab code (must be the matlab code provided) and
- Add a ‘Bump’ sensor eg. sensor(‘Bump’) which returns a precept ‘Bump’ or ‘None’ if the last action was a movement which would place the vacuum into a square that is a wall.
- Add the actions ‘GoEast’,’GoWest’,’GoNorth’,’GoSouth’ to the actions. Remember to check if the motion would result in you moving into a wall, and set the ‘Bump’ sensor’s environment state to true. You can’t move into a wall, so the robot should remain at the location it had prior to the move.
- Write a simple deterministic reflex agent. Answer the following: “Can a simple reflex agent ever clean all of the room?” “Will it ever stop?”, “For the room provided, what percentage of the room will be visited?”
- Write a simple stochastic reflex agent. Again, answer the following: “Can a simple reflex agent ever clean all of the room?” “Will it ever stop?”, “For the room provided, what percentage of the room will be visited?”
- [Extra Credit, 10 points] Can a faulty bump sensor (one which mistakenly returns ‘Bump’ instead of ‘None’ sometimes) improve the performance of the simple deterministic reflex agent? The simple stochastic reflex agent? Put this option into the code, document and test your hypothesis.
Post your project: Code, answers to the questions and testing (youtube videos would be nice) on your website for the course. Send me the link.
Video Discussion
MATLAB Code (Environment.m)
function Environment(agentType)
Exists = true;
% The agent.m must be defined and have a function called agent
% The agent calls Sense(Type) to sense the environment
% The agent calls Act(Type) to affect the environment
global M;
global N;
global Clean;
global Dirt;
global Room;
global Wall;
global VacR;
global VacC;
global BumpState;
M = 6;
N = 6;
Clean = 0;
Dirt = 2;
Wall = 1;
Room = (rand(M,N)>0.7)*Dirt;
Room(1,:) = Wall;
Room(6,:) = Wall;
Room(:,1) = Wall;
Room(:,6) = Wall;
% Initial Position of Vac
VacR = 2;
VacC = 2;
BumpState = false;
hfSense = @Sense;
hfAct = @Act;
Last = ' ';
hold on;
imagesc(Room);
axis square;
plot(VacC,VacR,'*y');
hold off;
pause
while(Exists)
if (strcmpi(agentType, 'deterministic'))
AgentDeterministic(hfSense,hfAct);
elseif (strcmpi(agentType, 'stochastic'))
AgentStochastic(hfSense,hfAct,floor(random('Uniform', 1,5 )));
elseif (strcmpi(agentType, 'model'))
Last = AgentModel(hfSense,hfAct, floor(random('Uniform', 1,5 )),Last);
else
fprintf(1,'Must choose "deterministic" or "stochastic"\n');
end
fprintf(1,'\n');
% Display Env
hold on;
imagesc(Room);
axis square;
plot(VacC,VacR,'*y');
hold off;
pause
end
function [percept]= Sense(sensor)
global VacR;
global VacC;
global Room;
global Clean;
global Dirt;
global Wall;
global BumpState;
fprintf(1,'Sense is called %s\n',sensor);
% We will can check the agent state in the environment and
% return the correct sensor and tell the agent what it sensed
if (strcmpi(sensor,'Dirt'))
if (Room(VacR,VacC)== Dirt)
fprintf(1,' D');
percept = 'Dirty' ;
else
fprintf(1,' C');
percept = 'Clean';
end
fprintf(1,' %d : %f %f \n',Room(VacR,VacC),VacR,VacC);
end
if (strcmpi(sensor,'Bump'))
if (BumpState)
fprintf(1,' BUMP\n');
percept = 'Bump';
else
fprintf(1,' CLEAR\n');
percept = 'None';
end
end
return;
function Act(action)
global VacR;
global VacC;
global Room;
global Clean;
global Dirt;
global Wall;
global BumpState;
fprintf(1,'---Act is called %s\n',action);
% We will check the agent state in the environment and
% update the environment.
if(strcmpi(action,'Clean'))
Room(VacR,VacC)= Clean;
end
if(strcmpi(action,'East'))
if(Room(VacR,VacC+1) == Wall)
BumpState = true;
else
BumpState = false;
VacC = VacC+1;
end
end
if(strcmpi(action,'West'))
if(Room(VacR,VacC-1) == Wall)
BumpState = true;
else
BumpState = false;
VacC = VacC-1;
end
end
if(strcmpi(action,'North'))
if(Room(VacR+1,VacC) == Wall)
BumpState = true;
else
BumpState = false;
VacR = VacR+1;
end
end
if(strcmpi(action,'South'))
if(Room(VacR-1,VacC) == Wall)
BumpState = true;
else
BumpState = false;
VacR = VacR-1;
end
end
return;
MATLAB Code (AgentDeterministic.m)
function AgentDeterministic(sense, act)
%AGENT Summary of this function goes here
% Detailed explanation goes here
if (strcmpi(sense('Dirt'), 'Dirty'))
act('clean')
else if (strcmpi(sense('Bump'), 'Bump'))
act('North')
else
act('East')
end
end
end
MATLAB Code (AgentStochastic.m)
function AgentStochastic(sense, act, rv)
%AGENT Summary of this function goes here
% Detailed explanation goes here
if (strcmpi(sense('Dirt'), 'Dirty'))
act('clean')
elseif (rv == 1)
act('North')
elseif (rv == 2)
act('East')
elseif (rv == 3)
act('South')
elseif (rv == 4)
act('West')
else
end
end
Computer Algorithms – Homework Number 1
The Problem
1. Implement the Consecutive Integer Checking algorithm for finding the greatest common
divisor of two positive integers m and n as a procedure in a programming language of your
choice. Add a counter in your procedure to count the number of integers that are checked
before the answer is found for each pair of input. Write a main program to generate 100
pairs of integers randomly between 1000 and 10,000 and call the consecutive integer
checking procedure for each pair. Keep a record of which pair requires the most number of
iterations, which pair requires the least number of iterations, and the average number of
iterations overall. Output from your program should look like:
The most number of iterations is (?) for GCD(?, ?) = ?.
The least number of iterations is (?) for GCD(?, ?) = ?.
The average number of iterations for all 100 pairs is (?).
Each question mark (?) above should show a specific number.
2. Implement the Euclid’s algorithm as a procedure in the same way and gather the output
result for the same 100 pairs of randomly generated integers. Compare the output results
from the two solutions and describe what you think about the difference in the number of
iteractions performed.
Video Discussion
Numerical Methods Homework – Problem 15.15
The Problem
Develop an M-file to locate a minimum with the golden section search. Rather than using the standard stopping criteria, determine the number of iterations needed to attain a desired tolerance.
Video Discussion
MATLAB Code
function [x,fx,iter] = goldmin(xlow,xhigh,es,f)
R = (5^(.5) - 1)/2;
xl = xlow;
xu = xhigh;
d = R *(xu - xl);
x1 = xl + d;
x2 = xu - d;
f1 = f(x1);
f2 = f(x2);
if (f1 < f2)
xopt = x1;
fx = f1;
else
xopt = x2;
fx = f2;
end
ea = 100;
iter = 1;
while (ea > es)
d = R*d;
if (f1 < f2)
xl = x2;
x2 = x1;
x1 = xl + d;
f2 = f1;
f1 = f(x1);
else
xu = x1;
x1 = x2;
x2 = xu-d;
f1 = f2;
f2 = f(x2);
end
if (f1 < f2)
xopt = x1;
fx =f1;
else
xopt = x2;
fx = f2;
end
if (xopt < 0 || xopt > 0)
ea = (1.-R) * abs((xu-xl)/xopt)*100;
end
iter = iter + 1;
end
x = xopt;
end
Numerical Methods Homework – Problem 15.14
The Problem
Develop an M-file that is expressly designed to locate a maximum with the golden-section search algorithm. The function should iterate until the relative error falls below a stopping criterion or exceeds a maximum number of iterations, and return both the optimal x and f(x).
Test it on
Video Discussion
MATLAB Code
function [x,fx] = goldmax(xlow,xhigh,maxit,es,f)
R = (5^(.5) - 1)/2;
xl = xlow;
xu = xhigh;
iter = 1;
d = R *(xu - xl);
x1 = xl + d;
x2 = xu - d;
f1 = f(x1);
f2 = f(x2);
if (f1 > f2)
xopt = x1;
fx = f1;
else
xopt = x2;
fx = f2;
end
ea = 100;
while (ea > es && iter < maxit)
d = R*d;
if (f1 > f2)
xl = x2;
x2 = x1;
x1 = xl + d;
f2 = f1;
f1 = f(x1);
else
xu = x1;
x1 = x2;
x2 = xu-d;
f1 = f2;
f2 = f(x2);
end
iter = iter + 1;
if (f1 > f2)
xopt = x1;
fx =f1;
else
xopt = x2;
fx = f2;
end
if (xopt < 0 || xopt > 0)
ea = (1.-R) * abs((xu-xl)/xopt)*100;
end
end
x = xopt;
end
Numerical Methods Homework – Problem 13.18
The Problem
The deflection of a uniform beam subject to a linearly increasing distributed load can be computed as:
Given that L = 600cm, E= 50,000 kN/cm2, I = 30,000cm4, and w0 = 2.5 kN/cm, determine the point of maximum deflection graphically and using the golden-section search until the approximate error falls below 1% with initial guesses of xl = 0 and xu = L
Video Discussion
MATLAB Code
L = 600; E = 50000; I = 30000; w0 = 2.5; y = @(x)(w0/(120*E*I*L)*(-x.^5+2*L^2*x.^3-L^4*x)); x = (0:.001:1000); plot (x,y(x)); [x,ea] = goldmax(0,L,1000,.0001,y)
chrislaurich 