For this project, I aimed to program a strategic game between a human player and an AI agent. Besides the template and overall rules, the primary task that I intended to achieve was to employ an AI agent with some degree of intelligence to make the game more challenging for the user interacting with the program. For this task, Firstly, I sought to understand how humans play this game and what are their strategies to win the game. Then I attempted to implement these strategies step by step to utilize the AI agent. I was able to implement an AI agent that keeps track of its previous actions’ consequences and uses this memory to limit its future decisions.
Firstly, in the gameplay, two different instances of the Person class are created. One of the instances is of the AI type and the other is from the Human class type. Two classes AI and Human are inherited from the Person class. These classes use and have access to the protected member variables of the Person class. These variables include one Board, five Ship, one Boolean ‘won_status’ variable, and also public methods such as ‘create_boards’, ’enter_ships’, ‘Activate_bombs’, ‘won_status_getter’, ‘enter_a_ship’. After ‘ai_player’ and ‘human_player’ are instantiated, a board will be created for both players using the ‘create_boards’ function. This function embedded in both AI and Human classes, will create boards using the private Board variable of these classes. Firstly, A board class has two Int and one 2d array of a Patch class type. The Patch class is the simplest in the program containing Int ‘height’ and ‘weight’ of 1, ‘val’ and ‘loc’ string variables, and setter/getter methods for each of these variables. The Patch class can also be thought of as a bomb to be detonated later. When creating boards, the Board class makes a 2d array of 10x10 Patches with default value “---”. The value of a patch will change in case it contains a ship or has been used in a (un)successful attack. When displaying boards, a column of letters from A to J and a row of numbers from 1 to 9 will also be printed to help the user navigate and place bombs on a specific patch. The boards are implemented on the terminal using a text-based interface. The Ship class also contains private variables ‘main_patch_loc’, ’ship_direction’, integer ‘size’, and public setter/getter methods. String ‘main_patch_loc’ variable contains the start point location of the ship and, ’ship_direction’ is the direction in which the ship is placed (‘H’ for horizontal and ‘V’ for vertical).
Furthermore, Ships will be placed on the boards using the players’ ’enter_ships’ function. This void function first creates five Ship variables and passes each to the ‘enter_a_ship’ function. This function gets a string ship size variable (e.g. destroyer, submarine) and an integer ship size which specifies how many paths a ship will occupy. If successful it will return a Ship variable that is used to instantiate the specific ship variable of the player. Then for the AI players’ board, the function will ask for a specific location (e.g. A6, J9) and direction (‘H’ or ‘V’) to put a ship. This method also employs an error handling technique in case the user enters an inappropriate location (e.g. A10, wrong direction, or already occupied location). The program will randomly put five ships on the board for the Human class player. The patches that contain (part of) a ship, will have the value “SSS”.
Afterwards, attacking ships starts. For detonating bombs, each player uses a different method with the same function name of ‘Activate_bombs’. For the human player, the program will ask for a specific location to attack. Then the program will enter a loop and check whether the location contains part of a ship. If so, the loop will continue, and the program will print ‘HIT!’ and the updated board of the player. The value of the patch will be changed to “HHH”. The loop will continue until the (next) given location does not contain a (part of) ship or if all the parts of the ship are attacked. For the former system will print ‘MISS!’ and for the latter ‘A SHIP WAS SUNKED!’. Then the board will be displayed. The value of the patch will be changed to “MMM” if missed or “XXX” to show a ship has been sunk.
Then, the other player takes the turn to detonate bombs on their board. However, the AI agent will attack ships differently using a hill-climbing method. Firstly, the AI player creates a board called ‘masked_board’. This is a directory in which the AI agent will put the results of its actions and use it to infer and decide where to attack next. First, the agent will search for a pattern in its masked board. For instance, if it has hit a ship before (e.g. for a ‘H’ patch) in a direction for more than two patches. If so, it will continue the pattern in the same direction until the ship is sunk. If no patterns are found, the agent will look for a single patch it has successfully hit before. In case a patch is found, then it will attack neighboring patches until a patch is hit successfully. This can lead to the agent finding a pattern that will limit its problem space for the next move. However, if the agent cannot find a ‘H’ patch or a pattern of ‘H’ patches, then it will randomly pick a patch to attack. Afterward, the agent will receive from the program the result of its attack. Based on the result, the agent will update that patch as ‘H’ or ‘M’ in its masked board.
If the agent successfully hits a ship, it will be able to attack again until a ship is sunk, or it misses. When the AI agent sinks a ship, it will update the patches in its masked board that contain that ship and change their value to ‘X’. Then again, the human player takes the turn, and the game continues until either side has sunk all the ships and therefore, won the game. In addition, both players check if a ship is sunk using the ‘Sunk_check’ after each attack and turn. This void function receives a ship pointer and updates that ship’s status. This will be used in each iteration of the gameplay’s loop to check all the ships in a player’s boards are sunk. In that case, the player will become the winner of the game, and the program will print which player has won the game. In each iteration, the program shows the player’s (covered) board and how many ships each player has sunk.
As mentioned in the overview, the main task was to understand how humans play this game and to mimic their strategies. However, this led to a challenge since humans have a holistic view compared to the simplistic view of a computer. In simpler words, a human player usually looks at the whole board and decides where to attack. If a pattern is seen, the player will continue that pattern. In contrast, if there is a part of the board that is empty, the human will first try to attack the middle. How to apply this strategy to the AI agent? This challenge was mostly solved using a three-step hill-climbing strategy for AI agents explained in the previous section. One way to fix this issue was to use a (solely) probability distribution technique. In this method, the agent will initiate a probability distribution and the probability of areas close to a ‘H’ path would be higher. However, I did not choose this method as the agent would waste time attacking neighboring patches without looking for patterns. This method would not also work for edge cases such as ships placed on the edges of the board. That is why the third step of the hill-climbing method uses randomness to pick areas not attacked before.
In addition, another challenge was to create robust error handling throughout the program. This is especially true for the parts of the program that get input from the user. For instance, what if the users give the wrong location for ship placement or attacks? What if the AI agent decides to attack a location that it has already attacked? These issues came up during the testing of the game and led to the use of many error-handling cases throughout the program that solved these challenges. However, this also led to higher computational complexity of the game due to an excessive number of ‘if’ conditions used.
Furthermore, two challenges could not be solved during this project. Firstly, after a ship is sunk, the program does not mention which specific type of ship is sunk. The second issue arises when the human player attacks a position that has already been attacked before. In this case, the game will not get crashed. However, the program does not warn and does not ask the human player for another location. Then the AI agent will take the turn to attack. These two issues arise due to the nature of the code and the logic behind the program. For example, adding a “name” variable to the Ship class can be a solution to the former issue. Using a position-checking function and a while loop can solve the latter. These can be applied to future works and improvements.
For future work, the game can be improved by adding a probability distribution alongside the current hill-climbing technique. Also, as mentioned, avoiding error handling has led to excessive amounts of code. This can be fixed by using other methods for some parts of the program. For instance, using a 2d array for boards led to checking whether a given position does not exceed the boundaries of the array; e.g. A10 can be interpreted as A1 if not handled (Appendix D). Moreover, using a GUI would be another improvement over the current game. Keeping track of each move using a text-based terminal interface can be overwhelming and needs numerous amounts of scrolling.