Cc Candylips: Algorithms - Programming

Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / New
Stats: 3,148,466 members, 7,801,179 topics. Date: Thursday, 18 April 2024 at 11:56 AM

Cc Candylips: Algorithms - Programming - Nairaland

Nairaland Forum / Science/Technology / Programming / Cc Candylips: Algorithms (1546 Views)

I Need To Learn Algorithms / Learning Java Algorithms:merge Equal And Unequal Arrays. / Genetic Algorithms And Neural Networks (2) (3) (4)

(1) (Reply) (Go Down)

Cc Candylips: Algorithms by logica(m): 2:28pm On Jan 21, 2010

OK let's talk about algorithms. I have not implemented many. Actually just 2 as far as I can remember.

Minimax with alpha-beta pruning

This is used for the move selection by the computer in a group of games referred to as Games of Perfect Information (such as Chess, Checkers, etc). I implemented this for the game of Ayo.

A*/Simple Depth First
Usually used for path finding problems. I came up with one for the above (not A*), and another for a Blackplanet puzzle recently.

Which have you implemented?

Re: Cc Candylips: Algorithms by candylips(m): 6:06pm On Jan 21, 2010

Nice one logica.

Can you take use through how you did this. Pseudo-code might be very useful. Lets learn from your expereience wink

i optimised an algorithm for calculating the fibonacci series in a recent project.

nothing fancy since the algorithm used brute force recursion but i had to optimise the speed of the result returned from the fibonacci function that encapsulated this spec so i used a combo of divide and conquer to slit the series into smaller chunks and then results were cached at intermidiate steps which where then used by larger fibonacci numbers

Re: Cc Candylips: Algorithms by logica(m): 6:26pm On Jan 21, 2010

Minimax/alpha beta
I got the initial pseudo-code from a magazine (can't remember the name or edition) way back in '96, and then got another version in the book "Encyclopedia of Artificial Intelligence" by Stuart Shapiro. I no longer have the code as a matter of fact and I had it implemented in QBasic, C, and Java. (though it won't take much to reproduce a better version, since I've gotten way better of course).

Right now, I can only quote from Wikipedia: http://en.wikipedia.org/wiki/Alpha-beta_pruning

function alphabeta(node, depth, α, β)
(* β represents previous player best choice - doesn't want it if α would worsen it *)
if depth = 0 "or" node is a terminal node
return the heuristic value of node
foreach child of node
α := max(α, -alphabeta(child, depth-1, -β, -α))
(* use symmetry, -β becomes subsequently pruned α *)
if β≤α
break (* Beta cut-off *)
return α

(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity)

Depth First
Here is the main class:
[


package com.blackplanet.puzzle;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class shortest implements Runnable {
	private String connectionsFileName;
	
	private String startUserName;
	
	private String endUserName;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		shortest finder = new shortest();
		//Making sure all the required parameters are entered proper.
		if(args.length < 3) {
			System.out.println("Come on dude, you did it wrong!\nUsage:\njava com.blackplanet.puzzle.shortest <relations-file-name> <start-user-name> <end-user-name>";
		} if(args.length > 3) {
			System.out.println("Come on dude, you did it wrong!Usage:\njava com.blackplanet.puzzle.shortest <relations-file-name> <start-user-name> <end-user-name>";
		} 
		else {
			finder.setConnectionsFileName(args[0]);
			finder.setStartUserName(args[1]);
			finder.setEndUserName(args[2]);
			Thread finderThread = new Thread(finder);
			
			finderThread.start();

		}		
	}

	public void run() {
		List<BPMember> members = loadMembers(connectionsFileName);
		
//Tree (binary-tree in the case of sample data, technically speaking) representation of BlackPlanet sample members		
//		System.out.println("Member List: " + members);
		
		String shortestPath = exec(startUserName, endUserName, members);
		
		System.out.println(shortestPath);
	}
	
	public List<BPMember> loadMembers(String fileName) {
		List<BPMember> members = new ArrayList<BPMember>();
		
		BufferedReader reader;
		try {
			reader = new BufferedReader(new FileReader(fileName));
			String line = null;
			String memberName = null;
			String connectedMemberName = null;
			while((line = reader.readLine()) != null) {
				StringTokenizer tk = new StringTokenizer(line, " ";
				memberName = tk.nextToken();
				connectedMemberName = tk.nextToken();
				
				BPMember member = new BPMember(memberName);
				if(!members.contains(member)) {
					members.add(member);
				} else {
					member = members.get(members.indexOf(member));
				}
				
				BPMember connectedMember = new BPMember(connectedMemberName);
				if(!members.contains(connectedMember)) {
					members.add(connectedMember);
				} else {
					connectedMember = members.get(members.indexOf(connectedMember));
				}
				
				if(!connectedMember.getConnectingNodes().contains(member)) {
					connectedMember.addConnectingNode(member);
				}
				if(!member.getConnectingNodes().contains(connectedMember)) {
					member.addConnectingNode(connectedMember);
				}
			}			
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
		
		return members;
	}
	
	public String exec(String startUserName, String endUserName, List<BPMember> members) {
		StringBuilder builder = new StringBuilder();
		
		int memberIdx = members.indexOf(new BPMember(startUserName));
		BPMember startUser = null;
		if(memberIdx >= 0) {
			startUser = members.get(memberIdx);			
		}
			
		memberIdx = members.indexOf(new BPMember(endUserName));
		BPMember endUser = null;
		if(memberIdx >= 0) {
			endUser = members.get(memberIdx);			
		}

		if(startUser != null && endUser != null) {
//			System.out.println("Ready or not, here I come, you can't hide, ";
			Stack<String> currentPath = new Stack<String>();
			ArrayList<Stack<String>> pathSolutions = new ArrayList<Stack<String>>();
//			long startTime = System.currentTimeMillis();
			startUser.findConnection(new BPMember(startUserName), new BPMember(startUserName), new BPMember(endUserName), members.size(), members.size(), currentPath, pathSolutions);
//			long timeInterval = System.currentTimeMillis() - startTime;
			
			if(!pathSolutions.isEmpty()) {
//				System.out.println(", I think I found something, better check.";
//				System.out.println(pathSolutions);
				
//				Figuring out the path with the shortest length, 				
				ArrayList<Long> pathLengths = new ArrayList<Long>();
				for(Iterator<Stack<String>> itr = pathSolutions.iterator(); itr.hasNext(); ) {
					pathLengths.add(new Long(itr.next().size()));
				}
				Collections.sort(pathLengths);
				long optimalPathLength = pathLengths.get(0);

//				System.out.println("OPTIMAL_PATH_LENGTH: " + optimalPathLength);
				
				ArrayList<Stack<String>> optimalPaths = new ArrayList<Stack<String>>();
				optimalPaths.addAll(pathSolutions);				
				
				Stack<String> path = null;
				for(Iterator<Stack<String>> itr = pathSolutions.iterator(); itr.hasNext(); ) {
					path = itr.next();
					if(path.size() > optimalPathLength) {
						optimalPaths.remove(path);
//Separating the chaff from the wheat.
//						System.out.println("Removing the garbage " + path + ", ";
//						System.out.println("OPTIMAL_PATH_REDUCED: " + optimalPaths);
					}
				}
				
				ArrayList<String> optimalPathStrings = new ArrayList<String>();
				
//				System.out.println("And here we are folks!: " + optimalPaths);
				
				Stack<String> aPath = null;
				
				for(Iterator<Stack<String>> itr = optimalPaths.iterator(); itr.hasNext(); ) {
					aPath = itr.next();
					StringBuilder bldr = new StringBuilder();
					for(Iterator<String> j = aPath.iterator(); j.hasNext(); ) {
						bldr.append(j.next());
						if(j.hasNext()) {
							bldr.append(" ";
						}						
					}
					optimalPathStrings.add(bldr.toString());
				}
				Collections.sort(optimalPathStrings);
				
				for(Iterator<String> itr = optimalPathStrings.iterator(); itr.hasNext(); ) {
					builder.append(itr.next());
					if(itr.hasNext()) {
						builder.append("\n";
					}
				}
			} else {
//				System.out.println("Awwww man! What a waste of time. I want my " + ((double) timeInterval) / 1000.0  + " secs back";
				builder.append("NONE";
			}
		} else if(startUser == null){
			builder.append("Come on dude, we don't have anybody called '" + startUserName + "' in here!";
		} else if(endUser == null){
			builder.append("Come on dude, we don't have anybody called " + endUserName + "' in here!";
		}
		
		return builder.toString();
	}

	public void setConnectionsFileName(String connectionsFile) {
		this.connectionsFileName = connectionsFile;
	}

	public String getConnectionsFileName() {
		return connectionsFileName;
	}

	public void setStartUserName(String startUserName) {
		this.startUserName = startUserName;
	}

	public String getStartUserName() {
		return startUserName;
	}

	public void setEndUserName(String endUserName) {
		this.endUserName = endUserName;
	}

	public String getEndUserName() {
		return endUserName;
	}
}

Anybody interested in what the code does and the rest can get it on request.

Re: Cc Candylips: Algorithms by candylips(m): 6:33pm On Jan 21, 2010

logica can you repost. your last post was deleted by the spam bot

Re: Cc Candylips: Algorithms by logica(m): 6:50pm On Jan 21, 2010

That's a very stupid bot, but then what do you expect of a bot?

Anyway here goes:

Minimax/Alpha-beta

I initially got the algorithm from a magazine in '96 and I no longer remember the name or edition, neither do I have the actual code (but it should be fairly easy to come up with something even better if I put my mind to it).

I got this from Wikipedia: http://en.wikipedia.org/wiki/Alpha-beta_pruning

function alphabeta(node, depth, α, β)
(* β represents previous player best choice - doesn't want it if α would worsen it *)
if depth = 0 "or" node is a terminal node
return the heuristic value of node
foreach child of node
α := max(α, -alphabeta(child, depth-1, -β, -α))
(* use symmetry, -β becomes subsequently pruned α *)
if β≤α
break (* Beta cut-off *)
return α

(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity)

Re: Cc Candylips: Algorithms by logica(m): 6:53pm On Jan 21, 2010


package com.blackplanet.puzzle;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class ShortestUserPath implements Runnable {
	private String connectionsFileName;
	
	private String startUserName;
	
	private String endUserName;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		shortest finder = new shortest();
		//Making sure all the required parameters are entered proper.
		if(args.length < 3) {
			System.out.println("Come on dude, you did it wrong!\nUsage:\njava com.blackplanet.puzzle.shortest <relations-file-name> <start-user-name> <end-user-name>";
		} if(args.length > 3) {
			System.out.println("Come on dude, you did it wrong!Usage:\njava com.blackplanet.puzzle.shortest <relations-file-name> <start-user-name> <end-user-name>";
		} 
		else {
			finder.setConnectionsFileName(args[0]);
			finder.setStartUserName(args[1]);
			finder.setEndUserName(args[2]);
			Thread finderThread = new Thread(finder);
			
			finderThread.start();

		}		
	}

	public void run() {
		List<BPMember> members = loadMembers(connectionsFileName);
		
//Tree (binary-tree in the case of sample data, technically speaking) representation of BlackPlanet sample members		
//		System.out.println("Member List: " + members);
		
		String shortestPath = exec(startUserName, endUserName, members);
		
		System.out.println(shortestPath);
	}
	
	public List<BPMember> loadMembers(String fileName) {
		List<BPMember> members = new ArrayList<BPMember>();
		
		BufferedReader reader;
		try {
			reader = new BufferedReader(new FileReader(fileName));
			String line = null;
			String memberName = null;
			String connectedMemberName = null;
			while((line = reader.readLine()) != null) {
				StringTokenizer tk = new StringTokenizer(line, " ";
				memberName = tk.nextToken();
				connectedMemberName = tk.nextToken();
				
				BPMember member = new BPMember(memberName);
				if(!members.contains(member)) {
					members.add(member);
				} else {
					member = members.get(members.indexOf(member));
				}
				
				BPMember connectedMember = new BPMember(connectedMemberName);
				if(!members.contains(connectedMember)) {
					members.add(connectedMember);
				} else {
					connectedMember = members.get(members.indexOf(connectedMember));
				}
				
				if(!connectedMember.getConnectingNodes().contains(member)) {
					connectedMember.addConnectingNode(member);
				}
				if(!member.getConnectingNodes().contains(connectedMember)) {
					member.addConnectingNode(connectedMember);
				}
			}			
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
		
		return members;
	}
	
	public String exec(String startUserName, String endUserName, List<BPMember> members) {
		StringBuilder builder = new StringBuilder();
		
		int memberIdx = members.indexOf(new BPMember(startUserName));
		BPMember startUser = null;
		if(memberIdx >= 0) {
			startUser = members.get(memberIdx);			
		}
			
		memberIdx = members.indexOf(new BPMember(endUserName));
		BPMember endUser = null;
		if(memberIdx >= 0) {
			endUser = members.get(memberIdx);			
		}

		if(startUser != null && endUser != null) {
//			System.out.println("Ready or not, here I come, you can't hide, ";
			Stack<String> currentPath = new Stack<String>();
			ArrayList<Stack<String>> pathSolutions = new ArrayList<Stack<String>>();
//			long startTime = System.currentTimeMillis();
			startUser.findConnection(new BPMember(startUserName), new BPMember(startUserName), new BPMember(endUserName), members.size(), members.size(), currentPath, pathSolutions);
//			long timeInterval = System.currentTimeMillis() - startTime;
			
			if(!pathSolutions.isEmpty()) {
//				System.out.println(", I think I found something, better check.";
//				System.out.println(pathSolutions);
				
//				Figuring out the path with the shortest length, 				
				ArrayList<Long> pathLengths = new ArrayList<Long>();
				for(Iterator<Stack<String>> itr = pathSolutions.iterator(); itr.hasNext(); ) {
					pathLengths.add(new Long(itr.next().size()));
				}
				Collections.sort(pathLengths);
				long optimalPathLength = pathLengths.get(0);

//				System.out.println("OPTIMAL_PATH_LENGTH: " + optimalPathLength);
				
				ArrayList<Stack<String>> optimalPaths = new ArrayList<Stack<String>>();
				optimalPaths.addAll(pathSolutions);				
				
				Stack<String> path = null;
				for(Iterator<Stack<String>> itr = pathSolutions.iterator(); itr.hasNext(); ) {
					path = itr.next();
					if(path.size() > optimalPathLength) {
						optimalPaths.remove(path);
//Separating the chaff from the wheat.
//						System.out.println("Removing the garbage " + path + ", ";
//						System.out.println("OPTIMAL_PATH_REDUCED: " + optimalPaths);
					}
				}
				
				ArrayList<String> optimalPathStrings = new ArrayList<String>();
				
//				System.out.println("And here we are folks!: " + optimalPaths);
				
				Stack<String> aPath = null;
				
				for(Iterator<Stack<String>> itr = optimalPaths.iterator(); itr.hasNext(); ) {
					aPath = itr.next();
					StringBuilder bldr = new StringBuilder();
					for(Iterator<String> j = aPath.iterator(); j.hasNext(); ) {
						bldr.append(j.next());
						if(j.hasNext()) {
							bldr.append(" ";
						}						
					}
					optimalPathStrings.add(bldr.toString());
				}
				Collections.sort(optimalPathStrings);
				
				for(Iterator<String> itr = optimalPathStrings.iterator(); itr.hasNext(); ) {
					builder.append(itr.next());
					if(itr.hasNext()) {
						builder.append("\n";
					}
				}
			} else {
//				System.out.println("Awwww man! What a waste of time. I want my " + ((double) timeInterval) / 1000.0  + " secs back";
				builder.append("NONE";
			}
		} else if(startUser == null){
			builder.append("Come on dude, we don't have anybody called '" + startUserName + "' in here!";
		} else if(endUser == null){
			builder.append("Come on dude, we don't have anybody called " + endUserName + "' in here!";
		}
		
		return builder.toString();
	}

	public void setConnectionsFileName(String connectionsFile) {
		this.connectionsFileName = connectionsFile;
	}

	public String getConnectionsFileName() {
		return connectionsFileName;
	}

	public void setStartUserName(String startUserName) {
		this.startUserName = startUserName;
	}

	public String getStartUserName() {
		return startUserName;
	}

	public void setEndUserName(String endUserName) {
		this.endUserName = endUserName;
	}

	public String getEndUserName() {
		return endUserName;
	}
}

Re: Cc Candylips: Algorithms by logica(m): 6:58pm On Jan 21, 2010

Depth First

For the problem being solved, check the Blackplanet site for the puzzles. It shouldn't be difficult to figure which the solves. Here is the main class. I can send the rest if there's any interest.

package com.blackplanet.puzzle;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class ShortestUserPath implements Runnable {
private String connectionsFileName;

private String startUserName;

private String endUserName;

/**
* @param args
*/
public static void main(String[] args) {
shortest finder = new shortest();
//Making sure all the required parameters are entered proper.
if(args.length < 3) {
System.out.println("Come on dude, you did it wrong!\nUsage:\njava com.blackplanet.puzzle.shortest <relations-file-name> <start-user-name> <end-user-name>" wink

;
} if(args.length > 3) {
System.out.println("Come on dude, you did it wrong!Usage:\njava com.blackplanet.puzzle.shortest <relations-file-name> <start-user-name> <end-user-name>" wink

;
}
else {
finder.setConnectionsFileName(args[0]);
finder.setStartUserName(args[1]);
finder.setEndUserName(args[2]);
Thread finderThread = new Thread(finder);

finderThread.start();

}
}

public void run() {
List<BPMember> members = loadMembers(connectionsFileName);

//Tree (binary-tree in the case of sample data, technically speaking) representation of BlackPlanet sample members
// System.out.println("Member List: " + members);

String shortestPath = exec(startUserName, endUserName, members);

System.out.println(shortestPath);
}

public List<BPMember> loadMembers(String fileName) {
List<BPMember> members = new ArrayList<BPMember>();

BufferedReader reader;
try {
reader = new BufferedReader(new FileReader(fileName));
String line = null;
String memberName = null;
String connectedMemberName = null;
while((line = reader.readLine()) != null) {
StringTokenizer tk = new StringTokenizer(line, " " wink

;
memberName = tk.nextToken();
connectedMemberName = tk.nextToken();

BPMember member = new BPMember(memberName);
if(!members.contains(member)) {
members.add(member);
} else {
member = members.get(members.indexOf(member));
}

BPMember connectedMember = new BPMember(connectedMemberName);
if(!members.contains(connectedMember)) {
members.add(connectedMember);
} else {
connectedMember = members.get(members.indexOf(connectedMember));
}

if(!connectedMember.getConnectingNodes().contains(member)) {
connectedMember.addConnectingNode(member);
}
if(!member.getConnectingNodes().contains(connectedMember)) {
member.addConnectingNode(connectedMember);
}
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

return members;
}

public String exec(String startUserName, String endUserName, List<BPMember> members) {
StringBuilder builder = new StringBuilder();

int memberIdx = members.indexOf(new BPMember(startUserName));
BPMember startUser = null;
if(memberIdx >= 0) {
startUser = members.get(memberIdx);
}

memberIdx = members.indexOf(new BPMember(endUserName));
BPMember endUser = null;
if(memberIdx >= 0) {
endUser = members.get(memberIdx);
}

if(startUser != null && endUser != null) {
// System.out.println("Ready or not, here I come, you can't hide, " wink

;
Stack<String> currentPath = new Stack<String>();
ArrayList<Stack<String>> pathSolutions = new ArrayList<Stack<String>>();
// long startTime = System.currentTimeMillis();
startUser.findConnection(new BPMember(startUserName), new BPMember(startUserName), new BPMember(endUserName), members.size(), members.size(), currentPath, pathSolutions);
// long timeInterval = System.currentTimeMillis() - startTime;

if(!pathSolutions.isEmpty()) {
// System.out.println(", I think I found something, better check." wink

;
// System.out.println(pathSolutions);

// Figuring out the path with the shortest length,
ArrayList<Long> pathLengths = new ArrayList<Long>();
for(Iterator<Stack<String>> itr = pathSolutions.iterator(); itr.hasNext(); ) {
pathLengths.add(new Long(itr.next().size()));
}
Collections.sort(pathLengths);
long optimalPathLength = pathLengths.get(0);

// System.out.println("OPTIMAL_PATH_LENGTH: " + optimalPathLength);

ArrayList<Stack<String>> optimalPaths = new ArrayList<Stack<String>>();
optimalPaths.addAll(pathSolutions);

Stack<String> path = null;
for(Iterator<Stack<String>> itr = pathSolutions.iterator(); itr.hasNext(); ) {
path = itr.next();
if(path.size() > optimalPathLength) {
optimalPaths.remove(path);
//Separating the chaff from the wheat.
// System.out.println("Removing the garbage " + path + ", " wink

;
// System.out.println("OPTIMAL_PATH_REDUCED: " + optimalPaths);
}
}

ArrayList<String> optimalPathStrings = new ArrayList<String>();

// System.out.println("And here we are folks!: " + optimalPaths);

Stack<String> aPath = null;

for(Iterator<Stack<String>> itr = optimalPaths.iterator(); itr.hasNext(); ) {
aPath = itr.next();
StringBuilder bldr = new StringBuilder();
for(Iterator<String> j = aPath.iterator(); j.hasNext(); ) {
bldr.append(j.next());
if(j.hasNext()) {
bldr.append(" " wink

;
}
}
optimalPathStrings.add(bldr.toString());
}
Collections.sort(optimalPathStrings);

for(Iterator<String> itr = optimalPathStrings.iterator(); itr.hasNext(); ) {
builder.append(itr.next());
if(itr.hasNext()) {
builder.append("\n" wink

;
}
}
} else {
// System.out.println("Awwww man! What a waste of time. I want my " + ((double) timeInterval) / 1000.0 + " secs back" wink

;
builder.append("NONE" wink

;
}
} else if(startUser == null){
builder.append("Come on dude, we don't have anybody called '" + startUserName + "' in here!" wink

;
} else if(endUser == null){
builder.append("Come on dude, we don't have anybody called " + endUserName + "' in here!" wink

;
}

return builder.toString();
}

public void setConnectionsFileName(String connectionsFile) {
this.connectionsFileName = connectionsFile;
}

public String getConnectionsFileName() {
return connectionsFileName;
}

public void setStartUserName(String startUserName) {
this.startUserName = startUserName;
}

public String getStartUserName() {
return startUserName;
}

public void setEndUserName(String endUserName) {
this.endUserName = endUserName;
}

public String getEndUserName() {
return endUserName;
}
}

Re: Cc Candylips: Algorithms by logica(m): 7:03pm On Jan 21, 2010

Minimax/Alpha-beta

I initially got the pseudo-code from a magazine back in '96 but I can't remember the name or the edition. I got another variation from the "Encyclopedia of Artificial Intelligence" by Stuart Shapiro. I don't have any of the code anymore (written first in QBasic then C, then Java). I'm sure I can come up with something better at the moment if I feel like.

But I got this from Wikipedia:

http://en.wikipedia.org/wiki/Alpha-beta_pruning

function alphabeta(node, depth, α, β)
(* β represents previous player best choice - doesn't want it if α would worsen it *)
if depth = 0 "or" node is a terminal node
return the heuristic value of node
foreach child of node
α := max(α, -alphabeta(child, depth-1, -β, -α))
(* use symmetry, -β becomes subsequently pruned α *)
if β≤α
break (* Beta cut-off *)
return α

(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity)

Re: Cc Candylips: Algorithms by logica(m): 7:07pm On Jan 21, 2010

Re: Cc Candylips: Algorithms by logica(m): 9:29pm On Jan 21, 2010

Minimax/Alpha-beta Pruning

I first saw the algorithm in a magazine of which I can't recall the name or edition/date since it was back in '96, and then later saw a variant in the book "Encyclopedia of Artificial Intelligence". I first implemented in QBasic, then C, then Java. Unfortunately I no longer have the code, but I can definitely come up with something even better than I had back then (thanks to experience of course).

Here is the algorithm as found on Wikipedia:

http://en.wikipedia.org/wiki/Alpha-beta_pruning
functn alphabeta(node, depth, α, β) (* β represents previous player best choice - doesn't want it if α would worsen it *) if depth = 0 "or" node is a terminal node return the heuristic value of node foreach child of node α := max(α, -alphabeta(child, depth-1, -β, -α)) (* use symmetry, -β becomes subsequently pruned α *) if β≤α break (* Beta cut-off *) return α (* Initial call *) alphabeta(origin, depth, -infinity, +infinity)

Re: Cc Candylips: Algorithms by logica(m): 9:31pm On Jan 21, 2010

Minimax/Alpha-beta Pruning

I first saw the algorithm in a magazine of which I can't recall the name or edition/date since it was back in '96, and then later saw a variant in the book "Encyclopedia of Artificial Intelligence". I first implemented in QBasic, then C, then Java. Unfortunately I no longer have the code, but I can definitely come up with something even better than I had back then (thanks to experience of course).

Here is the algorithm as found on Wikipedia:

http://en.wikipedia.org/wiki/Alpha-beta_pruning

The algorithm is on that page. I cannot post it here since the "smart" bot thinks it's likely to be some attempt to embed Javascript or something (it is smart enough to know it's code, but not smart enough to know it's pseudo).

Re: Cc Candylips: Algorithms by Seun(m): 11:24pm On Jan 21, 2010

Excellent topic. I've not fully figured out this algorithm yet, but it's really useful.

Re: Cc Candylips: Algorithms by logica(m): 11:35pm On Jan 21, 2010

Seun:

Excellent topic. I've not fully figured out this algorithm yet, but it's really useful.

Minimax? Have you ever tried to implement it?

Have you implemented any before?

Can you please delete all my posts (except for this of course) after my second post? Thanks.

Re: Cc Candylips: Algorithms by candylips(m): 2:26pm On Jan 22, 2010

Nice one logica. alpha-beta pruning looks like a very solid search algorithm

Re: Cc Candylips: Algorithms by logica(m): 3:07pm On Jan 22, 2010

candylips:

Nice one logica. alpha-beta pruning looks like a very solid search algorithm

Well, the simple fact is, computers will not be able to play humans in games of perfect information such as Chess, Checkers, Go, etc without this algorithm. Of course you also need a good evaluation function (which gives a numeric value to a game position, and the higher this value, the better it favors the player from whose perspective the position is viewed - such as 'White' in chess). For instance chess computers like Deep Blue have this algorithm and evaluation function implemented in hardware, not software.

Minimax algorithm is also utilized in a branch of Operations Research (Economics) called Game Theory on Zero Sum Two-Player games (unsurprisingly, as you can see the connection), which I believe is used to simulate dynamics in market systems.

Re: Cc Candylips: Algorithms by fallguy(m): 2:14am On Jan 23, 2010

i think maths and the sciences have a way of intimidating people with their funny names. like Al-gor-i-thms, Log-a-rithms.
what does algorithms mean-big sounding name? - simple. a way or process of getting something done.
Mutex lock- what that?
logarithms - means 'power' and people,non-mathematicians would exclaim when they finally find out that that big name means just what they've known for so long - "power" - like in ten raise to "power" 2 is 100. so , i think many programmers have implemented advanced algorithms without necessarily knowing the fancy name it comes with!!
yeah. and many programmers have ventured into scientific realms without necessarily grokking all them academic books and talking in deeper tones.
for example-if a programmer has written a chess playing program and a game of ayo then- most certainly he has implemented an algorithm- he may only later find out that its - what's the high sounding name again - minimax or such.
i beleive this is the case.
for example.
i read of von neumann and his contribution to game theory,it was interesting,i read of the minimax theorem . hmm nice but it didnt make sense to me. just interesting verbiage.

then i though writing a game of tic-tac-toe would b fun.well' i had some days on my hand before travelling away so i set to work on it.
well, i didnt know i was doing minimalist AI, nor did i know i was implementing minimax.i just knew i had to imbue the computer with enough intelligence to match any human player-i had to give it some smarts.
same thing happend when my trusty scientific calculator battery died and as u all know the calculator that comes with windows is not algebraic - now i had been learning programming for 2 years ,i knew of while and for loops and had tabled into php and html and web designing and css i was well spread but shallow but i thought it would be good to fix the calculator problem so i dont embarrassed when i have add up numbers ,foolish me i didnt even check the net for scientific calculators , i just set to work picking my way through ,writing little test codes until - wow- i saw the logic that could order the expression and make computation in an algebraic manner and no!- it wasnt a stack based solution . i had a book on algorithms and all i got was stack based i couldnt understand it so i wrote mine.i still don't know what the name is,its not post fix or prefix nonsense-it just works and - its fast.
so - why the examples - just to score the point that many many "pragmatic" programmers out there would not only be writing
algorithms they'll b inventing algorithms to solve problems- some wouldnt even know of it by its scientific name- if u've solved a complex problem they certainly u've used a pile of algorithms .
i'll upload the codes stated if anybody wants to take a peek at it.
and tell me what algorithms i used.
in my opinion- if any programmer can reason from the general --> to the particular-he'll discover a whole lot of algorithms on the way . and all programs - have a lot of "from general to particular logic " in them.

Re: Cc Candylips: Algorithms by logica(m): 6:02am On Jan 23, 2010

Dude, I'll address what I quickly picked from your post:

Tic-Tac-Toe is so trivial, that it doesn't require an evaluation function or even Minimax for that matter: there is a strategy for figuring out the best move at any time. You can actually enumerate the whole game tree within a few minutes by running a program written for that purpose (that can not be said for Chess or even Ayo). And even if you use Minimax, with the maximum number of moves in any game being 9 and a branch factor of probably less than 3, it is not even worth being used as a case study for Minimax/Alpha-beta.

Not many algorithms are obvious, in fact I don't know any that is. They all arise from years of experimentation and work, which result patterns being identified and in rules-of-thumb.

Re: Cc Candylips: Algorithms by IG: 6:15pm On Jan 24, 2010

If you guys can invest a few bucks for books, I'll recommend "Data Structures Algorithms And Applications Using Java" by Sartaj Sahni. It's the book I used and am still using. Though the book uses Java, you can easily transfer the ideas to whatever language you are using.

Re: Cc Candylips: Algorithms by bigboyslim(m): 1:11am On Jan 25, 2010

@IG,

I just searched the book you recommended on Amazon and was quite surprised to see so many negative reviews. I'm just curios to know why you would recommend such a book. 10 (1 star) reviews out of a total of 28 is anything but impressive.

Re: Cc Candylips: Algorithms by candylips(m): 12:00pm On Jan 25, 2010

@fallguy

You are partly right and partly wrong.

You are right because programmers do spend most of their time writing one form of algorithm or another to solve their daily problems

You are wrong because in other for a programmer to solve more complex problems he needs to apprecite and understand how classic algorithms tackle problems.

So infact classic algorithms and AI algo like the MiniMax shown by logica are like a foundation to developing your own more complex variations if required. A good understanding of how they work will give you a very solid incite as to how you can approve a similar problem. You might not implement the algo exactly as it is done , but you will be able to borrow ideas which you can incorporate.

Re: Cc Candylips: Algorithms by IG: 1:25pm On Jan 25, 2010

@bigboyslim, I never checked Amazon before reading the book. I was talking based on my experience with the book, and I tell you that the book is good. But don't take my word for it. If you can get anything better go for it.

(1) (Reply)

How Can I Get Port 8000 Or 8080 For Live Streaming / Let's Teach Kids To Code / Developers, Share Your Github URL!

(Go Up)

Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health
religion celebs tv-movies music-radio literature webmasters programming techmarket

Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 93
Disclaimer: Every Nairaland member is solely responsible for anything that he/she posts or uploads on Nairaland.