• Author / Uploaded
• Bermet Kerim Kyzy

Citation preview

Introduction Tic-Tac-Toe is one of the simplest forms of two person games. As it is widely known, in a board made of equal number if rows and columns the player in order to win an opponent has to create an entire row, column or diagonal consisting of the same entries first. Traditionally game is played with crosses (X) and noughts (O). The combinatorial game theory proves that conventionally player which makes the first move has higher chances for win, however most of the games played in end up with a draw, which made this game uninteresting tool for research (Beck, 2008). The objective of this report is to present information about the simulation of Tic-Tac-Toe game using MATLAB. Objectives and constraints set for the project were as follows:    

Computer, i.e. program, should be capable of choosing sign it plays for the whole game Computer should try to win the game Output could be done in any form, however it is preferable to make a user-friendly environment Program should not cheat and should be able to determine user’s attempts for cheating Solutions and Ideas developed:





 

As the computer starts the game it has more chances for win, therefore as first two cells are already occupied by X and O to choose sign for which the computer will play it has simply to count number of rows, columns or diagonals it can occupy and by comparison decide whether it wants to play for X or O. It is apparent that computer should choose the sign which is already on one of the corners or central cells. As the most expected outcome of the game is draw, goal of the computer simplifies to “not allow the player to win” by blocking any attempts to do so and bringing victory in case of strategy errors of the player. Graphical representation of the board was decided to be the most effective, as the player would be able to see the process and this would be the closest approximation to a real game mode. Using graphs to output the results also allows to make minimum cheating analysis because player cannot affect the program itself, thus the only cheating analysis required is check that cell player or computer wants to occupy is empty. Theory The strategy of the game was developed with assumption that player also wants to win, thus the main aim of the computer to win transforms to a simple idea of not giving player chance to beat the program. Therefore, mostly computer will be blocking attempts of the player to win and attack if player takes the defensive strategy. This logic of the game play should allow bringing the game to the draw result. As the computer is allowed to make the first move it has an advantage of choosing beneficial sign and according to the combinatorial game theory player who makes first move has better chances for win (Beck, 2008). As the program developed is a simulation or real-life game the aim was to make it user-friendly. Graphical user interface is the type of interface which will allow user to communicate with computer via graphical objects not text or direct intervention to the work of the program. Using menu toolbar will allow the player to output information to the user and input data about his choice.

Another problem of the GUI was to make a user-friendly output of the playing board. The simple idea of using plots and using image of the grid as background allowed to present player matrix in graphical form. Several MATLAB functions and logical were used in code. The most notable functions and commands used are presented in Table 1 and Table 2 (Source: Mathworks, 2012; Moore, 2011). MATLAB command How it works menu Generate menu of choices for user input switch Switch among several cases based on expression imread Read image from graphics file imagesc Scale data and display image object plot 2-D line plot pause Pause job manager queue fliplr Flip matrix left to right diag Diagonal matrices and diagonals of matrix Table 1. Main commands used in the code. if/elseif/else for while

Execute statements if condition is true Repetition of certain certain command Repeatedly execute statements while condition is true

Table 2. Main loops and logicals used in code.

Results and discussion As the result a program which fully simulates the game play of Tic-Tac-Toe was obtained. From a given 4 by 4 matrix program outputs user playing board given on Figure 1. To start the game user has to run script run_game (see Appendix 1).

The program made has several specifications and capabilities: 

Choice of the sign of play according to the chances for win by comparison of lines program can occupy playing for cross (X) or nought (O) (see Appendix 2). Obviously, it becomes apparent that diagonal cells allow user to occupy 3 lines, while placing sign at other cells give only 2 lines at most.











Program can read input data about user’s row/column and output information on the playing board as it is shown on Figure 1 and Figure 2 (see Appendix 3). After user has made move it was needed to make an integration of the playing board with main matrix. This was done by changing values in matrix Board1_new. The main problem that arose during integration process was mismatch in the row number in playing board and in matrix, i.e. row 1 on the board is row 4 in matrix. The problem was eliminated by subtracting row number from 5 in order to get correct matrix row. After user’s turn program makes its move. Program’s game strategy should allow it to get draw result and to win in the case of players’ intentional losing moves. It puts fourth sign in a line to complete it and win if three are already in line; program blocks player starting with 2 of his sign if no line satisfies two previous conditions; further it tries to block a line which has one of the user’s sign and intersecting line which contains one of its sign. However, it is worse to note that as the program mostly takes defensive role, if player does not attack computer takes the first line that satisfies requirements of the strategy, thus it cannot evaluate cells that are appropriate but simply puts on the line that is first (see Appendix 4). Thus program chances for win are small, but it always brings to a strong draw. Program can identify the results of the game: either computer wins or player or draw result (Figure 3). Check for winner occurs after each computer’s move and player’s move starting from the third move, because after third move theoretically one of the players could already achieve win. Computer displays “draw” starting from the moment when none of the players has opportunity to achieve victory. In order to identify whether draw occurs or not, program simply reads off all 10 lines of matrix and if each line contains at least one player’s sign and one computer sign than playing the game has no point (see Appendix 5).

Program contains m-files that are capable of counting number of crosses and noughts, signs put by the computer and player and number of empty places left in each line. It fills a beforehand created empty vector with respective number of signs in each of the rows, columns and diagonals (see Appendices 6, 7, 8, 9, 10). Counting is made using similar logics for all 5 scripts and cam be run in any place needed. This counting became a very useful tool in check for winner part of the program, because program counted number of signs put by the player, computer and could evaluate by this which move to make (see Appendix 5, NB 4). Also counting helped to identify the sign computer plays for (see Appendix 1, NB 1; Appendix 2) by counting number of lines each sign can occupy. The line that occupied is the line which contains one sign on it only, thus three others can be put during the game, for example any of the diagonal cells is more beneficial as it allows to occupy three lines. Cheating analysis is the crucial part of the whole game play. Using graphical output allowed minimizing amount if cheating analysis needed, because player cannot interfere into the work of the program and has to choose only rows and columns to put his sign. In addition, he has choice out of four different rows and columns thus cheating in this step was also prevented. The only cheating analysis that was to be done as for the computer so for the player was check that none of them takes not empty cell (see



Appendix 3, NB 1; Appendix 4, NB 2). If the player tries to avoid choosing row or column and closes choice window, program cancels running and the game is over. Lastly, when the game is over program offers player to restart the game and try his strength again (see Appendix 1, NB 5). Menu of the game restart is shown on Figure 4.

Recommendations: The program written satisfies all requirements of the assignment, however several drawbacks of the program could be eliminated further and program is feasible for changes and improvements. Advantages the program has:   

User-friendly interface and handy playing windows. Identification of the sign of play on the basis of given initial matrix Strategy of the game that will not allow computer to loose Improvements that could be done:

 







Playing windows appear on the screen separately however using GUI MATLAB commands will allow to present game environment in more convenient form. Computer identifies sign for which it will play according to the two given moves; this causes some problems in case of change of the board or number of given steps. Improvements in the strategy of choosing sign could eliminate this problem and make the program stronger. Computer takes defensive strategy, as the program was written with assumption that player wants to win and will take attacking position. However the weakness of the program is that in case of change of the strategy of player will not actively attack the user. Therefore another improvement that could be done is a game strategy that will allow computer to better analyze playing board and more complicated estimation of probabilities. This will require more sophisticated game strategy and simple generalization may be not sufficient. The main inconveniency of the game is that user has to count rows from the bottom. This causes no troubles with the program and requires no additional efforts from the player, however elimination of this problem will make program slightly easier. Game stops as player closes one of the playing windows, this was used as a part of cheating analysis, however to improve program code could be rewritten in such a way that there would be additional condition for closing the window and if this was done occasionally player will have chance to return to the game. Conclusions In summary, program that simulates Tic-Tac-Toe game was developed using MTALAB. The program written allows player to play the game in user-friendly atmosphere and is fully analogous to the real-life game. In accordance with theory game results in draw and allows computer to win in case of errors of the player. The program is fully written by simple MATLAB commands with use of no MATLAB build-in functions. Code demonstrates how a complicated algorithms and sequence of actions could be presented in MATLAB even at the beginner level.

Summary In order to complete the project in time and correctly much effort has to put in this project. The main difficulties were the unusualness of the task, novelty of the software to be used and time given for the project. As it is widely known time management is crucial for any project or submission, person may have great ideas but simply have no time to realize them. That is why from the beginning it was important to plan the work properly and effectively such that my project would ready on time.i have decided to start working on project on 7th week after end of ESD II course, when the timetable will be more feasible and free. In addition, big expectations were set on Project week, however I could start working on the project only after it. Long time given for the project was advantage and disadvantage at the same moment. Knowing that deadline is far makes you to relax and do not care about task to some extent that is why I had to plan my work and stages that I will undergo on the way of completion the task. The following plan was developed:     

Set the problem and identify key features of the task Understand the game and game strategy Search for similar projects and works Develop ideas Write the code and final report

At the first stage the task has to be read carefully and every single key feature of the task understood. Further the game has to be understood in order to know which strategy to develop. I started with playing this game to understand which moves are better in comparison to others. Constant playing helped me to realize that practically every game ends with draw, reading supplementary materials proved that draw occurs in most of the cases even though player who moves first has more chances for win. This helped me to develop my strategy. Then I started searching for similar projects in MATLAB in order to find some ideas that could be helpful; however this search did not bring good results, because most of the projects that were found were complicated and were based on more sophisticated level of programming than required by our task. Thus I had to develop own ideas and methods to complete the task. Reading books helped to find some useful commands and function, for example command fliplr was found occasionally while reading book and when I saw operation it performs I understood that this could be used in project. I started with designing window and start of the game then I had view on how to program the rest of the game and how to make the program to fit into the initial framework. The next stage and the longest one was to write strategy of game play for computer. This strategy had to be non-losing one and at the same moment as general as possible in order to include all possibilities that could occur. Finally, parts of the program that will allow player to make moves, choice of the sign, check for winner and restart of the game had to be written. When the program main parts were ready they had to be adjusted to each other and by the end of the program writing main work was done. One of the main things I have learnt during writing the project is the ability to learn things and apply them even if they go beyond the lecture notes and topics covered during the lectures. To do so consultations with teaching staff helped me significantly to understand the project requirements, some specifications. In addition, some problems with code were also eliminated with their help. Ideas exchange with friends helped to improve the program and come up with new ideas for my game. Also,

project helped me to plan work and time properly, which will help in future when I will have to be engaged in long-term projects. To sum up, this individual coursework was a great challenge and required a lot of effort to be put. In order to complete the task I had to apply communication skills, time management skills and planning skills. Reference List Beck, J., 2008. Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press. Mathworks, 2012. Product Documentation [online]. Available at: http://www.mathworks.com/help [Accessed 18 March 2012]. Moore, H., 2011. MATLAB for Engineers. 3rd ed. Prentice Hall.