1,105,644 Community Members

Unbeatable Tic-Tac_Toe

Member Avatar
Reputation Points: 783 [?]
Q&As Helped to Solve: 836 [?]
Skill Endorsements: 12 [?]
 
5
 

From a thread on another forum, I wondered how difficult it would be to create a Tic-Tac-Toe game that could not be beaten. Since it is easiest if the computer goes first and chooses the center square, this code implements that portion. The logic is fairly simple; occupy the center square as that removes both diagonals and both middle options for the opponent. Then choose a corner square since it removes two of the remaining options, leaving two only. Before every move, check for two in a row that can lead to a win or a block of the opponent. I suppose it could be improved a little and pick a square where there are 3 that are not occupied, and so a possible win, but this is all the time I have for now.

from Tkinter import *
import tkMessageBox
from functools import partial

class TicTacToe:
    def __init__(self, top):
        self.top = top
        self.top.geometry("108x117+20+20")
        self.button_dic = {}     ## pointer to buttons and StringVar()
        self.X_O_dict = {"X":[], "O":[]}  ## list of "X" and "O" moves
        self.top.title('Buttons TicTacToe Test')
        self.top_frame = Frame(self.top, width =500, height=500)
        self.top_frame.grid(row=0, column=1)
        self.next_player=BooleanVar()
        self.moves=0        ## incremented for each move
        self.buttons()

        exit = Button(self.top_frame, text='Exit', \
               command=self.stop).grid(row=10,column=0, columnspan=5)

        self.player = True   ## True = "X", False = "O"
        self.next_player.set(self.player) ## tk boolean to signal move has been made

        ctr=0
        while (len(self.X_O_dict["X"]) + len(self.X_O_dict["O"]) < 9):
            self.moves += 1
            ## "ret" is not used and is just to signal a return from the function
            ret=self.selection()

        if self.moves:     ## set to zero if there is a winner
            self.is_tie()

    ##-------------------------------------------------------------------
    def buttons(self):
        """ create 9 buttons, a 3x3 grid
        """
        b_row=1
        b_col=0
        for j in range(1, 10):
            sv=StringVar()
            sv.set(j)
            b = Button(self.top_frame, textvariable=sv, \
                       command=partial(self.cb_handler, j), bg='white')
            b.grid(row=b_row, column=b_col)
            self.button_dic[j]=[sv, b]

            b_col += 1
            if b_col > 2:
                b_col = 0
                b_row += 1

        exitb = Button(self.top_frame, text='Exit', \
                command=self.stop).grid(row=10,column=0, columnspan=5)

    ##----------------------------------------------------------------
    def cb_handler(self, square_number):
        if self.player:                       ## True = "X", False = "O"
            this_player = "X"
        else:
            this_player = "O"

        ##--- square not already occupied
        if self.legal_move(square_number):

            ## change button's text to "X" or "O"
            self.button_dic[square_number][0].set(this_player)
            self.X_O_dict[this_player].append(square_number)

            ## set background to occupied color
            self.button_dic[square_number][1].config(bg="lightgray")

            self.check_for_winner(self.X_O_dict[this_player])
            self.player = not self.player
            self.next_player.set(self.player)
        else:
            print "Occupied, pick another"

    ##----------------------------------------------------------------
    def check_for_winner( self, list_in):
        winner_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9], \
                       [1, 4, 7], [2, 5, 8], [3, 6, 9], \
                       [1, 5, 9], [3, 5, 7]]
        for winner in winner_list:
            if set(winner).issubset(set(list_in)):
                if self.player:     ## True = "X", False = "O"
                    self.display_msg("Winner is X")
                else:
                    self.display_msg("Winner is O")

    ##----------------------------------------------------------------
    def check_two_in_a_row(self):
        """ check for two, but not three, in a row
              if player="X", move to win
              if player="O", move to block
            one check for either strategy
        """
        two_row=(set([1,2,3]), set([4,5,6]), set([7,8,9]), \
                 set([1,4,7]), set([2,5,8]), set([3,6,9]), \
                 set([1,5,9]), set([3,5,7]), \
                 set([1,2,4]), set([2,3,6]), set([4,7,8]), set([6,8,9]))

        ## check to win first and then to block
        for player in ["X", "O"]:
            this_list = self.X_O_dict[player]
            for sub_set in two_row:
                ctr=0
                not_in = []
                for square in sub_set:
                    if square in this_list:
                        ctr += 1      ## number occupied
                    else:
                        not_in.append(square)
                ## if two squares only are occupied, and the third is not
                ## occupied by the opponent
                if (ctr == 2) and (self.legal_move(not_in[0])):
                    return not_in   ## = move to be made
        return []

    ##----------------------------------------------------------------
    def display_msg(self, msg):
        tl=Toplevel(self.top, takefocus=True)
        tl.geometry("75x50+30+60")
        lb=Label(tl, text=msg)
        lb.grid()
        self.top.after(3000, self.stop)

    ##----------------------------------------------------------------
    def is_tie(self):
        self.display_msg("...It's A TIE.....")

    ##-------------------------------------------------------------------
    def legal_move(self, square_number):
        if square_number not in self.X_O_dict["X"] and \
           square_number not in self.X_O_dict["O"]:
            return True

        return False

    ##----------------------------------------------------------------
    def selection(self):
        if self.player:     ## computer moves
            ## don't accept button clicks when it is computer's (X) turn
            for but in self.button_dic:
                self.button_dic[but][1].state=DISABLED

            move_list=self.check_two_in_a_row()
            if len(move_list):     ## move to win or block
                self.cb_handler(move_list[0])
                return 1

            ## sequence = middle square, and then each corner as the
            ## 2 middle rows are elmininated by the middle square
            start_set=(5, 1, 3, 7, 9, 2, 4, 6, 8)
            ret=False
            ctr = 0
            while not ret and ctr < 9:
                ret=self.legal_move(start_set[ctr])
                if ret:
                    self.cb_handler(start_set[ctr])
                ctr+=1

        else:     ## person moves
            ## set buttons back to normal
            for but in self.button_dic:
                self.button_dic[but][1].state=NORMAL
            self.top.wait_variable(self.next_player)
        return 1

    ##----------------------------------------------------------------
    def stop(self):
        ## clear any wait_variable
        self.next_player.set(False)
        self.next_player.set(True)
        self.moves=0

        ## a hack to get around the "len(self.X_O_dict" while() loop continuing
        for ctr in range(10):
            self.X_O_dict["X"].append(ctr)

        self.top.destroy()
        self.top.quit()

##===================================================================
root = Tk()
BT=TicTacToe(root)
root.mainloop()
Member Avatar
pyTony
pyMod
6,104 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

Thanks for sharing your knowledge, our dear brother wooeee (even you do not accept friendship requests).

However I do not like those \
line continuations. They are not needed when you have parenthesis available, which have automatic continuation. Don't like those separarator comments so much either.

Also I think that two quit buttons is little too much. So here is result of my experimenting of your code and making it pyTonyc. I took out some index based looping and used set operations for two in row. I used global list of sets for winners, same for two in line.

I googled on the wait_variable hang up. Finally I ended up try...except way with extranous stop. I added random start with instruction toplevel at beginning. But this version leaves ghosts processes behind from IDLE, so better use it from command line or double click. The algorithm should consider empty line preferable over one with opponents piece, but with correct play that winning chance is anyway blocked with opponent. Basically game will always end with tie with correct play.


The timer quit was fun novelty, but I took it out. User can close the window by himself at end of game.

This is little too trivial game, extend game to gomoku, and things would get interesting (http://flibuste.net/libre/morpyon/)

""" pyTonyc version of wooeee's code for Daniweb """
from Tkinter import *
import tkMessageBox

import random
from functools import partial

textsize = 24
class TicTacToe(object):
    winners = ({1, 2, 3}, {4, 5, 6}, {7, 8, 9},
                    {1, 4, 7}, {2, 5, 8}, {3, 6, 9},
                    {1, 5, 9}, {3, 5, 7})

    def __init__(self, top):
        self.player = bool(random.randint(0,1))   ## True = "X", False = "O"
        self.display(('I start with X.\nYou have O.' if self.player
                     else 'You start with O.\nI have X.') +
                     '\nClose this window to start the game!\n')

        self.button_dic = {}     ## pointer to buttons and StringVar()
        self.top = top
        self.top.geometry("240x240+20+20")
        self.top.wm_attributes('-topmost', True)

        self.X_O_dict = {"X":[], "O":[]}  ## list of "X" and "O" moves
        self.top.title('Buttons TicTacToe Test')
        self.top_frame = Frame(self.top, width=500, height=500)
        self.top_frame.grid(row=0, column=1)
        self.next_player=BooleanVar()
        
        self.buttons()
        
        # tie if moves finish
        self.tie = True
        self.moves = 0
        self.next_player.set(self.player)


    def play(self):
        while self.moves < 9 and self.tie:
            self.selection()
        try:
            self.stop()
        except TclError:
            pass

    def buttons(self):
        """ create 9 buttons, a 3x3 grid
        """
        b_row=1
        b_col=0
        for j in range(1, 10):
            sv=StringVar()
            sv.set(j)
            b = Button(self.top_frame, textvariable=sv, font=('Arial', textsize),
                       command=partial(self.cb_handler, j), bg='white')
            b.grid(row=b_row, column=b_col)
            self.button_dic[j]=[sv, b]

            b_col += 1
            if b_col > 2:
                b_col = 0
                b_row += 1
        # don't know how to separate from play field using grid
        Button(self.top, text='Exit', font=('Arial', textsize*3/4),
                command=self.stop).grid(row=2,column=1, columnspan=3)


    def stop(self):
        if self.moves == 99:
            # second stop ignored
            return
            
        if not self.tie:
            #self.X_O_dict['X'] = range(10)
            self.display("Winner is O" if self.player else "Winner is X")
        elif self.moves == 9:
            self.display("...It's A TIE....." )
        else:
            self.display("Quitter!")
            self.moves = 99
            self.tie = False

        # unsetting wait events
        self.next_player.set(self.player)

        self.top.destroy()
        #raise SystemExit('Bye, bye')

    def cb_handler(self, square_number):
        this_player = "X" if self.player  else "O"

        ##--- square not already occupied
        if self.legal_move(square_number):

            ## change button's text to "X" or "O"
            self.button_dic[square_number][0].set(this_player)
            self.X_O_dict[this_player].append(square_number)

            ## set background to occupied color
            self.button_dic[square_number][1].config(bg="lightgray")

            self.check_for_winner(self.X_O_dict[this_player])
            self.player = not self.player
            self.next_player.set(self.player)
        else:
            print "Occupied, pick another", square_number

    def check_for_winner( self, list_in):
        set_in = set(list_in)
        if any(winner.issubset(set_in) for winner in self.winners):
            self.tie = False

    def check_two_in_a_row(self):
        """ check for two, but not three, in a row
              if player="X", move to win
              if player="O", move to block
            one check for either strategy
        """

        ## check to win first and then to block
        for player in ["X", "O"]:
            this = set(self.X_O_dict[player])
            for sub_set in self.winners:
                if len(this & sub_set) == 2:
                    one_to_return = next(iter(sub_set - this))
                    # all one of  them legal, then return
                    if self.legal_move(one_to_return):
                        return one_to_return

    def display(self, msg, title='Instructions'):
        tl=Toplevel()
        tl.geometry("350x140+30+60")
        tl.title(title)
        tl.wm_attributes('-topmost', True)
        lb=Label(tl, text=msg, font=('Arial', 16))
        # sorry, but I love pack compared to grid (pyTony)
        lb.pack(fill='both', expand=True)
        tl.lift()
        tl.wait_window()

    def legal_move(self, square_number):
        return (square_number not in self.X_O_dict["X"] and
                   square_number not in self.X_O_dict["O"])

    def selection(self):
        ## computer moves
        if self.player:
            ## don't accept button clicks when it is computer's (X) turn
            for but in self.button_dic:
                self.button_dic[but][1].state=DISABLED

            move_to_take = self.check_two_in_a_row()
            if move_to_take is not None:
                self.cb_handler(move_to_take)
            else:
                ## sequence = middle square, and then each corner as the
                ## 2 middle rows are elmininated by the middle square
                for chosen in (5, 1, 3, 7, 9, 2, 4, 6, 8):
                    if self.legal_move(chosen):
                        self.cb_handler(chosen)
                        break
        else:
            ## person moves, set buttons back to normal
            for but in self.button_dic:
                self.button_dic[but][1].state=NORMAL
            # we can wait variable change, because they are BooleanVars
            self.top.wait_variable(self.next_player)
        self.moves += 1


game = TicTacToe(Tk())
game.play()
print('Finished')
Member Avatar
pyTony
pyMod
6,104 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

Amazingly this looks like your first own thread and code snippet, so congratulations. You are quite uncommon newbie, having joined 30.12.2006. Thanks for sticking around until this historical moment! ;)

Member Avatar
pyTony
pyMod
6,104 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

Your program (and by clean up) does not know to win in the situation human chooses the edge location (Point 1): http://www.wikihow.com/Win-at-Tic-Tac-Toe My clean up, starting human, human can win by using the corner and opposite corner strategy.

I noticed that only by checking winning lines, the game as changed by me, looses, if human plays strategy which needs edge square as response when corner places are available. Your program chooses the edge, I think because of extra 'two_in_line' checks, which I asked you to explain.

Member Avatar
pyTony
pyMod
6,104 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

Winning map, in case of no win chance or block exist from above link:

Attachments TTT_MAP_257.jpg 22.02KB
You
Post:
Start New Discussion
View similar articles that have also been tagged: