| Neat! This was fun to think about. Given the complete lack of relationship between the two matrices, the fact that you're playing against a computer seems immaterial. You make a move, and then a random square is filled in. You lose if you don't achieve the win condition in some number of turns (I wanna say around n^2/2). That said, here's a greedy algorithm I've arrived at, similar (but not identical to) ronaldx's: For an unfilled point p on an unfinished line, define its value, v(p). There are a bunch of ways to do this, but one that I've thought of is: the number of x's on all unfinished lines through that point. 1. Fill in the center square 2. Choose an unfinished line with a maximal number of x's such that the sum of the values of all its unfilled points is /maximal/ 3. Fill in a point p on that line with v(p) /minimal/ 4. Goto: step 2 Reasoning for step 1: The center space opens up the most options, lying on more lines than any other point. Reasoning for step 2: You want to pick a line to fill in. Moreover, you want the filling in of its points to benefit your efforts elsewhere as much as possible. Reasoning for step 3: Now that you've picked a line, you're going to fill in all its points. You pick the points in ascending order of value to give the robot as much time as possible to fill in the best points for you. |