I ended up using the UCT (MCTS with UCB1) algorithm but with a twist.
Normally, in UCT, the simulation phase is a simulated play-through of a game with moves chosen at random. If the simulated game ends in a win, the node's score, from where the simulation was played out, and all it's parents' scores all the way back to the root, are incremented by 1.
In my implementation, the simulated "play-through" is actually just a random walk down the tree of neighboring tiles that haven't been visited yet. Once the simulation reaches a terminal-node (dead-end) it assigns a score of s = d / m where d is the terminal node's depth in the tree and m is the maximum possible depth.
On a 15 x 15 grid with no obstacles, you would set m to 225 as the longest path would visit every tile. I've set mine slightly lower than that as I need the algorithm to be generalized and work on randomly generated maps that usually have 10-30 tiles occupied by obstacles.
Instead of incrementing the parents' score, the backtracking algorithm sets each parent's score to the newly computed score, if it is higher than their current score. In other words, a node's score always represents the length of the longest path reached so far from this node.
UCT uses UCB1 in order to select which node to exploit or explore once every children of the current node have been expanded and I have largely kept with that. The only modification I have made is to the exploitation term. In UCB1, the exploitation term is w / v where w is the node's accumulated score and v is the number of time the node was visited. This works great in a game where you want to select the move that maximizes your chances of winning. In my case, since the score reflects not a binary function of win = 1 and lose = 0 but rather a scale of 0 = super short path vs 1 = the longest path possible and I want to go down the longest path found by the algorithm, I have simply set the exploitation term to s = score = longest path reachable from this node.
The context in which I'm using this algorithm allows me about 40 ms of compute time in a NodeJS environment before I have to select a move. This usually affords around 785 tree traversals on my machine. On average, in that time, and on the map showed in OP, this algorithm will find a path that is 70 nodes deep. Which is more than enough for my purposes seeing as I get to run the algorithm again the next turn. In practice, when using this algorithm to select next moves, I end up travelling a path that is 100-110 steps long before hitting a dead-end and I cover a very large portion of the blue tiles.
For fun I have ran the algorithm for much longer and at around 300 000 traversals (30 secs on my machine), on average, again on the map shown in OP, it finds a path that is 125 nodes deep which is pretty close to the max depth on this map.
