GROUP cs20404 RISHI BHARDWAJ 01010118 SOUMADEEP BASU 01010126 PRAVEEN SINGH SAUGAT 01010116 BASIC CODE BEHIND ALL THE ASSIGNMENTS The core code for all the assignments, namely the various structures, functions used for different purposes remain more or less the same with the strategy changing to cater to the specifics of each assignment a)STRUCTURES USED:- 1) COIN represents a coin on the board 2) BOARD represents the whole board, consisting of 21 or 36 coins depending upon the game. 3) MOVE represents a valid move on the board. Consists at maximum 6 coins 4) LINE represents a line consisiting of ordered coins(maximum 6) which picked in the order would represent a valid move. b) FUNCTIONS USED:- 1) THREEPTS This function which handels all the possible cases that could arise when only three coins are left in the board. It also returns an integer which specifies whether you are in a winning position or not and if in winning position then which two coins you should pick to win. This kind of hard coding lessens the burden on recursion and thus improves performance in the long run. When generating the GAME TREE by recursion the program may only go till 3 coins and the rest of the thing this function would handle. 2) POSMOVES This function with the help of functions isaval(isavalaible coin) and extmv(extend move) generates all the possible valid moves for any given board configuration. 3) TRACEMV This funcyion is called by the main function for generating the move to be passed to the arbiter.This function, along with the two inter connected functions 'REC1' and 'REC2' (both function call each other), generates the whole GAME TREE and then returns the move which is the best suited for winning. This function is the starting point of the DEPTH FIRST SEARCH of the GAME TREE for a sure win move or an optimal move(max points). It generates all the possible moves(posmoves) for the program at the first level of the GAME TREE and then calls 'REC2' to make the opponents move and thus starting a real simulation of the whole game. 4) REC1 This function represents the our player for which we have to pass a valid optimal move to the arbiter . When called from 'REC2' it generates all the valid moves on the 'BOARD' passed from 'REC2' , and then goes for a DEPTH FIRST SEARCH passing the control again to 'REC2' for the opponents move. It returns 1 if our player is in a sure win situation and 0 if the opponent is in a sure win situation. 5) REC2 This function is the counterpart of 'REC1'. It represents the opponent player. Just like REC1, it also generates all the possible moves of the opponent for the 'BOARD' passed to it by the function 'TRACEMV' the first time and 'REC1' subsequently. It considers the moves for the opponent one by one by taking a move and passing the control to the 'REC1'. It returns a 1 if the opponent player is in a sure win situation and 0 if the player being represented by 'REC1' is in a sure WIN position. GENERAL STRATEGY ASSIGNMENT 1 The program tries to find the perfect move in a given situation by going in a recursive loop. The recursion process is accompished by three functions namely 'TRACEMV' (short form of trace move), 'REC1'(recursive function acting as our player) and 'REC2' signifying the opponent. The recursion works on the following principle:- At any stage of the game, it generates all the moves possible in that given situation and then 'explores' them one by one( DEPTH FIRST SEARCH) During exploration of a move, the program simulates the whole game, considering that you make that move, and then analysing all the moves the opponent can make and so on. During this process if the program finds a sure win situation then the function REC1 and REC2 exit from their inter connected recursion and the coressponding move is made. A sure win situation arises when for a move made by you, any move your opponent makes leads to your win, provided you make the right(correct) moves at all the stages. Thus by recursive calls we generate all possible moves at a stage exploring them one by one and try to find out if the move considered at the first stage gives us a sure win situation or not. At any point the program generates the whole GAME TREE considering the possible moves left, and as soon as it finds a SURE WINNING move it stops the recursion and the winning move is made. AND IF THERE IS NO WINNING MOVE POSSIBLE THEN THE MOVE WITH THE LOWEST PROBABILITY OF LOSIN IS THE MOVE THAT IS FINALLY MADE. What's interesting is the fact, that during initial testing and experimenting with the program, it became clear that player moving first is in a sure win position. If the player 1 cuts any of the three last lines i.e "1,2,4,7,11,16" or "16,17,18,19,20,21" or "1,3,6,10,15,21" and then goes on playing flawlessly it will always win. "A SMALL FLAW IN THE FIRST ASSIGNMENT PROGRAM ENSURED THAT WE COULD NOT GIVE OUR BEST PERFORMANCE IN THE FIRST ASSIGNMENT, BUT THE FLAW WAS CORRECTED IN THE 2nd ASSIGNMENT AND OPTIMAL PERFORMANCE WAS DONE." AMOUNT OF TIME TAKEN BY PROGRAM FOR A MOVE when the program has the first move, and since the sure win move is already known, the first move is always the same as 16,17,18,19,20,21 and after it a little bit of hard coding(function gofrkill) for the one coin moves which the other program might move ensures that time taken is almost negligible in case the program has the first move. minimum time taken for a move is negligible in most of the cases except when we have the 1st turn and after moving the 6 coin winning move the opponent moves a 2 coin move giving us 13 coins to move from. It takes the maximum time then about 15 - 20 sec. ASSIGNMENT 2 APART from the above strategy used in the 1st assignment the flaw in the 1st program in the hardcoding(GOFRKILL function) was fixed. And a few other things added. The flaw that creeped in the 1st asignment was in the function GOFRKILL. This function was basically hardcoding, and came in use when we had the 1st turn, had moved the sure win move "16,17,18,19,20,21" and then the opponent moved a single coin move. The hard coding in this case ensured a running time of less than a second for most of the situation and 15 - 20 seconds in the worst case when the number of coins for recursion is 13. SECOND THING ADDED In the other case when we have the 2nd move the program checks if the opponent has made the grievous mistake of moving coins from one of the three last lines and not cutting the whole line then if it's possible to cut the other coins left in the last line we will come in a sure win situation. If so then again a li'l bit of hard coding(gofrkill3, gofrkill5 functions) when again if the opponent gives a one coin move after us cutting the whole last line, ensure you win and the time taken is minimum. ASSIGNMENT 3 The MINIMAX strategy is the one used for the assignment 3. At a given point(when it's the program's turn to move) the program generates the whole GAME TREE, where the leaves of the tree represent the outcome of the game a win or a loss and total POINTS scored. In this assignment winning the game was not the aim but to get maximum points gained much more importance. The 6 coin move no longer was the feasible option as it gave -30 in one go. The strategy changed from searching the GAME TREE for a sure win move and stopping there to a strategy where you had to search the whole tree, keep tab of the points you score for each move and finally add the 25 bonus points to the case where you win. Thus you go on Calculating the points you would score in all the cases and then the program, considering the worst possible situation where the opponent('REC2') moves optimaly to give you the minimum points, makes the best possible move. Same way as the earlier two assignments the REC1 and REC2 generate all the moves possible at each stage and explore them one by one resulting in a DEPTH FIRST SEARCH for the move resulting in maximum points. The simulation of the game by the program assumes optimal play by the two players, while the opponent(REC2) tries to minimize the points you gain, the program(REC1) on the other hand tries to maximize the points you make. Thus the final move passed to the arbiter is the one which will result in maximum points in the end in the worst situation when the opponent moves optimaly (perfectly). RUNNING TIME:- Maximum time is taken when no. of coins is 12 - 13 and is the order of 20 sec, while minimum time when coins are less is negligible. ASSIGNMENT 4 For assignment 4 there is a two pronged strategy used. Considering the need for optimization for the 36 coin game a two way strategy was used. The MINIMAX strategy(explained in the above 3 assignment) gives the optimal move in the desired time only when the number of coins are less than 11, while in the other cases you get a time out. To maximize the recursive search for the optimal move to maximum number of coins, we try searching for the sure win move when the number of coins is greater than 10, assuming that winning move will in turn result in if not the maximum number of points then surely in more number of points than otherwise. Since in searching for a sure win move in the GAME TREE you do not have to keep a tab of number of points at each node and the search terminates as soon as you get a solution(unlike in the MINIMAX case when you must search the whole tree for the optimal move), thus the time required for the ALPHA BETA PRUNING of the tree is much less than in the MINIMAX case where you also calculated points being scored by you and were bound to search the whole tree. The time required for searching for the sure win move increases exponentially with the number of coins. Thus the search for the sure win move could also not be extended beyond 14 coins. Again to maximize the search for maximum number of coins, when the number of coins exceeded 14, the number of coins in the first move, during the generation of the GAME TREE was restricted to 3(in case of 15 coins) and 4(in the case of 16 coins), such that the recursive loop for searching the best move could start as early as 16 coins. Then to ensure we got the upper hand in all the games, whenever it was our turn to move and the number of coins were in the range of 17 to 21 we always picked a move which would give the opponent 16 coins to pick a move from. Since we knew that to get the optimal move for 16 coins in the desired time is difficult , and then in such a case the opponent will take the greedy choice(max. point move) which would probably be a four coin move(4 coins give the max points) which in turn would give us 12 coins to move from. Since the opponent took a greedy choice at 16 coins, it is unlikely that the move will be an optimal one, and since we can easily find a sure win move if it exists, in the case of 12 coins remaining, it would be fair to say that we will have a greater probability of winning and hopefully getting more points than our opponent. This strategy worked wonders for our game and we came 1st int the second round and then 2nd the next two rounds, that is excluding the first round when we had some faults in our program and gave wrong moves . TIMING: The maximum time(around 80 sec) is taken is when the coins are in range say 13-14 when it generates the whole GAME TREE , minimum time taken is negligible under a second. ASSIGNMENT 5 In addition to the two pronged strategy being used from the last assignment(MINIMAX and the SURE WIN MOVE) there was also an element of self learning added in the program. By experimenting we saw that it's the move you make when the number. of coins is in range of 18 that decides whether you win or not. Making a recursion for that many no. of coins was a giving a time out So when it's the program's turn of moving and the no. of coins is equal to 18 the program picks 4 coins with maximum points, such that the opponent has 14 coins to pick from. If in the end the program loses after pickingthose 4 coins, next time when the program plays the same player(which it checks by the move's the player is making), it gives a 2 coin move with the maximum point, thus giving the opponent 16 coins to pick from. finally if the program loses even after changing the move at 18 coins from a 4 coin to 2 coin move it changes it to a 3 coin move in the subsequent rounds. TIMING: maximum time taken is when the no. of coins for a move is around 12-13 around 35-40 sec and minimum time is negligible.