# Analyzing movement data for a checkerboard

For a psychology experiment - subject has to learn that the 2D grid is a checkerboard, and collect all the 1s (rewards). How do I test if subjects are actually doing it in the most optimal way -- making least effort for moving from one square to the next by taking smaller steps (or selecting closest reward neighbour). My guess is that if I could simulate a learning algorithm and approximate how long it takes to learn the reward distribution, and then explore it optimally (optimality is defined as a unit of time and exploring closest squares first), I could compare the behaviour.

• It seems like you could also use a pathing algorithm like something based on A* to get an exact right answer so you wouldn't have to worry about your learning algorithm not finding the global minimum. – Alan Wolfe Jun 17 '15 at 2:51

## 1 Answer

If the grid size is large, this becomes unsolvable by a computer, as this is a NP problem.

If your grid is small, you can get a computer to calculate all possibilities, and plan a optimal route. However, as your grid gets larger, your calculations get exponentially larger, to the point where it takes forever for a computer to determine the optimal path required.

To calculate all routes, a solution would be to utilize an A* pathfinding algorithm, to calculate the shortest path required to visit every single node.

You could calculate this by calculating every path possible, and taking the shortest one.