Johdatus tekoälyyn, syksy 2011, Teemu Roos Harjoitus 2 - PDF

Description
Johdatus tekoälyyn, syksy 2011, Teemu Roos Harjoitus 2 Huom: Voit saada tästä harjoituskerrasta max. 8 pistettä. Tehtävä 1. Minimax ja alpha-beta. (1 piste) a ja b) Ks. kuva 1 alla. c) Katso video kurssin

Please download to get full document.

View again

of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Scrapbooking

Publish on:

Views: 20 | Pages: 9

Extension: PDF | Download: 0

Share
Transcript
Johdatus tekoälyyn, syksy 2011, Teemu Roos Harjoitus 2 Huom: Voit saada tästä harjoituskerrasta max. 8 pistettä. Tehtävä 1. Minimax ja alpha-beta. (1 piste) a ja b) Ks. kuva 1 alla. c) Katso video kurssin sivulla. Muista, että α-arvon voi tulkita MIN-solmun yläpuolelle olevan MAX-solmun saamaksi toistaiseksi parhaaksi tarjoukseksi. Jos MIN-solmussa havaitaan, että solmun arvoksi on tulossa α-arvoa pienempi luku, voidaan lopettaa, koska yläpuolella olevasta MAXsolmussa ei koskaan pelata siirtoa, joka päätyisi nykyiseen MIN-solmuun. Myös β arvolla on vastaava tulkinta. Figure 1: Tehtävän 1 pelipuu. solmun alle (v = 1/0/1). Minimax-algoritmin tuottamat arvot on merkitty kunkin 1 Tehtävä 2. Syvyysrajoitettu alpha-beta. (1-2 pistettä) #!/usr/bin/python from array import array import random Empty = maxdepth = 10 def checkwin(board): col1 = board.b[0][0] + board.b[1][0] + board.b[2][0] col2 = board.b[0][1] + board.b[1][1] + board.b[2][1] col3 = board.b[0][2] + board.b[1][2] + board.b[2][2] row1 = board.b[0][0] + board.b[0][1] + board.b[0][2] row2 = board.b[1][0] + board.b[1][1] + board.b[1][2] row3 = board.b[2][0] + board.b[2][1] + board.b[2][2] diag1 = board.b[0][0] + board.b[1][1] + board.b[2][2] diag2 = board.b[2][0] + board.b[1][1] + board.b[0][2] if ( XXX in [row1,row2,row3,col1,col2,col3,diag1,diag2]): return X elif ( OOO in [row1,row2,row3,col1,col2,col3,diag1,diag2]): return O else: return None def applymove(board,r,c,turn): # returns a new position with turn (X or O) added at (r,c) newboard = Board(board) newboard.b[r][c] = turn newboard.winner = checkwin(newboard) newboard.turn = X if board.turn == O else O return newboard def copypieces(b): return [array( c,row) for row in b] class Board: def init (self,board=none): self.value = 0 self.winner = None if board: self.b = copypieces(board.b) self.turn = board.turn 2 self.value = board.value self.winner = board.winner def initialstate(self): b=[ OOX, X, OX ] # b=[,, ] self.b = [array( c,row) for row in b] self.turn = X self.winner = None def str (self): return \n .join([row.tostring() for row in self.b])+ \n def validmoves(self): if not self.winner == None: return [] moves = [] for (r,c) in [(r,c) for r in range(3) for c in range(3)]: if self.b[r][c] == : moves.append(applymove(self,r,c,self.turn)) return moves def evaluate(self): if self.turn == X : self.value = self.maxvalue(-float( inf ), float( inf ), 1) else: self.value = self.minvalue(-float( inf ), float( inf ), 1) def maxvalue(self, alpha, beta, depth): if self.winner == X : return 1 elif self.winner == O :return -1 if depth = maxdepth: return self.evaluateheuristic() v = -float( inf ) moves = self.validmoves() if moves == []: return 0 for move in moves: move.value = move.minvalue(alpha,beta,depth+1) v = max(v, move.value) if v = beta: return v alpha = max(alpha, v) return v def minvalue(self, alpha, beta, depth): if self.winner == X : return 1 elif self.winner == O : return -1 3 if depth = maxdepth: return self.evaluateheuristic() moves = self.validmoves() if moves == []: return 0 v = float( inf ) for move in moves: move.value = move.maxvalue(alpha,beta,depth+1) v = min(v, move.value) if v = alpha: return v beta = min(beta, v) return v def evaluateheuristic(self): if self.winner == X : return 1 elif self.winner == O : return -1 board = Board() col1 = self.b[0][0] + self.b[1][0] + self.b[2][0] col2 = self.b[0][1] + self.b[1][1] + self.b[2][1] col3 = self.b[0][2] + self.b[1][2] + self.b[2][2] row1 = self.b[0][0] + self.b[0][1] + self.b[0][2] row2 = self.b[1][0] + self.b[1][1] + self.b[1][2] row3 = self.b[2][0] + self.b[2][1] + self.b[2][2] diag1 = self.b[0][0] + self.b[1][1] + self.b[2][2] diag2 = self.b[2][0] + self.b[1][1] + self.b[0][2] all = [col1,col2,col3,row1,row2,row3,diag1,diag2] # count how many lines there are where X has one or two # pieces and O none, and vice versa, take the difference # and divide by the total number of lines (=8) heuristic = (len([x for x in all if x in [ XX, X X, XX, X, X, X ]]) \ -len([x for x in all if x in [ OO, O O, OO, O, O, O ]]))\ / 8. return heuristic board.initialstate() print board while True: print (board.turn + moves ) bestmove = None bestvalue = float( -Inf ) if board.turn == X else float( Inf ) 4 for move in board.validmoves(): move.evaluate() if (board.turn == X and move.value bestvalue) or \ (board.turn == O and move.value bestvalue): bestmove = move bestvalue = move.value if bestmove == None: print No moves! break board = bestmove print board if not board.winner == None: print (board.winner + wins! ) break if board.winner == None: print A draw! Esimerkkiajo: $./tictactoe.py OOX X OX X moves OOX XX OX O moves OOX XXO OX X moves OOX XXO OXX O moves No moves! A draw! 5 Tehtävä 3. Reittiopas. (3-6 pistettä) Java-esimerkki (kiitokset Kalle Viirille): Node.java. package reittiopas; import java.io.printstream; import java.util.list; import java.util.arraylist; /** Kalle Viiri */ class Node implements Comparable { private int time; //minutes from start private Stop location; //stop we re at private Node parent; //We came from where? private Transportation trans; public static Stop goal; public Node(int time, Stop location, Node parent, Transportation trans) { this.time = time; this.location = location; this.parent = parent; this.trans = trans; public boolean isgoalstate(int number) { if(number == location.number) return true; else return false; public List Node getneighbors(list stop stoplist) { List Node neighbors = new ArrayList Node (); Stop currentlocation = this.getlocation(); for(transportation t : currentlocation.transportations) { //Finding the right stop and the time associated int wait = this.gettime() % 10; int stopindex = 999; //We want to know the stop index for(int i = 0; i t.timetable.size(); i++) { if(t.timetable.get(i)[0] == currentlocation.number) { stopindex = i; wait = t.timetable.get(i)[1] % 10 - wait; 6 break; if(wait 0) wait+= 10; if(stopindex + 1 t.timetable.size()) { //If this isn t the last stop for(stop s : stoplist) { if(s.number == t.timetable.get(stopindex + 1)[0]) { //Find the next stop int tripcost = t.timetable.get(stopindex + 1)[1] - t.timetable.get(stopindex)[1]; neighbors.add(new Node(this.getTime() + wait + tripcost, s, this, t)); return neighbors; public void printstate(printstream ps) { ps.print(location.name + + (trans.name!= null? trans.name : ) + Aika: + time + \n\n ); public int calculatedistance(stop target) { return (int) Math.sqrt(Math.pow(Math.abs((this.getLocation().x - target.x)), 2) + Math.pow(Math.abs((this.getLocation().y - target.y)), 2)); public int estimatecost(stop goal) { return calculatedistance(goal) / 1000; public int totalcost(stop goal) { return time + estimatecost(goal); public Stop getlocation() { return location; public void setlocation(stop location) { this.location = location; public Node getparent() { 7 return parent; public void setparent(node parent) { this.parent = parent; public int gettime() { return time; public void settime(int time) { this.time = public int compareto(object t) { Node n = (Node) t; if(this.estimatecost(goal) + gettime() n.estimatecost(goal) + n.gettime()) return -1; else if(this.estimatecost(goal) + gettime() n.estimatecost(goal) + n.gettime()) return 1; else return 0; AStarReittiopas.java. package reittiopas; import java.util.linkedlist; import java.util.list; import java.util.priorityqueue; import java.util.vector; import reittiopas.stop; /** Kalle Viiri */ public class AStarReittiopas { public static int goalnodenumber = 2; public static int startnodenumber = 1; public static int starttime = 1; public static void main(string[] args) { PriorityQueue Node pq = new PriorityQueue Node (); List Node alreadyvisited = new LinkedList Node (); FileOperations.readDefaultFiles(); 8 Vector Stop stops = FileOperations.stops; Node goalnode = null; boolean goalfound = false; Node n = null; for(stop s : stops) { if(s.number == startnodenumber) { n = new Node(startTime, s, null, null); else if (s.number == goalnodenumber) { Node.goal = s; pq.add(n); while(!pq.isempty() &&!goalfound) { alreadyvisited.add(n); for (Node newnode : pq.poll().getneighbors(stops)) { if(newnode.isgoalstate(goalnodenumber)) { goalfound = true; goalnode = newnode; break; if(!pq.contains(newnode) &&!alreadyvisited.contains(newnode)) { pq.add(newnode); int totaltriptime = goalnode.gettime() - starttime; while(goalfound && goalnode.getparent()!= null) { goalnode.printstate(system.out); goalnode = goalnode.getparent(); System.out.println(n.getLocation().name + Aika: + starttime + \n ); System.out.println( Total trip time: + totaltriptime + minutes. ); 9
Related Search
Similar documents
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks