tictactoe script - commented - may have pedagogical value

[Ian Kelly]

On Tue, Sep 5, 2017 at 6:15 PM, Stefan Ram <ram at zedat.fu-berlin.de> wrote:
> Ian Kelly <ian.g.kelly at gmail.com> writes:
>>Usually I've seen Tic Tac Toe implemented using the Minimax algorithm
>>since the decision tree for Tic Tac Toe is quite shallow.
>
>   This thread made me want to write a tic-tac-toe game.
>
>   I am naïve in this field. I don't know what "Minimax" is.

http://neverstopbuilding.com/minimax

>   So I just did this: I try to evaluate every possible move
>   and then choose the best one.
>
>   To evaluate a move:
>     If I win with this move: +1
>     If I lose with this move: -1
>     If there are several possible continuations:
>       If this is not a recursive call and one of
>         the possible next moves of the opponent
>         makes me lose: -1
>       Otherwise, return the average of the values
>         of the possible continuations
>     If there is no possible move: None

I didn't read through your code in depth, but it sounds like you
implemented Minimax. We want to maximize our score, and we assume that
on the opponent's turn they will act to minimize our score, so the
goal is to find the highest possible minimum score.

Tic Tac Toe is great for demonstrating Minimax because the entire game
tree is limited to at most 9! = 362880 possible games without doing
any pruning at all. In reality it's fewer because some games end
before 9 moves have been played. That makes it feasible to traverse
the entire tree on an interactive time frame.

For more complex games like Chess it isn't usually feasible to look
all the way ahead to the end of the game, so they have to apply
additional strategies like alpha-beta pruning, stored opening and
endgame books, and incomplete positional evaluation.