The problem with the task is that you can demonstrate decrementing counters, recursive functions, and familiarity with the language, but if you don't solve the specified problem in a constrained timeframe, you fail. (My feedback was basically "You clearly know how to code, but you didn't solve the problem.")
One of the problems with the Tic-Tac-Toe AI scenario is that you have to figure out an algorithm to win at Tic-Tac-Toe. (If I recall correctly, one of the requirements is that it beats you.) I know how to play -- but to win every time? I'd have to formalize an algorithm, then convert it into working code, within a strict time limit with someone watching over my shoulder. I can do it, but probably not in 30 minutes. It'd take me 30 minutes to set up my 2D array and accept input to populate the board.
That's not how my day job works. That's not how any programming job works.
When I get a problem at my day job, I know the entire domain. I know who my customers are, I know the problems they have. If my day job were Tic-Tac-Toe, I'd know everything there is to know about how to play and win, and then it's a formality to convert that into code.
If you really want to go with the coding exercise thing, you can't focus on the "right answer." Whether their tic-tac-toe program wins every time is irrelevant. What's relevant is that they jump straight to the notion of a 2D array, that they know how to do recursion or for-loops. What's relevant is that they can write code without too many syntax errors, that they're comfortable, and that they make progress throughout the time alotted. Whether they actually cross the finish line is irrelevant at best. It's a red herring.
In the end, do you want to know if I can code, or do you want to know if I can write a winning Tic-Tac-Toe algorithm in 30 minutes? Those are two different answers -- just because I can't do the latter doesn't mean I'm not qualified. I just means I didn't pass your test.