StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Tic-Tac-Toe can be solved using a <a href="http://en.wikipedia.org/wiki/Greedy_algorithm" rel="nofollow noreferrer">greedy algorithm</a> and doesn't really require a decision tree.</p> <p>If you want to continue using your current algorithm, do as patros suggests, and minimize the possibility of losing at each decision.</p> <p>If you want a simpler approach have the AI do the following each turn:</p> <ol> <li>Complete a winning Tic-Tac-Toe if possible.</li> <li>Block an opposing Tic-Tac-Toe if possible.</li> <li><p>Rate each square for its desirability, for each other taken square (by the AI) on a line, add one point of desirability for that square. For each square taken by the opponent, remove one point of desirability.</p> <p>For example, if the board is currently:</p> <pre><code>_|O|X _|X|_ O| | </code></pre> <p>The top-left corner has a desirability of 0 (1 for the X in the same row, and 1 for the X in the diagonal, but -1 for each of the Os).</p></li> <li><p>Play on the most desirable square. Breaking ties arbitrarily.</p> <p>In the example from above, the AI would choose the mid-right square, since it has a desirability of 2, which would lead to a win the following turn.</p></li> <li><p>If the game has just begun, play the center square, if the center square is taken, choose a corner at random.</p></li> <li>Win (or tie).</li> </ol> <p>This was my grade 10 Visual Basic term project. It's impossible to beat and requires far less memory than storing a decision tree.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload