UserPreferences

PyroModuleAI:GamePlaying


Pyro Module AI Game Playing

This module explores two-person board game playing. This section looks at a simple version of checkers.

http://www.cs.swarthmore.edu/~meeden/cs63/s04/konane.jpg

Konane, Hawaiian Checkers

The game of Konane is typically played on an 8 x 8 board of light and dark pieces as shown below (using X for dark and O for light).

                1 2 3 4 5 6 7 8

        8       X O X O X O X O
        7       O X O X O X O X
        6       X O X O X O X O
        5       O X O X O X O X
        4       X O X O X O X O
        3       O X O X O X O X
        2       X O X O X O X O
        1       O X O X O X O X

Rules

These rules are slightly adapted.

First, players pick their color (shape) and a coin is flipped to see who goes first. If the the dark player (X) wins the toss, then they remove a dark piece either at position (1,8), (8,1), (4,5), or (5,4). Likewise, if the light player (O) wins the toss, then they remove a piece from either (1,1), (8,8), (4,4), or (5,5).

Next the other player removes one of their pieces adjacent to the space created by the first move. Then the players alternate moves, each jumping one of his/her own pieces over one horizontally or vertically adjacent opponent piece, landing in a space on the other side, and removing the jumped piece. If desired, this may be continued in a multiple move, as long as the same piece is moved in a straight line. For example, after the following moves:

        dark (X)                  light (O)
        -----------------------   ---------------------------------
        remove (5, 4)             remove (5, 5)
        jump (3, 4) to (5, 4)     jump (5, 7) to (5, 5)
        jump (3, 2) to (3, 4)     jump (5, 3) to (3, 3)
        jump (7, 6) to (5, 6)     jump (6, 4) to (6, 6)
        jump (7, 8) to (7, 6)     jump (2, 4) to (4, 4) to (6, 4)

the board looks like:

                1 2 3 4 5 6 7 8

        8       X O X O X O X O
        7       O X O X O X . .
        6       X O X O . O X O
        5       O X . . O X . X
        4       X O . . X O X O
        3       O . O . O X O X
        2       X O X . X O X O
        1       O X O X O X O X

Play continues until one player can't move; this player loses.

Pyro Konane

The Konane simulator in Pyro can be played by two Pyro programs, or against a human.

Simulalator

Pyro uses the SymbolicSimulator with the KonaneWorld.py. First, start pyro and select SymbolicSimulator under Servers:. Then select KonaneWorld.py when asked for a world file. You should see a window come up that looks something like:

http://bubo.brynmawr.edu/~dblank/images/konane.gif

Don't click in the Konane GUI window. That will be interpreted as a move (removes the stone in that cell). If you accidently do so, you can put a piece back my clicking on that spot again.

The red color indicates who's move it is.

See The Symbolic Simulator for more worlds that can be used with this simulator.

Robot

After starting the server, you need to connect onto one of the two available ports using a robot file. You can select either SymbolicPlayer60000.py or SymbolicPlayer60001.py. At this point, you (or someone else) can start another version of Pyro, and select the other SymbolicPlayer file. Use SymbolicPlayer.py and name the host and port if connecting from a different computer.

You can also play a human. The human interface is very simple: click on one of your shapes when it is red, and it will vanish (its in your simulated hand). Click again on the other side of an opponent and the opponent piece will vanish, and your piece will land in the cell that you just clicked in. Click "Done!" when you are done jumping. To start over, press "Reset!". If you do press "Reset!" you should "Reload" your brain so that it starts in a fresh state.

Brain

The Symbolic Simulator has a slighty different interface than when working with robots. You have the following commands:

myNum = self.robot.id                        - method of figuring out which player you are
self.robot.whosMove                          - who's move is it? compare with robot.id
board = self.robot.board                     - get the board
self.robot.play("remove(%d,%d)" % move)      - remove a piece at location
self.robot.play("jump(%d,%d,%d,%d)" % move)  - make a single jump
self.robot.play("done")                      - signal that you are done making moves

Note that play() takes string data. With the above commands, you have everything you need to write a Pyro brain to play Konane. Here is a skeleton, showing how to manage some of the overhead:

...

 def setup(self):
        if self.id == 0:
            self.myPiece = "O"
        else:
            self.myPiece = "X"
        self.firstMove = 1

    def step(self):
        if self.robot.whosMove != self.id: return
        board = self.robot.board
        moves = GET ALL POSSIBLE MOVES 
        self.firstMove = 0
        if len(moves) > 0:
            # Here is where you would go through the possible
            # moves and pick the best one.
            move = PICK ONE ACCORDING TO SOME CRITERIA 
            if len(move) == 2: # remove the piece
                self.robot.play("remove(%d,%d)" % move)
                self.robot.play("done")
            elif len(move) == 4: # a single jump
                self.robot.play("jump(%d,%d,%d,%d)" % move)
                self.robot.play("done")
            else:
                # multi-jump
                ...
        else:
            print "You win!"

Here is an entire program that plays random Konane moves.

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 75 
 76 
 77 
 78 
 79 
 80 
 81 
 82 
 83 
 84 
 85 
 86 
 87 
 88 
 89 
 90 
 91 
 92 
 93 
 94 
 95 
 96 
 97 
 98 
 99 
100 
101 
102 
103 
104 
105 
106 
107 
108 
109 
110 
111 
112 
113 
114 
115 
116 
117 
118 
119 
120 
121 
122 
123 
124 
125 
126 
127 
128 
129 
130 
131 
132 
133 
134 
135 
136 
137 
138 
139 

"""
This module contains a class of a random Konane Player.
The brain KonanePlayer program plays a random game of Konane.
"""

from pyrobot.brain import Brain
import time, random

def otherPiece(piece):
    """ What is the opponent's shape? """
    if piece == 'O': return 'X'
    else: return 'O'

def getEmpties(board):
    """ Returns all of the empty positions on board. """
    retval = []
    for i in range(8):
        for j in range(8):
            if board[i][j] == '':
                retval.append( (i+1, j+1) )
    return retval

def add(pos, offset):
    """ Adds two board positions together """
    return (pos[0] + offset[0], pos[1] + offset[1])

def validPos(pos, offset = (0,0)):
    """ Is this position + offset a valid board position?"""
    newx, newy = add(pos, offset)
    return (newx >= 1 and newx <= 8 and newy >= 1 and newy <= 8)

def moveGenerator(board, myPiece, firstMove):
    """Generates legal board moves. Doesn't find multiple-jumps. """
    retval = []
    empties = getEmpties(board)
    if firstMove:
        if len(empties) == 0: # I'm first!
            if myPiece == "O":
                retval.extend( [(4,4), (5,5), (1,1), (8,8)] )
            else:
                retval.extend( [(5,4), (4,5), (1,8), (8,1)] )
        else: # I'm second
            # get one of the 4 (or less) surrounding pieces
            openPos = empties[0] # better be just one
            for i,j in [(-1,0), (+1,0), (0, -1), (0, +1)]:
                if validPos(openPos, (i,j)):
                    retval.append( add(openPos, (i,j)) )
    else:
        # find all moves, and add them to list
        for i in range(1,9):
            for j in range(1,9):
                if board[i-1][j-1] == myPiece:
                    for a,b in [(0, -2),(+2,-2), (+2, 0),(+2, +2),
                                (0, +2),(-2, +2),(-2, 0),(-2, -2)]:
                        p, q = i, j   # a starting place
                        move = [i, j] # first part of move
                        while 1: # still jumps to make
                            if validPos((p,q), (a,b)):
                                x,y = add((p,q),(a,b))
                                if board[x-1][y-1] == '':
                                    bx, by = add( (p,q), (x,y) )
                                    bx, by = bx/2, by/2
                                    if board[bx-1][by-1] == otherPiece(myPiece):
                                        move.extend( [x,y] )
                                        # jump some more?
                                        p, q = x, y
                                    else:
                                        break
                                else:
                                    break
                            else:
                                break
                        if len(move) > 2:
                            retval.append( move )
    return retval

def formatMove(move):
    """ Formats a list of positions into a jump() string. """
    movestr = "jump(%d,%d" % (move[0], move[1])
    while 1:
        x1, y1, x2, y2 = move[:4]
        movestr += ",%d,%d" % (x2, y2)
        move = move[2:]
        if len(move) < 4:
            break
    movestr += ")"
    return movestr

class KonanePlayer(Brain):
    """
    A simple Random Konane Player. Note that the rep of board is
    zero-based, but all other places is one's based.
    For use with PyrobotSimulator and KonaneWorld.py and
    PyrobotRobot.py (a TCPRobot from pyrobot/robot/symbolic.py)
    """
    def setup(self):
        if self.robot.id == 0:
            self.myPiece = "O"
        else:
            self.myPiece = "X"
        self.firstMove = 1
        self.turn = 1
        print "Welcome to Konane, Hawaiian Checkers!"
        print "Red O or X on the board indicates that it"
        print "is that shape's move."
        print "Jumps must occur in a straight line."
        print "A human can play, or start two Pyro's up,"
        print "and connect onto two different ports using"
        print "PyrobotRobot60000 and PyrobotRobot60001."

    def step(self):
        if self.robot.whosMove != self.robot.id:
            time.sleep(1)
            return
        board = self.robot.board
        moves = moveGenerator(board, self.myPiece, self.firstMove)
        self.firstMove = 0
        if len(moves) > 0:
            # Here is where you would go through the possible
            # moves and pick the best one.
            # I'm just going to pick a random one:
            move = moves[int(len(moves) * random.random())]
            if len(move) == 2: # remove the piece
                self.robot.play("remove(%d,%d)" % move)
                print self.turn, "remove(%d,%d)" % move
                self.robot.play("done")
            else: # jumps
                movestr = formatMove(move)
                print self.turn, movestr
                self.robot.play(movestr)
                self.robot.play("done")
            self.turn += 1
        else:
            print "You win!"
            self.pleaseStop() # request to stop running brain

def INIT(engine):
    return KonanePlayer("Random Konane Player", engine)

Exercises

  1. Write a "static evaluator" that judges how good a board position is for you.

  2. Use the static evaluator to write a Konane player using:

    1. Breadth-first search (two ply)

    2. A-star search

    3. MINIMAX

    4. MINIMAX with alpha-beta pruning

Your program should also provide the following information:

  1. Have a friendly tournament in class

  2. Copy and edit KonaneWorld.py to make your own game to play. It is very easy to make a different simulator: the entire Konane simulator is only about 200 lines of code, and the simple brain above is only about 100 lines. You can change the Konane simulator to be chess, checkers, or something else entirely (poker anyone?).

Links


This page is based on an assignment originally by Deepak Kumar.

Pyro Modules Table of Contents

Modules

  1. PyroModuleIntroduction

  2. PyroModuleObjectOverview

  3. PyroModulePythonIntro

  4. PyroModuleDirectControl

  5. PyroModuleSequencingControl

  6. PyroModuleBehaviorBasedControl

  7. PyroModuleReinforcementLearning

  8. PyroModuleNeuralNetworks

  9. PyroModuleEvolutionaryAlgorithms

  10. PyroModuleComputerVision

  11. PyroModuleMapping

  12. PyroModuleMultirobot

  13. FurtherReading

Additional Resources

  1. PyroIndex

  2. PyroAdvancedTopics

  3. PyroUserManual

  4. [WWW]Pyro Tutorial Movies

Reference: PyroSiteNotes