Booth Id:
ROBO051T
Category:
Robotics and Intelligent Machines
Year:
2018
Finalist Names:
Hayes, Nathan (School: Northern High School)
Kong, Jim (School: Northern High School)
Longsworth, William (School: Northern High School)
Abstract:
There is, as of now, no objective method of measuring the difficulty of a given problem. Since biological brains are too generalized, however, a substitute becomes necessary for experimental purposes. To this end we utilized neural networks, mathematical models for learning processes involved in specific tasks. Using these networks, we defined relative difficulty as Problem A being of equal or greater difficulty than Problem B if all neural networks that can be trained to solve Problem B can also solve Problem A. This definition was used to determine an objective measure of problem difficulty based on network dimensions.
Othello puzzles served as the test problems for our genetically-learning neural networks. Populations of networks were trained to solve our sample puzzles; once they achieved a 100% win rate, we noted the dimensions of the successful networks. These were then compared to other networks of different sizes and used to analyze the relationship between the dimensions of the neural networks and the difficulty of problems they could solve.
Simpler networks, when their weights are not tuned to immediately solve a problem at initialization, lack the learning potentials of more complex ones, as indicated by our networks of smaller dimensions being unable to consistently discover solutions to certain multi-step Othello puzzles. Due to this correlation between problem-solving capacity and network dimensions, successful networks that can be said to be minimally broad and deep can be used to compare the difficulty of a problem relative to others.
Awards Won:
National Security Agency Research Directorate : Second Place Award "Mathematics"$750