Progress Report and Detailed Plan November 10th, 2002 Author: Roy Schestowitz / Supervisor: Dr. Andrea Schalk This paper presents the background and future plans for project number 500 Table of Contents 1 Introduction 2 Background 2.1 Othello 2.2 Game-Playing Programs 2.3 Game Theory 3 Progress 4 Objectives 4.1 Main Objectives 4.2 Secondary Objectives 4.3 Mandatory Milestones 5 Information Sources 5.1 Literature 5.2 On-line Sources 6 System Development Outline 6.1 Requirement Analysis 6.2 Specification 6.3 System Design 6.3.1 High-level Design 6.3.2 Low-level Design 6.4 Implementation 6.5 Testing 6.5.1 Stability 6.5.2 Performance 6.5.3 Strength 6.6 Documentation 6.6.1 User's Manual 6.6.2 Programmer's Manual and Documentation 6.7 Simulation and Research 6.8 Maintenance and Extension 7 Time Management 7.1 Project Development 7.2 Project Deliverables 8 Deviation from Project Proposal and Plan 9 Summary 10 Appendices 1 Introduction This project has been set to produce an application which will be titled Othello Master due to some visual similarity to an older game called Chess Master. It will require knowledge of game theory and advanced computer graphics. The main research issues to be addressed are: 1. How to represent a game scene in a convincing three-dimensional way. This project also attempts to put considerable effort into advanced graphical interfaces. 2. How to carry out the complicated task of computing a good move in the game Othello. 3. How to utilise different algorithmic approaches to solve problem 2. 4. How to enable the program to play against itself using different approaches and generate statistics for beneficial researchThe main research issue to be addressed in this project shall be the strength of game playing algorithms, derived from the results of games being played. or analysis of the program's performance. 5. How to store the state of a program in a reliable and persistent manner, with the possibility of retaining a stack of multiple states. Othello Master will utilise the basic principles of game theory and implements them in an imperative programming language. It also will work closely with a package called GLUTProvides scene description and user interaction facilities., which will be responsible for the graphical domain of the program. 2 Background 2.1 Othello Othello is an easy game to learn, but long practice and experience are required to master it. The following is a brief summary of the rules: At the beginning of the game, four stones are already placed at the centre of an 8x8 standard board. The two stones of one player are placed diagonally and, by convention, the player to make the first move is of white colour, whereas the other is of black colour. The stones are all two-sided and flipping them changes their colour to the opponent's colour. A legal move is such that it reverses one or more stones of the opponent's colour. To reverse a stone, one colour places one of his stones in such a way so that it surrounds a sequence of one or more of the opponent's stones. Such a sequence of opponent's stones must be ending in a board slot that is occupied by a reversing player's stone. All straight lines are applicable in such a reversal: horizontal, vertical or diagonal. If no reversal is possible, the turn is passed to the opponent. The game is finished when neither player has any legal moves left. Usually, by this point the board is completely full. Whoever has the most stones placed on the board at that point wins the game. There are a few extra points that are worth mentioning: * Only one type of element can be placed on the board. A board slot can be either empty or occupied by a stone of one player. * Almost any stone on the board can be recaptured by the opponent i.e. the game score is highly volatile. * Low number of possible moves is a great disadvantage in the game. 2.2 Game-Playing Programs A game-playing program will be required, above all, to generate a valid and good move given any game state. The game itself can be viewed as a form of a tree - one which specifies all possible playsSequence of valid moves in the game. This can be more abstractly defined as a path in the game tree. in the game. In practice, it will attempt to find the best path within the game tree. Our application will evaluate a current game state by inspecting various different aspects such as current positioning, prospective positioning, structure formed by stones, etc. Structure and formation are some very subtle issues that differ significantly from one game to another. In a game like Chess, we might want to take into consideration the structure that a group of pieces form, or the structure of the board slots that are reachable by any of the pieces. In a game like Othello, the shape of an occupied cluster of stones might be an aspect that is worth paying great attention to. Analysis of the formation of stones which were placed on the sides and corners of the board may even be a more fruitful process. At the design stage, many of these issues must be taken into consideration. The most important aspect of this project will be the strength of the game-playing engine, given that the creation of a strong playing-engine is my personal main ambition. 2.3 Game Theory In order to apply our logical analysis and knowledge of Othello within a programming language and practically be able to generate a good play, we must be aware of some of the basic elements of game theory. Alpha-beta pruningBasic theoretical principle that allows anticipating moves in a game. traverses the game tree and evaluates the state of the game (as seen from one player's point of view) at different positions of the tree using an evaluation function. Since we cannot traverse the whole game tree of an Othello gameAs the traversal depth is incremented, the time complexity shows exponential characteristics. , we can concede certain plays that appear to lead to worse evaluation results. Much more on the broad topic of game theory and its application within my project will be available in the final project report. 3 Progress This section presents the details of the progress made up to this date. The initial plan, as it was described in the previous document (c/f Project Proposal and Plan), was to be complete the requirement analysis and specifications by this point. Necessary reading, primarily concerning game theory, should have been almost completed by this point too, as well as some reading about the graphical aspects, bearing in mind that the graphical domain can, at this point, be accommodated by some simple I/O facilities such as a terminal/shell under Unix. It is now well known and defined what is to be achieved and design work can take place shortly. Many of the issues concerning the construction of the game-playing engine have now been resolved too. Literature sources on game theory have provided me with sufficient knowledge about the process that needs to be carried out in order to predict the opponent's moves and the process of evaluation. Furthermore, supplementary notes and on-line sources have given me some better insight into techniques of designing and coding game-playing applications. What is required to be achieved by the system is more precisely recorded in various sketches in my project log book as well as in section 4. 4 Objectives 4.1 Main Objectives The application should: 1. Allow an Othello game to be played in accordance with the predefined rules and deal with all the game exceptions e.g. deadlocks. 2. Make use of alpha-beta pruning and ensure that its function is sufficiently parameterised so that we can control its behaviour rather easily. The result of such parameterisation is high usability and flexibility. 3. Enable the program and the user to control the behaviour of the game-playing engine. Such control should allow the program to play better, worse or even more quickly by fine-tuning and alternating the functions used to compute a given move. 4. Allow the inclusion of extra features such as: * Load and save game * Board editing tool with an appropriate interface * ASCII mode Othello * Undo function relying on a stack of game states * View customisation 4.2 Secondary Objectives Convert the application into a package that: 1. Provides support for the standard player vs. game mode and boasts various different levels of strength, corresponding to different approaches and algorithms that are being utilised. The main intention is to have different levels of difficulty, where preferably and quite naturally, the broaderBreadth typically refers to LOC (Lines Of Code) value, however, larger amounts of code do not imply better performance. Broad algorithms can be defined as those that perform deeper and wider search of the game tree. algorithms should produce better game performance. 2. Provides multi-player mode, where one human player plays against another. 3. Allows watching the program as it plays against itself on different levels of strength. This will, in principal, allow tracing a game that is being played very quickly and be of assistance in the later debugging process. 4. Records game information by generating a game log. Such a log will specify all placements of stones, display the final board state and, most importantly, record the final score. 5. Generates statistical reports automatically for many consecutive games. 4.3 Mandatory Milestones The following suggests a listing of the features that must be generated by the completion of the project: 1. Othello game can be played with the control of two user controlled players. 2. Alpha-beta pruning implemented and the program is able to carry out a legal play. 3. The above simple play is now changed to a sensible and good move and the program is able to compete with other Othello game-playing application. In order to convert Othello Master into a unique package, we may as well wish to include the following as milestones: 1. 'Save game' and 'load game' features are implemented and an 'undo' stack is maintained throughout the application's run. 2. Versatile computation algorithms are devised and the program can play against itself. 3. Logs with a sensibly informative layout are generated for each game. 4. Reports are generated and hold statistical data about multiple games played within the application. 5. The board state can be altered manually using a board editing tool. 6. ASCII interface implemented and is bug free. 7. Customisation of the user interface is available. 8. Computation of a move is controlled by command-line arguments or menu entries within the GUI. 5 Information Sources 5.1 Literature * CS3192 lecture notes, which are available from the project supervisor. These notes supply the fundamental knowledge of game theory and some background on how to apply its principles within a program e.g. data structures and alpha-beta pruning. * CS2072 lecture notes, which are available on-line and off-line. These will provide some background on advanced theoretical use of OpenGL. * CS3071 lectures notes. Background on features such as illumination, texture mapping, hidden-surface removal, object shading and some practical guidance on those is included in those. * GLUT specifications available off-line in PDF format. * CS1052, CS2341 and CS2452 lecture notes on the software development process. 5.2 On-line Sources * http://www.mattelothello.com/purpleindex.html A great resource of tips on Othello playing techniques and strategies. * http://www.dcc.unicamp.br/~stolfi/EXPORT/images/textures/ppm-400x400/ A graphical library of PPM images to be used as a resource of textures for the OpenGL GUI. * http://crow.cs.und.ac.za/angus/GameProgramming/OglTextures.html One of many OpenGL FAQ sources to be used for scene rendering. * http://www.nada.kth.se/~gunnar/howto.html Notes on searching and position evaluation in Othello. * http://home.tiscalinet.ch/t_wolf/tw/misc/reversi/html/index.html The Anatomy of a Game Program. * http://vcg.iei.pi.cnr.it/swform.html Bump mapping demo and illustration program. This complements the graphical aspects of the application. * http://www.codesampler.com/oglsrc.htm More advanced OpenGL examples. * http://www1.ics.uci.edu/~eppstein/180a/w99.html Strategy and board game programming. * http://www.maths.nott.ac.uk/personal/anw/G13GAM/ Game theory from Nottingham University. 6 System Development Outline The system is to be built in several stages, as defined by the software engineering discipline: 6.1 Requirement Analysis At this Stage the requested result is to be discovered and analyzed. It is important that it is ensured that this project will evolve into a non-trivial entity - one which will make this project a 'one of a kind' and, therefore, more interesting to analyze and discuss. 6.2 Specification This phase will produce some clear description of what is to be achieved without having us concerned about how to implement everything. 6.3 System Design We are now looking at how the system will be implemented. This can be logically divided into two different stages: 6.3.1 High-level Design Also functional design. We need to agree on which modules the system will comprise of and what each one of them is responsible for. Diagrams could, indeed, be useful here as we are interested in some structural representation, which will ease our process of understanding the system. 6.3.2 Low-level Design We would need to incorporate the above and develop some pseudo-code incrementally. This will be a very time consuming stage where programming skills are essential. Also, efficiency issues should be addressed here, otherwise they will have to wait to a much later stage where the effort spent will be greater. Design of the algorithms for all the different approaches takes place at this stage. This is a good point to refer to the information sources and reveal some of the different conventional methodologies that are used to solve the problem of computing a good play. A simple and useful starting point would be designing one algorithm that will make an arbitrary placement of a stone (preferably a random one). 6.4 Implementation Using the output of the above stage (diagrams, paper or text) we need to code what was agreed on previously. If C is used, a Makefile needs to be created to link all the different parts of the overall system and the pseudo code needs to be translated into (lower-level) imperative code. 6.5 Testing 6.5.1 Stability Is our program robust enough to allow all games to be ended gracefully without crashing? If exceptions occur, does the system catch them? Does it handle them appropriately? All of these factors should be taken into consideration if we wish to extend the system comfortably and see if it is going through unexpected and undesirable paths. 6.5.2 Performance Let us check if the system is operating quickly enough. Should we impose some constraints on the time that the CPU can spend computing a move? Should we modify the graphical engine to allow more frames to be generated in a given time? 6.5.3 Strength It is highly advisable that Othello Master is then put against as many other Othello-playing applications as possible. Testing it against other playing engines will give us an indication of how well it plays against other game engines with (possibly) different approaches. Allowing experienced human players to play against Othello Master may also prove to be useful since more constructive analysis and feedback can be obtained. The drawback of this idea is the fact that this can be slow and tedious. Assignment of difficulty titles to the various approaches is left untouched until the simulation phase which will be discussed later (c/f section 6.7). 6.6 Documentation 6.6.1 User's Manual The user will require having a help feature within the program, but is that enough? Perhaps the user may wish to use some non-trivial options too. We can provide some command-line options specification, as well as a user's manual, which will explain how to use the system more productively. A more detailed manual with concise reference to all the features that are available in Othello Master will form a part of the final project report. Relevant bits from this report can then be exported and expanded to form an official user's manual. 6.6.2 Programmer's Manual and Documentation The code which may be very readable to its creator is not always as manageable and understandable to another programmer that wishes to extend, improve or maintain it. Therefore, some more abstract views of the system, along with some description in natural language can save a lot of time and effort. The following are some basic suggestions: 1. It needs to be assured that the code is well documented, preferably with comments where appropriate. 2. A functional and modular summary is necessary to give a system overview. This can also prove to be useful if we want to re-use the code, let us say, for some new chess application. Finding the appropriate functions fairly trivial in this way. 3. A diagram of the system structure would be highly appreciated by the next person to familiarise himself/herself with the code structure. It often proves to be crucial for the understanding of the interactions within it. 4. A report of how the system works as a whole, how to compile it, platform/OS dependent code and debugging tools are a necessity. It is a very common phenomenon for a programmer to find himself/herself lost with a piece of code that is unreadable, unusable or lacks the compilation facilities. 6.7 Simulation and Research This is a phase that is applicable in our project, but not necessarily in other software engineering development processes. We can now utilise batch facilities to have the program play itself. Most importantly, if we have written different game-playing algorithms (corresponding to different approaches), we can now gather some game statistics which will indicate which approach is stronger than another or which seems to have special weaknesses against specific other approaches. if simulation time allows, we can extend this series of testsFor N levels of difficulty in our game, N! testing series shall take place. by parameterisation of the existing algorithms. Fine-tuning of those algorithms is now applicable, but more on this will be discussed in the final project report. We may have to conduct a more complex analysis that will produce graphs and tables. These will also be valuable for the later project report. Some research can take place on performance and strength of certain Othello-playing algorithms, as the end of this section will discuss in greater detail. Having performed these analyses, we can now have some vague conclusion as for which approaches are stronger than others. Since the interface to the end-user should not bog down to details of implementation, linking each approach to some word that will indicate a difficulty level, will be a wise step. The allegedly best algorithm that we have put together should, for instance, be titled 'Master'. To determine which algorithms appear to perform better than others within a game of Othello and to adjust or fine-tune those appropriately, we will certainly have to re-write some code. This will require a long repetitive process of testing and re-implementing the code. In fact, a testing-implementation loop will consume a considerable amount of time at this phase. As for the aspect of research, we can derive from the above figures and logs (or possibly even charts): * The time complexity of each approach - by accumulating the duration of each move. * The strength of each approach - by inspecting the results of a series of games. * Stability - hopefully, this will not be an issue. If and when bugs occur, the full attention should again be diverted to the previously specified testing phase. The results of these observations and analyses shall also form a reasonably large section in the final project report. Extending a project which initially focused on construction and development into one of contribution to research has often been encouraged by the project supervisor. 6.8 Maintenance and Extension When the system, as it was initially intended to look like, has become a finished package (as specified within the main objectives) , we might desire to extend it or improve it by adding more features or reviewing the algorithms respectively. This stage is a never-ending process which would be classified as 'just a possibility' at this point. The tasks listed as secondary objectives should be the ones to be taken into consideration here. Shall any other ideas come up during development, assuming that they are of some importance of use, we may add them to the list of the secondary tasks. It is quite likely that some of these features that are identified later are even more useful than the ones currently suggested. The previous prioritisation should be re-evaluated in such a case too. However, since the code is flexible enough to allow the game to mutate into anotherFor instance, most of the code can be reused for the construction of a Checkers application. To name but very few similarities, the presentation layer is analogous and storage of any game state is identical. , it is valuable to bear in mind that maintenance and extensions could potentially be carried out by other game programmers. The documentation for this application, as it was specified in subsection 6, should practically serve its purpose here. 7 Time Management 7.1 Project Development For a Gantt chart, see appendix A. The following describes the preferred completion dates and does not exclude the possibility of a few phases overlapping. These are the 'ideal dates', but there is still time to accommodate changes if need be. 1. Readings on game theory and implementation of game playing programs need to be fully completed by the end of week 11. 2. Readings on advanced graphical models and coding them in GLUT must be completed by beginning of semester 2, although more of that could be complemented within the phase of maintenance and extension. 3. Requirement Analysis - to be completed by the end of week 3. 4. Specification - to be completed by the end of week 5. 5. High-level Design - to be completed by the end of week 7. 6. Low-level Design - to be completed by the end of week 11. This will require a great deal of work, therefore, a month is allocated for that stage. 7. Implementation - to be completed by the beginning of semester 2. Please note that these phase will have begun 2 months earlier (as indicated in the Gantt chart). 8. Testing - to be completed by the end of week 3 of semester 2. 9. Simulation - collection and analysis of data to be completed by the end of week 3 of semester 2. This should not really require more than a few days to complete. 10. Documentation - to be completed by the end of week 4 of semester 2. 11. Maintenance and Extension - to be considered as time allows. Note that the above plan leaves a few weeks vacant until the demonstration. This is, in principal, a safety net that should be used mainly to cover for work on stages 5-7, which are possibly the most crucial ones. Shall any of these stages happen to progress more slowly than anticipated, they should occupy these weeks at the expense of research and extra work (c/f Section 4.2). 7.2 Project Deliverables Throughout the development of the project, as well as after the development is finished, some assessment milestones take place. Excluding this current document, there are 3 such milestones called the project deliverables: 1. Project Seminar 2. Project Demonstration 3. Project Report Two extra milestones are the Project Proposal and Plan and the Final Report Draft. None of these is being assessed. Each of the above will require some preparation time, which varies depending on the extent of the work expected. Appendix B presents the Gantt chart corresponding to these deliverables, which need not overlap with any particular development phases, given that the development is halted before the demonstration and the report are put together. The strict deadlines for these milestones are: * Seminar: 18th-29th November * Final Report Draft: 13th March * Demonstration: 18th March - 2nd April * Final Report: May 7th 8 Deviation from Project Proposal and Plan Inspection of the change in plans, intentions and concepts bears some responsibility and importance. Only by looking at that aspect can we really get a realistic estimate on how often we are likely to change the objectives, the trends and the time constraints within our project. Not very much has been changed since the previous report was put together. The previous report was, in fact, 8 pages long and most changes are strictly additive and are as follows: 1. More information sources have been collected and specified in section 5. Nevertheless, the main topics to be covered have remained the same. 2. A new section, which introduces the background to the game Othello and game-playing programs, has been added. 3. Another Gantt chart for the deliverables has been included. 4. Deliverables have been added to the development Gantt chart as milestones. 5. A new stage in the construction of the system has been introduced - Simulation and Research. 6. A few more secondary objectives have been identified. As the above makes quite apparent, there is no prominent deviation from the original plan. It is rather the case that the plan has evolved into a clearer, more accurate document that describes the requested system. The process of achieving the requested system has not changed; It may have been phrased slightly differently. Guidance on the utility of spare time has been reviewed, however, it has not changed much either. Deadlines and development plan remained as they were before. These have been reviewed, but it is unlikely that any change to them will be required, unless the project takes a sharp turn or its main objectives are altered. 9 Summary The project that aims to implement Othello will require the use of different sources, many of which have been read and covered already. The system should shortly start being built and assembled with respect to the above deadlines. The project is to be completed some reasonably long time before the easter vacation begins, although in a worst scenario case, some more time might be allocated for system design and coding. 10 Appendices See the following pages.