Team: 87
School: Media Arts Charter School
Area of Science: Math/Statistics
Interim: Problem Definition:
A search algorithm is used to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values(Wikipedia) . Search algorithms can be used in several different ways. One of the few important jobs search algorithms can do is how you could utilize search patterns to find missing/hidden things in our everyday life. There are numerous ways a search pattern can be used. By optimizing a search pattern, we can increase the effectiveness of finding missing/hidden things.
Problem Solution:
By using the game Battleship as an example of utilizing a search pattern, we can find the efficiency of how it finds the hidden ships, by using the program NetLogo to determine the percentage based off of the number of ships hit divided by the number of shots it took to find all ships which is seventeen total tiles. By using multiple references to strategies on how people win the game, we can optimize an ideal search pattern, to help make a more efficient way of searching for the hidden ships. To summarize, Our program will play the game Battleship, where our shots are controlled by several types of search algorithms. Our team’s main goal is to create an optimal search algorithm that raises efficiency in finding the ships.
Current Progress:
After doing some research and testing out the Battleship game, I started the code prior to a couple months ago by using the program NetLogo. So far, I have created the board layout, the ships, the efficiency percentage and the random shots. The board was created first by asking patches to set the background to a blue color to represent it like the Battleship game. The ships were made by asking if there isn't a current existing ship on the board, and there isn’t any duplicates of the current ship being placed, place it on a random coordinate where a ship doesn't exist as long as it doesn’t exceed boundaries. I was also able to determine efficiency by taking the number of shots it took, dividing it by the number of total ship tiles there are in which this case is seventeen for the ships. So far, I am planning to look up more strategies, and furthermore optimize a search pattern to make it easier to look for ships, as well as optimizing the code to finding the neighboring ships, as it is not as efficient as we want it to be, because it doesn’t know yet when to end the neighboring search.
Expected Outcome:
The expected outcome that I have is, the search pattern would have an efficiency around twenty five to thirty percent. My reasoning for this is because the current search pattern I have is based off of a random search pattern, so it significantly lowers the search efficiency by a lot, because it is unorganized. I also have a neighbor search pattern if a ship was hit, but it is currently in the works, because I will need to code the function where it needs to stop if the whole ship has been sunken. The results of running the test a hundred times previously was about twenty three percent, so I believe if I can optimize an organized search pattern instead of holding a random search pattern, and optimize the neighbor search pattern, I believe the efficiency will significantly rise on finding the ships
Citations:
https://en.wikipedia.org/wiki/Search_algorithm
http://www.slate.com/blogs/browbeat/2012/05/16/_battleship_how_to_win_the_classic_board_game_every_time.html
http://www.datagenetics.com/blog/december32011/
http://www.ultrabattleship.com/tips.php
https://www.thesprucecrafts.com/how-to-win-at-battleship-411068
Team Members:
Sponsoring Teacher: Creighton Edington