Genaral areas of interest: Algorithms, complexity, robotics. PROJECT I Dr Nicolai Vorobjov nnv@cs.bath.ac.uk PROGRAM FOR SOLVING TWO-PERSON GAMES The aim is to design an application for finding optimal strategies in finite two-person games. Such games are called bimatrix. They include all possible situations in which two parties have finite number of possible ways to act (strategies) and the outcomes lead to payoffs depending on the pair of chosen strategies. Chess is an example, though hardly tractable, stone-paper-scissors is another, very simple to solve. The application should be able to accept any pair of pay-off matrices as an input and to output optimal mixed strategies. For games usually defined in the positional form an appropriate universal representation of the input should be designed. The project includes the stage of learning the background game-theoretical material including the existing algorithms for solving bimatrix games. A similar project: PROGRAM FOR TEACHING GAME THEORY The aim of the project is to design a program which will help to explain and illustrate the basic concepts of the theory of games. When the number of strategies of one of the players in a matrix game is small (say, two or three) then the optimal strategies can be found by drawing certain two- or three-dimensional pictures. The program will draw such pictures and explain interactively some elements of the theory. Pre-requisite knowledge: some modest knowledge of linear algebra Indicative reading: any introductory text on game theory PROJECT II Dr Nicolai Vorobjov nnv@cs.bath.ac.uk COMPUTER LINEAR ALGEBRA SYSTEM The aim is to design a basic linear algebra system as a very simplified analogy (and a part) of usual computer algebra systems, like REDUCE, Maple, etc. It should include algorithms for matrix multiplication (trivial, as well as advanced and more efficient, like Strassen's), for solving systems of linear equations (Gauss, and based on fast matrix multiplication), computing determinants, etc. The system should have a convenient interactive interface with an ability to extend by adding new commands. Existing systems could be used as examples, but all programming is supposed to be original. Pre-requisite knowledge: some basic knowledge of linear algebra Indicative reading: any introductory text on linear algebra, user manual for Maple. PROJECT III Dr Nicolai Vorobjov nnv@cs.bath.ac.uk ROBOT MOTION PLANNING The aim is to design a graphical application for robot motion planning on the plane in the presence of polygonal obstacles. In one version of the problem the robot is considered as a point and we are looking for a shortest piece-wise linear path connecting "start" and "finish". In another version the robot is a polygon, and the aim is to decide whether it is possible for him to pass through a corridor of a complex form, and if yes, to plane the move. Pre-requisite knowledge: some basic knowledge of computer graphics and algorithms Indicative reading: see NNV PROJECT IV Dr Nicolai Vorobjov nnv@cs.bath.ac.uk DOMINO PARTNERS The game of domino is usually played between two teams of two players in each. Since it might be hard to find enough partners willing to play, it's desirable to have a computer program which can model one, two or three players, breaking them in teams, as required. The project consists of designing such a program together with a graphic interface to show moves. Pre-requisite knowledge: non-special Indicative reading: web search on the existing software in this area