Let's Play Hide and Seek! The user will hide, and the computer will try to find them.

First, the program will take an input, for the size of the grid. Like 5x5, 10x10, 15x15, etc. The grid won't always be a perfect square.

The grid is sort of like a chessboard:

_______________________________
|     |     |     |     |     |
| A1  |     |     |     |     | A
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     | B2  |     |     |     | B
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     | C3  |     |     | C
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     | D4  |     | D
|_____|_____|_____|_____|_____|
|     |     |     |     |     |
|     |     |     |     | E5  | E
|_____|_____|_____|_____|_____|
   1     2     3     4     5


Now, the user will pick a square, such as B2 (without telling the computer)

The computer will start guessing squares. If it picks the correct square, the user will respond with y. If not, they will input the direction their tile is from the one picked (N, NE, E, SE, S, SW, W).

So if the user picked B2, and the computer guessed C3, the user would input NW.

Here is an example of the outputs and inputs:

Grid?
5x5

C3?
NW

C2?
N

B2?
y


Scoring:

This will be scored a little differently than a normal challenge.

The winner is the program that takes lowest number of guesses  (on average) it takes to guess the correct square. The test cases to be averaged will be all of the possible squares in a 5x5 and then in a 10x10.

However, it must also work with every pattern of grid up to 26 rows (i.e. 5x8, 6x2, 20x5, etc.).

Please include a way for it to be tested, such as a JSFiddle.

And lastly, in case of a tie, the shortest program wins.
Python 3.6, 466 398 392 bytes, minimax



x, y = 1, 1
w, h = [int(x) for x in input('Grid?\n').split('x')]


def split_factor(a, b):
    N = b-y
    W = a-x
    S = h+~N
    E = w+~W
    return max(1, N, W, S, E, N*W, S*W, S*E, N*E)


def move(a, b):
    *Z, = zip([a, x, a, a+1, x, x, a+1, a+1],
              [y, b, b+1, b, y, b+1, b+1, y],
              [1, a-x, 1, w+x+~a, a-x, a-x, w+x+~a, w+x+~a],
              [b-y, 1, h+y+~b, 1, b-y, h+y+~b, h+y+~b, b-y])
    return Z[['N', 'W', 'S', 'E', 'NW', 'SW', 'SE', 'NE'].index(d)]

d = ''
while d != 'y':
    print()
    splits = {(a, b): split_factor(a, b) for a in range(x, x+w) for b in range(y, y+h)}
    a, b = min(splits, key=splits.get)
    d = input(f'{a}{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"[b]}?\n')
    x, y, w, h = move(a, b)


Input and output should be in the form shown in the example. This finds the square with the minimal "split factor"--which is the largest remaining area that can result from the player's answer (i.e. NW, E, y, etc.)--and guesses that. Yes, that's always the center of the remaining area in this game, but this technique of minimizing the worst-case will work more generally in similar games with different rules.

Unreadable version:

x=y=d=1
w,h=map(int,input('Grid?\n').split('x'))
while d!='y':print();s={(a,b):max(b-y,h+y+~b)*max(w+x+~a,a-x)for a in range(x,x+w)for b in range(y,y+h)};a,b=min(s,key=s.get);d=input(f'{a}{chr(64+b)}?\n');*z,=zip([a+1,x,a+1,x,a,a,a+1,x],[b+1,b+1,y,y,b+1,y,b,b],[w+x+~a,a-x,w+x+~a,a-x,1,1,w+x+~a,a-x],[h+y+~b,h+y+~b,b-y,b-y,h+y+~b,b-y,1,1]);x,y,w,h=z[~'WENS'.find(d)or-'NWNESWSE'.find(d)//2-5]