Open Technical Blog: A Framework for Board Games

This is the Part II of a board game Tic-Tac-Tao. In this post, a tree searching algorithm for determining the moves of the computer is presented. With that intelligence, the computer will act like an expert player and can beat all human in theory.

A depth first search (DFS) algorithm is employed.
A scoring scheme is installed to assist the DFS so that the algorithm will choose the path with the highest score to go in order to increase the chance of winning.
The scoring scheme will consider both the computer's moves and the subsequent human's moves during the evaluation.
The scoring scheme will work recursively until it reaches the predefined maximum depth of the tree, or until it has found a way to win, or until it has tried all nodes.
The AI has been tuned not to be so strong, otherwise it will either win or draw in each game. This is achieved by setting its first move by random, and use smaller value (e.g. 3) for the predefined maximum depth.

Source Code

# Title         : Tic-Tac-Tao
#               : computer chooses move by 
#               : thinking n steps ahead
#               : through recursive calls
#               : (depth first search DFS)
# Date          : 13/08/2019
# Version       : 0.4
#
# Remarks:
# 1. Positions for the slots on
#    the board
#      1 | 2 | 3
#     ---|---|----
#      4 | 5 | 6
#     ---|---|----
#      7 | 8 | 9
# 2. human(O), computer(X), free( )
# 3. Rules for wining:
#    [1,2,3],[4,5,6],[7,8,9],[1,4,7],
#    [2,5,8],[3,6,9],[1,5,9],[3,5,7]
#

import random, copy

class players:
    def __init__(self):
        self.freeSlots = range(1,10)
        self.human = []
        self.computer = []
        self.turn = 'c'

def humanMove(self,pMove):
        if pMove in self.freeSlots:
            self.freeSlots.remove(pMove)
            self.human.append(pMove)
            self.turn = 'c'

def computerMove(self,pMove):
        if pMove in self.freeSlots:
            self.freeSlots.remove(pMove)
            self.computer.append(pMove)
            self.turn = 'h'

class boardgame:
    def __init__(self):
        self.icons = [' ','O','X']
        self.players = players()

def printBoard(self):
        mBoard = []
        for mi in range(1,10):
            if mi in self.players.freeSlots:
                mBoard.append(self.icons[0])
            elif mi in self.players.human:
                mBoard.append(self.icons[1])
            else:
                mBoard.append(self.icons[2])
        mr = ''
        mbar = '  ---|---|---\n'
        mr = '   %s | %s | %s\n' % tuple(mBoard[0:3])
        mr += mbar
        mr += '   %s | %s | %s\n' % tuple(mBoard[3:6])
        mr += mbar
        mr += '   %s | %s | %s\n' % tuple(mBoard[6:9])
        print
        print mr

# determine whether the game
    # is ended or not
    # return
    #   d - draw
    #   h - human win
    #   c - computer win
    #   n - not yet ended
    def endGame(self):
        mrules = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],
                  [2,5,8],[3,6,9],[1,5,9],[3,5,7]]
        mret = 'n'
        # determine who win
        for mi in mrules:
            # computer win?
            mrs = set(mi)
            if mrs.issubset(
                set(self.players.computer)):
                mret = 'c'
                break
        if mret == 'n':
            # human win?
            for mi in mrules:
                mrs = set(mi)
                if mrs.issubset(
                    set(self.players.human)):
                    mret = 'h'
                    break
        if mret == 'n':
            # draw?
            if len(self.players.freeSlots)==0:
                mret = 'd'
        return mret

# evaluate the score of a player
# reflecting his current state
# higher scores means better state
#
# pPlayers - current state of the players
def score(pPlayers):
    mrules = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],
              [2,5,8],[3,6,9],[1,5,9],[3,5,7]]
    msc = 0
    mfs = set(pPlayers.freeSlots)
    if pPlayers.turn=='h':
        # the next turn is human
        # => computer just move
        # => score the computer
        mps = set(pPlayers.computer)
    else:
        # the next turn is computer
        # => human just move
        # => score the human
        mps = set(pPlayers.human)
    for mr in mrules:
        # set for a winning rule
        mrs = set(mr)
        mint = mps & mrs # intersection
        if (mrs - mint).issubset(mfs):
            # score for the ith rule
            msc_ri = len(mint)
            if msc_ri==3:
                # ri is a winning rule
                msc = 10
                break
            msc += msc_ri
    return msc

# recursive scoring for a proposed move
# using DFS algorithm
#
# pDepth    - current depth of the search
#             tree
# pMove     - the proposed move
# pPlayers  - current state of players
def a_score(pDepth, pMove, pPlayers):
    if pDepth==0:
        # reach required tree depth
        return 0
    elif len(pPlayers.freeSlots)==0:
        # no more free slots
        return 0
    md = gSearchLevel-pDepth+1
    mreply = '  '*(md-1)
    mreply += 'L%s: %s tries %s' % \
          (md,pPlayers.turn,pMove)
    print mreply
    mscore = 0
    mplayers = copy.deepcopy(pPlayers)
    if mplayers.turn=='c':
        mplayers.computerMove(pMove)
        mscoreComp = score(mplayers)
        if mscoreComp==10:
            # a winning move is found
            mscore = mscoreComp
            return mscore
        # get maximum score for the next
        # move from the human
        mhmax = 0
        for mi in mplayers.freeSlots:
            # try every possible move for
            # the human
            mscoreHuman = a_score(pDepth-1,mi,mplayers)
            if mscoreHuman > mhmax:
                mhmax = mscoreHuman
                #
                # cut the search tree
                # by skipping the rest
                if mhmax==10:
                    break
        # calculate the final recursive score
        mscore = mscoreComp-mhmax
    elif mplayers.turn=='h':
        mplayers.humanMove(pMove)
        mscoreHuman = score(mplayers)
        if mscoreHuman==10:
            # a winning move is found
            mscore = mscoreHuman
            return mscore
        # get maximum score from the next
        # move from the computer
        mcmax = 0
        for mi in mplayers.freeSlots:
            # try every possible move for
            # the computer
            mscoreComp = a_score(pDepth-1,mi,mplayers)
            if mscoreComp > mcmax:
                mcmax = mscoreComp
                #
                # cut the search tree
                # by skipping the rest
                if mcmax==10:
                    break
        # calculate the final recursive score
        mscore = mscoreHuman-mcmax
    return mscore

# determine the next move
# return the position of the next move
#   x - 1, 2, ... 9
def nextMove(pGame):
    if len(pGame.players.freeSlots)==1:
        # if only 1 cell is left
        # take that move
        mpos = pGame.players.freeSlots[0]
        return mpos
    elif len(pGame.players.computer)==0:
        # if computer is the 1st to move
        # choose a position by random
        mpos = random.choice(pGame.players.freeSlots)
        return mpos
    #
    # Depth First Search (DFS)
    # ------------------------
    mtreesrchlvl = gSearchLevel # maximum tree search level
    mmovescore = []   # [(move,score)]
    # evaluate the score for each
    # available move
    for mi in pGame.players.freeSlots:
        mscoreComp = a_score(
            mtreesrchlvl,mi,pGame.players)
        mmovescore.append([mi,mscoreComp])
        # debug
        mstr = 'Pos: %s  '%mi
        mstr += 'C Score: '+str(mscoreComp)
        print mstr
        print '-'*20
    mmax = -20
    mbestmovelist = []
    # find best move list
    for mi in mmovescore:
        if mi[1]>mmax:
            mmax = mi[1]
    for mi in mmovescore:
        if mi[1]==mmax:
            mbestmovelist.append(mi[0])
    mpos = random.choice(mbestmovelist)
    return mpos

# main
gSearchLevel = 3  # maximum depth of the tree level for DFS

mgame = boardgame()
mgame.players.turn = random.choice(['c','h'])
if mgame.players.turn=='h':
    mgame.printBoard()
while mgame.endGame() == 'n':
    if mgame.players.turn=='h':
        # human's turn
        mfree = mgame.players.freeSlots
        ms = 'Your turn ['
        for mi in mfree:
            ms += str(mi) + ', '
        ms = ms[:-2]+'] ? '
        mpos = input(ms)
        if not mpos in mfree:
            continue
        mgame.players.humanMove(mpos)
    else:
        # computer's turn
        # next move
        mpos = nextMove(mgame)
        # random move
        print 'Computer choose %s' % (mpos)
        mgame.players.computerMove(mpos)
    mgame.printBoard()
    print

# print result
if mgame.endGame() == 'h':
    print 'Human wins!'
elif mgame.endGame() == 'c':
    print '          (X) Computer wins!'
elif mgame.endGame() == 'd':
    print '     Draw!'
print

Test Run



     |   |  
  ---|---|---
     |   |  
  ---|---|---
     |   |  

Your turn [1, 2, 3, 4, 5, 6, 7, 8, 9] ? 3

     |   | O
  ---|---|---
     |   |  
  ---|---|---
     |   |  


Computer choose 4

     |   | O
  ---|---|---
   X |   |  
  ---|---|---
     |   |  


Your turn [1, 2, 5, 6, 7, 8, 9] ? 6

     |   | O
  ---|---|---
   X |   | O
  ---|---|---
     |   |  


L1: c tries 1
  L2: h tries 2
    L3: c tries 5
    L3: c tries 7
  L2: h tries 5
    L3: c tries 2
    L3: c tries 7
  L2: h tries 7
    L3: c tries 2
    L3: c tries 5
    L3: c tries 8
    L3: c tries 9
  L2: h tries 8
    L3: c tries 2
    L3: c tries 5
    L3: c tries 7
  L2: h tries 9
Pos: 1  C Score: -7
--------------------
L1: c tries 2
  L2: h tries 1
    L3: c tries 5
    L3: c tries 7
    L3: c tries 8
    L3: c tries 9
  L2: h tries 5
    L3: c tries 1
    L3: c tries 7
    L3: c tries 8
    L3: c tries 9
  L2: h tries 7
    L3: c tries 1
    L3: c tries 5
    L3: c tries 8
    L3: c tries 9
  L2: h tries 8
    L3: c tries 1
    L3: c tries 5
    L3: c tries 7
    L3: c tries 9
  L2: h tries 9
Pos: 2  C Score: -8
--------------------
L1: c tries 5
  L2: h tries 1
    L3: c tries 2
    L3: c tries 7
    L3: c tries 8
    L3: c tries 9
  L2: h tries 2
    L3: c tries 1
    L3: c tries 7
    L3: c tries 8
    L3: c tries 9
  L2: h tries 7
    L3: c tries 1
    L3: c tries 2
    L3: c tries 8
    L3: c tries 9
  L2: h tries 8
    L3: c tries 1
    L3: c tries 2
    L3: c tries 7
    L3: c tries 9
  L2: h tries 9
Pos: 5  C Score: -7
--------------------
L1: c tries 7
  L2: h tries 1
    L3: c tries 2
    L3: c tries 5
    L3: c tries 8
    L3: c tries 9
  L2: h tries 2
    L3: c tries 1
  L2: h tries 5
    L3: c tries 1
  L2: h tries 8
    L3: c tries 1
  L2: h tries 9
Pos: 7  C Score: -7
--------------------
L1: c tries 8
  L2: h tries 1
    L3: c tries 2
    L3: c tries 5
    L3: c tries 7
    L3: c tries 9
  L2: h tries 2
    L3: c tries 1
    L3: c tries 5
    L3: c tries 7
    L3: c tries 9
  L2: h tries 5
    L3: c tries 1
    L3: c tries 2
    L3: c tries 7
    L3: c tries 9
  L2: h tries 7
    L3: c tries 1
    L3: c tries 2
    L3: c tries 5
    L3: c tries 9
  L2: h tries 9
Pos: 8  C Score: -7
--------------------
L1: c tries 9
  L2: h tries 1
    L3: c tries 2
    L3: c tries 5
    L3: c tries 7
    L3: c tries 8
  L2: h tries 2
    L3: c tries 1
    L3: c tries 5
    L3: c tries 7
    L3: c tries 8
  L2: h tries 5
    L3: c tries 1
    L3: c tries 2
    L3: c tries 7
    L3: c tries 8
  L2: h tries 7
    L3: c tries 1
    L3: c tries 2
    L3: c tries 5
    L3: c tries 8
  L2: h tries 8
    L3: c tries 1
    L3: c tries 2
    L3: c tries 5
    L3: c tries 7
Pos: 9  C Score: 3
--------------------
Computer choose 9

     |   | O
  ---|---|---
   X |   | O
  ---|---|---
     |   | X


Your turn [1, 2, 5, 7, 8] ? 5

     |   | O
  ---|---|---
   X | O | O
  ---|---|---
     |   | X


L1: c tries 1
  L2: h tries 2
    L3: c tries 7
  L2: h tries 7
Pos: 1  C Score: -7
--------------------
L1: c tries 2
  L2: h tries 1
    L3: c tries 7
    L3: c tries 8
  L2: h tries 7
Pos: 2  C Score: -8
--------------------
L1: c tries 7
  L2: h tries 1
    L3: c tries 2
    L3: c tries 8
  L2: h tries 2
    L3: c tries 1
  L2: h tries 8
    L3: c tries 1
Pos: 7  C Score: 4
--------------------
L1: c tries 8
  L2: h tries 1
    L3: c tries 2
    L3: c tries 7
  L2: h tries 2
    L3: c tries 1
    L3: c tries 7
  L2: h tries 7
Pos: 8  C Score: -7
--------------------
Computer choose 7

     |   | O
  ---|---|---
   X | O | O
  ---|---|---
   X |   | X


Your turn [1, 2, 8] ? 1

   O |   | O
  ---|---|---
   X | O | O
  ---|---|---
   X |   | X


L1: c tries 2
  L2: h tries 8
Pos: 2  C Score: 2
--------------------
L1: c tries 8
Pos: 8  C Score: 10
--------------------
Computer choose 8

   O |   | O
  ---|---|---
   X | O | O
  ---|---|---
   X | X | X


          (X) Computer wins!

Open Technical Blog

Wednesday, 28 August 2019

A Framework for Board Games - Part II

Source Code

Test Run

No comments:

Post a Comment