[Tutor] Michael Dawson Chapter 6 Challenge 4

[Dave Angel]

On 11/23/2014 07:04 AM, John Feleppa wrote:
> Dear all,
>
> Has anyone solved the fourth challenge in Chapter 6 of Michael Dawson's
> book, 'Python Programming for the absolute beginner'?
>
> The challenge: 'Write a new *computer_move()* function for the Tic-Tac-Toe
> game to plug the hole in the computer's strategy.  See if you can create an
> opponent that is unbeatable!'
>
> The function is as follows:
>
> def computer_move(board, computer, human):
>      """Make computer move."""
>      # make a copy to work with since function will be changing list
>      board = board[:]
> *    # the best positions to have, in order*
> *    BEST_MOVES = (4, 0, 2, 6, 8, 1, 3, 5, 7)*
>
>      print("I shall take square number", end=" ")
>
>      # if computer can win, take that move
>      for move in legal_moves(board):
>          board[move] = computer
>          if winner(board) == computer:
>              print(move)
>              return move
>          # done checking this move, undo it
>          board[move] = EMPTY
>
>      # if human can win, block that move
>      for move in legal_moves(board):
>          board[move] = human
>          if winner(board) == human:
>              print(move)
>              return move
>          # done checkin this move, undo it
>          board[move] = EMPTY
>
>      *# since no one can win on next move, pick best open square*
> *    for move in BEST_MOVES:*
> *        if move in legal_moves(board):*
> *            print(move)*
> *            return move*
>
> I believe a solution lies in the final lines, which I put in bold, and in
> the BEST_MOVES tuple, which is also in bold.  As in, it looks through the
> list of best moves in order regardless of what move the opponent has made.
> So it just dumbly selects the next item in the tuple instead of responding
> to the opponent's move.  So, for example, the following sequence shows the
> computer's weakness:
>
> a. the opponent goes first in a corner, in Square 0
> b. the computer picks the centre, in Square 5
> c. the opponent picks the opposite corner, Square 8
> d. the weakness - the computer picks the corner, Square 2, which will be
> easily countered by the opponent going in Square 6, instead of the smarter
> Square 1, which will result in a draw, and not a loss.
>
> HAS ANYONE SOLVED THIS?  I'd much appreciate help here.
>

I've solved problems similar enough to this one.  Note that once you've 
solved it, the game becomes uninteresting to the other player, as he can 
never win.  Also, every game is repeatable.  To solve these two problems 
it's typical to introduce some randomness and/or some inaccuracy, rather 
than playing perfectly.

A way to greatly improve the odds of winning is to fix the BEST_MOVES 
tuple.  Something like

    BEST_MOVES = (5, 0, 8, 6, 2, 1, 3, 7, 5)

would probably help.

As for a total non-losing strategy, I'd make the function recursive, 
toggling the role of player and computer till there's no choice.  Then 
pick one that the opponent does not win.  Since the total number of 
games isn't that huge, it should be able to iterate through them in a 
reasonable time.  Note that the return value probably should be changed 
to a tuple, indicating who won for a particular call.

If I were then worried about performance, there are many ways to improve 
on it.

-- 
DaveA