On the Internet since 2004 there is a game "Bug". This is in russian, but you can use the google translator for translate all page, or ask me if there is something that is not clear after translation.
Goal of game — build a correct labyrinth 19 x 29 for bug. Result — number of bug's movements from start point to finish point. The results on the site are sorted by the amount of movement of the bug for the passage of the labyrinth. Algorithm of bug's movement:
Bug always starts movement from the upper left corner, and the exit is always in the lower right corner. The bug is not moving optimally, but in the following way: he goes to where he was not yet, or was there less often. Passing every cell of the labyrinth, the beetle remembers: how many times he was in this cell and when thinking about the direction of his movement at some particular moment he looks: how many times he was in the cell from down side, how many from the right side, how many on the left and how much from up side and moves to where he was fewer times. If there are several such directions and one of them equal with the current direction of the movement, bug does not change direction, otherwise bug moves according to the following priorities: down, right, up, left. Example: if the minimum number of visits immediately to the right and left (but bug is moving up or down), the bug goes to the right, because the "right" priority is higher.
The site has a table of records for all the labyrinths, in which the user is specified and the result of the bug's passing through its most difficult for bug labyrinth. I'm there, 5 th place with 10 million moves. By the way, the winner received 250 million moves quite recently.
For 14 years of work, no good upper bounds were obtained for the maximum possible number of steps of the bug, and no algorithm for constructing the worst test was obtained.
Those interested are invited to play the game "Bug", to generate labyrinths and research this algorithm. Perhaps, it will be possible to shift the leaders from their pedestal. Maybe you can create english version of this game.
UPD: For speed up bug on the site for test your labyrinth you can open google chrome console on F12 and set speed = 1/512. To register a record, you do not have to wait. Just click on 'save' button and your result will be sent on server.
Honestly I was looking for a "Connect Four" meme when I saw the title
Do all labyrinths need to be 19 x 29?
Yes, all labyrinths in this contest need to be a (1 + 29 + 1) in width and (1 + 19 + 1) in height. (I added 1 for borders)