OOMPA Lecture 17

of 59

Please download to get full document.

View again

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.
PDF
59 pages
0 downs
0 views
Share
Description
OOMPA Lecture 17. Artificial intelligence and game playing Course evaluation & discussion C++ standard template library. Lab4. Design and implement a general game playing framework for deterministic two player zero-sum games Implement Min-Max-search Implement the games TicTacToe
Transcript
OOMPA Lecture 17
  • Artificial intelligence and game playing
  • Course evaluation & discussion
  • C++ standard template library
  • Lab4
  • Design and implement a general game playing framework for deterministic two player zero-sum games
  • Implement Min-Max-search
  • Implement the games
  • TicTacToe
  • Connect-Four
  • Extra point
  • Implement alpha-beta pruning
  • Implement checkers
  • Games as Search Problems
  • The behavior / actions of the opponent are unpredictable, therefore search for a “worst-case”-plan.
  • Time limit, therefore complete search is not feasible and an approximation is needed
  • Algorithm for perfect play (van Neumann 1944)
  • Finite horizon, approximate evaluation (Zuse 1945, Shannon 1950, Samuel 1952)
  • Pruning search tree (McCarthy 1956)
  • Types of GameMiniMax
  • Optimal strategy for deterministic, perfect-information game
  • Idea: Choose move that results in position with highest minmax-value = best achievable payoff against best opponents play
  • 5Max:A3A1A2Min:352A11A13A21A23A31A33A12A22A323128579427MiniMaxFunction MINIMAX-DECISION(game) returns a move for each move in PossibleMoves[game] do value[move] <- MINIMAX-VALUE(apply(move,state),game) end return the move with the highest value[move]Function MINIMAX-VALUE(state, game) returns a utility value if TERMINAL-TEST[game](state) then return UTILITY[game](state) else if MAX is to move in state return the highest MINIMAX-VALUE of SUCCESSORS(state) else return the lowest MINIMAX-VALUE of SUCCESSORS(state)MiniMax Properties
  • Complete: yes, if search tree is finite
  • Optimal : yes, if opponent plays optimal
  • Time complexity : O(bm)
  • Space complexity : O(bm) depth first search
  • Chess b~35 possible moves in each state, m~100 moves per game -> exact solution infeasible
  • Standard solution
  • cutoff test for search (e.g. depth limit)
  • Evaluation function : approximates utility of board position
  • Evaluation Functions
  • For chess for example typically linear weighted sum of features
  • Eval(s) = w1 f1(s) + w2 f2(s) + …wn fn(s)
  • w1=9 f1(s)= #white queens - #black queens w2=5 f2(s) = #white rooks - #black rooks etc.Cutting of Search
  • MINIMAXCUTOFF is identical to MINIMAXVALUE except
  • 1. TERMINAL? is replaced by CUTOFF?
  • 2. UTILITY is replaced by EVAL
  • Ply = one half-move (move by one player)
  • Chess:
  • 4-ply = novice
  • 8-ply = PC, human master
  • 12-ply = Deep Blue, Kasparov
  • Pruning ExampleMax:3A3A1A2Min:325A11A13A21A23A21A12A22A2231282??572A232Standard Template Library
  • The standard template library (STL) contains
  • Containers
  • Algorithms
  • Iterators
  • A container is a way that stored data is organized in memory, for example an array of elements.
  • Algorithms in the STL are procedures that are applied to containers to process their data, for example search for an element in an array, or sort an array.
  • Iterators are a generalization of the concept of pointers, they point to elements in a container, for example you can increment an iterator to point to the next element in an array
  • Containers, Iterators, AlgorithmsAlgorithms use iterators to interact with objectsstored in containersContainerContainerIteratorAlgorithmIteratorObjectsAlgorithmIteratorIteratorAlgorithmContainers
  • A container is a way to store data, either built-in data
  • types like int and float, or class objects
  • The STL provides several basic kinds of containers
  • <vector> : one-dimensional array
  • <list> : double linked list
  • <deque> : double-ended queue
  • <queue> : queue
  • <stack> : stack
  • <set> : set
  • <map> : associative array
  • Sequence Containers
  • A sequence container stores a set of elements in
  • sequence, in other words each element (except for the first and last one) is preceded by one specific element and followed by another, <vector>, <list> and <deque> are sequential containers
  • In an ordinary C++ array the size is fixed and can
  • not change during run-time, it is also tedious to insert or delete elements. Advantage: quick random access
  • <vector> is an expandable array that can shrink or
  • grow in size, but still has the disadvantage that inserting or deleting elements in the middle is costly as it requires to copy chunks of memorySequence Containers
  • <list> is a double linked list (each element has
  • points to its successor and predecessor), it is quick to insert or delete elements but provides no random access (e.g. return 5th element in list)
  • <deque> is a double-ended queue, that means one
  • can insert and delete elements from both ends, it is a kind of combination between a stack (last in first out) and a queue (first in first out) and constitutes a compromise between a <vector> and a <list>Associative Containers
  • An associative container is non-sequential but uses
  • a key to access elements. The keys, typically a number or a string, are used by the container to arrange the stored elements in a specific order, for example in a dictionary the entries are ordered alphabetically.Associative Containers
  • A <set> stores a number of items which contain keys
  • The keys are the attributes used to order the items, for example a set might store objects of the class Person which are ordered alphabetically using their name
  • A <map> stores pairs of objects: a key object and
  • an associated value object. A <map> is somehow similar to an array except instead of accessing its elements with index numbers, you access them with indices of an arbitrary type.
  • <set> and <map> only allow one key of each value,
  • whereas <multiset> and <multimap> allow multiple identical key valuesVector Containerint array[5] = {12, 7, 9, 21, 13 };vector<int> v(array,array+5);12792113v.push_back(15);v.pop_back();13…127921127921150 1 2 3 412792115v.begin();v[3]Vector Container#include <vector>#include <iostream>vector<int> v(3); // create a vector of ints of size 3v[0]=23;v[1]=12;v[2]=9; // vector full v.push_back(17); // put a new value at the end of arrayfor (int i=0; i<v.size(); i++) // member function size() of vector cout << v[i] << ” ”; // random access to i-th elementcout << endl;Constructors for Vector
  • A vector can be initialized by specifying its size and
  • a prototype element or by another vectorvector<Date> x(1000); // creates vector of size 1000, // requires default constructor for Datevector<Date> dates(10,Date(17,12,1999)); // initializes // all elements with 17.12.1999vector<Date> y(x); // initializes vector y with vector xIterators
  • Iterators are pointer-like entities that are used to
  • access individual elements in a container.
  • Often they are used to move sequentially from element to element, a process called iterating through a container.
  • vector<int>array_17vector<int>::iterator423The iterator corresponding tothe class vector<int> is ofthe type vector<int>::iterator 12size_4Iterators
  • The container member functions begin() and end() return an iterator to the first and past the last element of a container
  • vector<int> vv.begin()array_17423v.end()12size_4Iterators
  • One can have multiple iterators pointing to different or identical elements in the container
  • vector<int> vi1array_174i22312i3size_4Iterators#include <vector>#include <iostream>vector<int> v; // initialize empty vector v.push_back(13);v.push_back(9);v.push_back(8);vector<int>::iterator iter=v.begin(); // iterator for class vector// define iterator for vector and point it to first element of vcout << ”first element of v=” << *iter; // de-reference iteriter++; // move iterator to next elementiter=v.end()-1; // move iterator to last element Iteratorsint max(vector<int>::iterator start, vector<int>::iterator end){ int tmpmax=*start; while(start != stop) { if (*start > tmpmax) tmpmax=*start; ++start; } return tmpmax;}cout << ”max of v = ” << max(v.begin(),v.end());Iterator Categories
  • Not every iterator can be used with every container for example the list class provides no random access iterator
  • Every algorithm requires an iterator with a certain level of capability for example to use the [] operator you need a random access iterator
  • Iterators are divided into five categories in which a higher (more specific) category always subsumes a lower (more general) category, e.g. An algorithm that
  • accepts a forward iterator will also work with a bidirectional iterator and a random access iterator inputforwardbidirectionalrandomaccessoutputFor_Each() Algorithm#include <vector>#include <algorithm>#include <iostream>void show(int n) { cout << n << ” ”; } int arr[] = { 12, 3, 17, 8 }; // standard C arrayvector<int> v(arr, arr+4); // initialize vector with C array for_each (v.begin(), v.end(), show); // apply function show // to each element of vector vFind() Algorithm#include <vector>#include <algorithm>#include <iostream>int key;int arr[] = { 12, 3, 17, 8, 34, 56, 9 }; // standard C arrayvector<int> v(arr, arr+7); // initialize vector with C array vector<int>::iterator iter;cout << ”enter value :”;cin >> key;iter=find(v.begin(),v.end(),key); // finds integer key in vif (iter != v.end()) // found the element cout << ”Element ” << key << ” found” << endl;else cout << ”Element ” << key << ” not in vector v” << endl;Find_If() Algorithm#include <vector>#include <algorithm>#include <iostream>Bool mytest(int n) { return (n>21) && (n <36); };int arr[] = { 12, 3, 17, 8, 34, 56, 9 }; // standard C arrayvector<int> v(arr, arr+7); // initialize vector with C array vector<int>::iterator iter;iter=find_if(v.begin(),v.end(),mytest); // finds element in v for which mytest is true if (iter != v.end()) // found the element cout << ”found ” << *iter << endl;else cout << ”not found” << endl;Count_If() Algorithm#include <vector>#include <algorithm>#include <iostream>Bool mytest(int n) { return (n>14) && (n <36); };int arr[] = { 12, 3, 17, 8, 34, 56, 9 }; // standard C arrayvector<int> v(arr, arr+7); // initialize vector with C array int n=count_if(v.begin(),v.end(),mytest); // counts element in v for which mytest is true cout << ”found ” << n << ” elements” << endl;Linked List
  • A linked list is composed of a chain of elements (links). Each element contains some data and a pointer to the next element in the list.
  • In a double linked list, each element also contains a pointer to its predecessor.
  • ElementElementElementnextdatanextdatanextdataElementElementElementnextprevdatanextprevdatanextprevdataList Container
  • A list container is a double linked list, in which
  • each element contains a pointer to its successor and predecessor.
  • It is possible to insert and remove elements at arbitrary location in the list, without having to copy large chunks of memory as with vectors
  • Lists do not allow random access but are efficient to
  • insert new elements and to sort and merge listsList Containerint array[5] = {12, 7, 9, 21, 13 };list<int> li(array,array+5);12792113li.push_back(15);li.pop_back();13…12792112792115li.pop_front();li.push_front(8);12…8127921157921li.insert()19712172123Sort & Merge
  • Sort and merge allow you to sort and merge elements in a container
  • #include <list> int arr1[]= { 6, 4, 9, 1, 7 };int arr2[]= { 4, 2, 1, 3, 8 };list<int> l1(arr1, arr1+5); // initialize l1 with arr1list<int> l2(arr2, arr2+5); // initialize l2 with arr2l1.sort(); // l1 = {1, 4, 6, 7, 9}l2.sort(); // l2= {1, 2, 3, 4, 8 }l1.merge(l2); // merges l2 into l1 // l1 = { 1, 1, 2, 3, 4, 4, 6, 7, 8, 9}, l2= {}Functions Objects
  • Some algorithms like sort, merge, accumulate can take a function object as argument.
  • A function object is an object of a template class that has a single member function : the overloaded operator ()
  • It is also possible to use user-defined functions instead of pre-defined function objects
  • #include <list>#include <functional> int arr1[]= { 6, 4, 9, 1, 7 };list<int> l1(arr1, arr1+5); // initialize l1 with arr1l1.sort(greater<int>()); // uses function object greater<int>// for sorting in reverse order l1 = { 9, 7, 6, 4, 1 }Function Objects
  • The accumulate algorithm accumulates data over the elements of the containing, for example computing the sum of elements
  • #include <list>#include <functional> #include <numeric>int arr1[]= { 6, 4, 9, 1, 7 };list<int> l1(arr1, arr1+5); // initialize l1 with arr1int sum = accumulate(l1.begin(), l1.end() , 0, plus<int>());int sum = accumulate(l1.begin(), l1.end(),0); // equivalentint fac = accumulate(l1.begin(), l1.end() , 0, times<int>());User Defined Function Objectsclass squared _sum // user-defined function object{ public: int operator()(int n1, int n2) { return n1+n2*n2; } }; int sq = accumulate(l1.begin(), l1.end() , 0, squared_sum() );// computes the sum of squaresUser Defined Function Objectstemplate <class T>class squared _sum // user-defined function object{ public: T operator()(T n1, T n2) { return n1+n2*n2; } }; vector<complex> vc;complex sum_vc;vc.push_back(complex(2,3));vc.push_back(complex(1,5));vc.push_back(complex(-2,4));sum_vc = accumulate(vc.begin(), vc.end() , complex(0,0) , squared_sum<complex>() );// computes the sum of squares of a vector of complex numbersAssociative Containers
  • In an associative container the items are not arranged in sequence, but usually as a tree structure or a hash table.
  • The main advantage of associative containers is the speed of searching (binary search like in a dictionary)
  • Searching is done using a key which is usually a single value like a number or string
  • The value is an attribute of the objects in the container
  • The STL contains two basic associative containers
  • sets and multisets
  • maps and multimaps
  • Sets and Multisets#include <set>string names[] = {”Ole”, ”Hedvig”, ”Juan”, ”Lars”, ”Guido”}; set<string, less<string> > nameSet(names,names+5);// create a set of names in which elements are alphabetically// ordered string is the key and the object itselfnameSet.insert(”Patric”); // inserts more namesnameSet.insert(”Maria”);nameSet.erase(”Juan”); // removes an elementset<string, less<string> >::iterator iter; // set iteratorstring searchname; cin >> searchname;iter=nameSet.find(searchname); // find matching name in setif (iter == nameSet.end()) // check if iterator points to end of set cout << searchname << ” not in set!” <<endl;else cout << searchname << ” is in set!” <<endl;Set and Multisetsstring names[] = {”Ole”, ”Hedvig”, ”Juan”, ”Lars”, ”Guido”, ”Patric”, ”Maria”, ”Ann”}; set<string, less<string> > nameSet(names,names+7);set<string, less<string> >::iterator iter; // set iteratoriter=nameSet.lower_bound(”K”); // set iterator to lower start value ”K”while (iter != nameSet.upper_bound(”Q”)) cout << *iter++ << endl;// displays Lars, Maria, Ole, PatricMaps and Multimaps
  • A map stores pairs <key, value> of a key object and associated value object.
  • The key object contains a key that will be searched for and the value object contains additional data
  • The key could be a string, for example the name of a person and the value could be a number, for example the telephone number of a person
  • Maps and Multimaps#include <map>string names[]= {”Ole”, ”Hedvig”, ”Juan”, ”Lars”, ”Guido”, ”Patric”, ”Maria”, ”Ann”};int numbers[]= {75643, 83268, 97353, 87353, 19988, 76455, 77443,12221};map<string, int, less<string> > phonebook;map<string, int, less<string> >::iterator iter;for (int j=0; j<8; j++) phonebook[names[j]]=numbers[j]; // initialize map phonebookfor (iter = phonebook.begin(); iter !=phonebook.end(); iter++) cout << (*iter).first << ” : ” << (*iter).second << endl;cout << ”Lars phone number is ” << phonebook[”Lars”] << endl;Course Analysis
  • Fill out the questionaire on the course webpage
  • Use the comment boxes for suggestions, complaints, negative and positive aspects of the course.
  • Course Analysis
  • Do you think the course in general was
  • Easy
  • Medium
  • Difficult
  • What was most/least difficult
  • Exam
  • Seminars
  • Labs
  • Lectures
  • Course Analysis
  • Do you think the course was interesting and useful for you?
  • Yes
  • Partially useful
  • No
  • Do you think your previous knowledge (e.g. programming experience in JAVA) was sufficient for this course?
  • Yes
  • Somewhat
  • No
  • Course Analysis
  • What do you think about the course literature Larman book?
  • Would you recommend the book to someone else?
  • Course Analysis
  • What do you think about the lectures?
  • Pedagogics
  • Presentation
  • Lecture notes, references
  • Which topics did you find most/least interesting
  • OO analysis and design
  • Object oriented programming
  • Extreme programming
  • Design patterns
  • UML
  • C++
  • Smalltalk
  • Course Analysis
  • What do you think of the seminars?
  • Useful
  • Partially useful
  • Not useful at all
  • Assistents
  • Competent
  • Partially Competent
  • Incompetent
  • Course Analysis
  • What do you think about the style of seminars?
  • Presentation by students or rather assistant
  • More or fewer discussions
  • More or fewer practical exercises
  • Did you learn most on OOA/D by
  • Attending the lectures
  • Attending the seminars
  • Reading the book
  • Doing the labs
  • Course Analysis
  • What do you think about the lab hours
  • Help by assistents
  • Good
  • Acceptable
  • Unacceptable
  • Availability, number of hours, waiting time
  • Good
  • Acceptable
  • Unacceptable
  • Course Analysis
  • Did you feel that you got enough and competent help in general, help beside the labs, pointers to reading, hints, tips
  • Good
  • Acceptable
  • Unacceptable
  • Course Analysis
  • What do you think about the lab assignments
  • Difficulty
  • Easy
  • Suitable
  • Difficult
  • Programming tasks
  • Interesting
  • Partially interesting
  • Uninteresting
  • Course Analysis
  • Which lab assignment did you like best/least ?
  • Lab 1 class hierarchy (graphics)
  • Lab 2 design patterns
  • Lab 3 bank (CORBA)
  • Lab 4 game playing C++
  • Lab 5 Smalltalk
  • Course Analysis
  • How much time did you spend on the labs in total?
  • Less than 60 hours
  • 60-120 hours
  • More than 120 hours
  • What do you think about the lab redovisning?
  • Fair
  • Mostly fair
  • Unfair
  • Course Analysis
  • What do you think about the exam?
  • Difficulty
  • Comprehensibility
  • Prior information about the exam (test exam)
  • Would you like to see more/less
  • Practical assignments (drawing UML diagrams)
  • Multiple choice questions
  • Verbal questions
  • Course Analysis
  • What is the percentage of your study time this semester that you spend on this course?
  • Less t
  • Related Search
    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