RPS的简单机器学习

1 .CMPE 135: Object-Oriented Analysis and Design September 25 Class Meeting Department of Computer Engineering San Jose State University Fall 2018 Instructor: Ron Mak www.cs.sjsu.edu/~mak 1

2 .Simple Machine Learning for RPS Human players of the Rock Paper Scissors game try to develop strategies to beat the opponent. Therefore, humans generally do not make random choices. Human choices exhibit patterns that a computer can discover and exploit. 2

3 .Simple Machine Learning for RPS , cont’d Continuously record the last N choices between the human and the computer player. Throw out the oldest choice in order to add a new one. For example, suppose N = 5 and during the game, the recorded choices are (the human’s choices are underlined): The last choice was made by the human, and it was paper . 3 P S R S P

4 .Simple Machine Learning for RPS , cont’d For each recorded sequence that ends with the human’s choice, the computer should store how many times that sequence has occurred (each sequence’s frequency). For example, for N = 5, the stored sequences and their frequencies may be (in no particular order, human choices are underlined): 4 R S P S R :1, S P R P P :3, R S P R S :2, R S P S S :4, R S P S P :3, S S R P P :2

5 .Simple Machine Learning for RPS , cont’d Suppose the last four choices are R S P S . In the last round, the human chose paper and the computer chose scissors. The computer can predict that the human will most likely next choose scissors , since R S P S S appears more times than R S P S R and R S P S P in the stored frequencies. Therefore, the computer should choose rock to beat the human’s predicted choice of scissors. 5 R S P S R :1, S P R P P :3, R S P R S :2, R S P S S :4, R S P S P :3, S S R P P :2

6 .Simple Machine Learning for RPS , cont’d When a game ends, write the frequency data to a file, so that when a new game begins, these frequencies can be read back in. As the computer plays more games and stores more frequency data, it becomes increasingly more capable of predicting the human’s next choice. Over the long haul, the computer will become very difficult for humans to beat. 6

7 .Assignment #4: RPS with Simple ML Update your Rock-Paper-Scissors game program from Assignment #3 by adding the simple machine learning (M L) algorithm for making the computer’s choice in each round. Design an interface (abstract class) with pure virtual member functions to represent the computer’s choice algorithm. Implement the interface with the random choice algorithm and with the simple ML choice algorithm. Be able to swap between the two algorithms with minimal changes to the rest of the code. 7

8 .Assignment #4 , cont’d The ML algorithm should save its data at the end of each game to be read by the next game. What to submit A zip file of all the C++ source files for your game. Instructions on how to build and run your game. Text output from playing a 20-round game. A short (2- or 3-page) report that explains: Your interface design for the computer’s choice algorithm. How you store and read the ML frequency data. Due Friday, October 5. 8

9 .9

10 .10 Inheritance By now, inheritance should be a familiar concept. Object-Oriented Design & Patterns by Cay Horstmann John Wiley & Sons, 2006.

11 .11 Manager : public Employee class Employee { public:     Employee(string nam ) { name = nam ; }    void set_salary (double sal ) { salary = sal ; }    string get_name () const { return name; }    double get_salary () const { return salary; } private:    string name;    double salary; } class Manager : public Employee { public:    Manager(string aName ) { ... }    void set_bonus (double bon) { bonus = bon; } // new member function    double get_salary () const { return salary + bonus } // overrides Employee // member function private:    double bonus; // new member variable } What are the differences between Manager and Employee ?

12 .12 Superclasses and Subclasses Employee is the superclass (or base class ). Manager is the subclass . A manager “ is a ” employee. A manager is a specialized type of employee. The set of Manager objects is a subset of the set of Employee objects. Object-Oriented Design & Patterns by Cay Horstmann John Wiley & Sons, 2006.

13 .13 Class Hierarchies AKA inheritance hierarchies . In the real world, hierarchies express general/specific relationships among concepts. The most general concept is at the root of a tree. More specific concepts are children . The most specific concepts are leafs .

14 .14 Class Hierarchies , cont’d Object-oriented programming uses class hierarchies. The most general superclass is at the root of a tree. More specific subclasses are children . The most specific subclasses are leafs . Class hierarchies can be complex. But they shouldn’t be.

15 .15 Class Hierarchies , cont’d Object-Oriented Design & Patterns by Cay Horstmann John Wiley & Sons, 2006.

16 .16 Class Hierarchies , cont’d Object-Oriented Design & Patterns by Cay Horstmann John Wiley & Sons, 2006. Java’s “Swing” GUI classes.

17 .17 The Liskov Substitution Principle Named after Barbara Liskov . MIT computer science professor A pioneer in object-oriented programming. In your C++ code, you should be able to substitute a superclass object by a subclass object . Employee *e = new Employee ("John Doe"); cout << "salary = " << e -> get_salary () << endl ; Superclass object Employee *e = new Manager ("Mary Jane"); cout << "salary = " << e -> get_salary () << endl ; Subclass object

18 .18 Overridden Member Functions Assign an object value to a variable. The data type of variable e is Employee* . The data type of the object value is Manager* . At run time, which member function is called? Employee:: get_salary () Manager:: get_salary () In C++, that depends on how you declare the get_salary () member functions. Employee *e = new Manager ("Mary Jane"); cout << "salary = " << e -> get_salary () << endl ;

19 .Overridden Member Functions , cont’d 19 class Employee { public:     ...    double get_salary () const { return salary; } private:    string name;    double salary; } class Manager : public Employee { public:    ...    double get_salary () const { return ... } // overrides Employee // member function private:    double bonus; // new member variable } Employee *e = new Manager ("Mary Jane"); cout << "salary = " << e -> get_salary () << endl ; Employee:: get_salary () will be called. Determined by the data type Employee of variable e .

20 .Polymorphism Since the value that e points to is a Manager object, we really want to get a manager’s salary, not that of a general employee. We want which member function get_salary () to call to be determined by the data type of the runtime value of e . Not the data type of the variable e . This is the principle of polymorphism . 20 Employee *e = new Manager ("Mary Jane"); cout << "salary = " << e -> get_salary () << endl ;

21 .Polymorphism , cont’d To make get_salary () polymorphic in C++, we must declare it to be virtual . You only need to declare it virtual in the base class. 21 class Employee { public:     ...    virtual double get_salary () const { return salary; } ... } class Manager : public Employee { public:    ...    double get_salary () const { return ... } ... }

22 .Polymorphism , cont’d Polymorphism is not free. C++ must consult a virtual table at run time for every class that contains a virtual function. C++ cannot tell at compile time what the value (and hence value’s data type) of the variable will be. Consulting the virtual table to determine which member function to call will affect performance. Use polymorphism judiciously. 22 Demo

23 .23 The Liskov Substitution Principle , cont’d How is the Liskov Substitution Principle related to programming to the interface? The type of variable e is the superclass Employee instead of the more specific subclass Manager . Variable e can point to an object instantiated from another subclass of Employee without causing further code changes. Variable e is not restricted to any particular subclass. Employee *e = new Manager ("Mary Jane"); cout << "salary = " << e -> get_salary () << endl ;

24 .24 Invoke a Superclass Member Function Suppose a manager’s salary is his regular employee salary plus a bonus that only managers get. class Manager : public Employee { public: double get_salary () const    { return salary + bonus;    }    ... } public: double get_salary () const { return get_salary () + bonus; } A subclass cannot access the private fields of its superclass. What’s wrong with this solution? Infinite recursion! What’s wrong with this solution?

25 .25 Invoke a Superclass Member Function , cont’d Name the superclass and use the scope resolution operator :: . Turns off polymorphism. class Manager : public Employee { public: double get_salary () const    { return Employee:: get_salary () + bonus;    }    ... }

26 .26 Invoke a Superclass Constructor You can name the superclass in the subclass constructor to call the superclass constructor. Pass any required parameters. class Manager : public Employee { public: Manager(string name) : Employee(name) , bonus(0)    { ...    }    ... }

27 .Invoke a Superclass Constructor , cont’d If a subclass constructor does not explicitly call a superclass constructor, the superclass’s default constructor (the one without parameters) is called automatically . In this case, the superclass must have a default constructor. 27

28 .28 Invoke a Constructor from Another A class can invoke one of its constructors from another constructor. Called delegating constructors . class Manager : public Employee { public: Manager (string name) : Employee (name), bonus(0)    { ...    }    Manager (string name, double bon) : Manager(name) , bonus(bon) { ... } } First became available with C++11.

29 .29 Preconditions and Inheritance Recall that a precondition of a function is a condition that must be true before the method can be called. The caller is responsible for making sure the precondition is true before making the call. Suppose a subclass overrides a superclass member function. The precondition of the subclass member function cannot be stronger than the precondition of the overridden superclass member function.