Reentrant's Blog

How I made a checker's program

How I made a checker's program

In python and text-based

Robert Huang's photo
Robert Huang
·

12 min read

Table of contents

My 2022 new year's resolution is to crack the computer programming industry within 3 years. So I decided to start somewhere, and what better way is there than to get advice from random strangers on reddit. I made a cash register first, but that was simple. Then I made the checker's game -- it took about 4 days to make, about 2-3 hours each day the first 3 days and about 5-6 hours the last day.

I already knew python relatively well and I had Miniconda environment set up for my various random projects like web crawling/scraping, machine learning tutorials. So it didn't take me time to set up the environment. I use Notepad++ to write my code and then run it under Anaconda prompt.

Then I played a quick game of checkers online to understand the rules, and from there I drafted a general outline of the logic and algorithm of the game.

The Basic Mechanics of the Game

For me, coding is the easier part. The harder part is to assemble the game mechanics correctly together and organizing the code. To do so well, I started with defining the criteria and limitations of the game: how it's going to represented and how to play it.

To focus on programming logic, I limited the game to being a text-based representation and works only offline -- so no need to dabble in GUI programming, graphics nor web development. That cut down a lot of extra work to program the logic behind the game.

I also decided that the game will be played by 2 human players so no game AI need to be developed, which drastically cut down on logic loops. The primary focus is on assembling the game code together. Once that is done, GUI and graphics can be updated if desired, or ported online for the internet. Player 2 can be updated to becoming a computer player by replacing human input (but being able to put in a computer player doesn't mean the quality of the AI will be great, because that would require the programmer to have in-depth game experience, which I don't.) Whilst machine learning can be utilized, I am not there yet.

Board Representation

Because the spaces not occupied by pieces are never used, the board was represented by a 2D array only for used spaces. So instead of a 8x8 array, an 8x4 array was used, 8 rows and 4 columns.

chest_representation.jpg

Here's the code for the checker board and checker piece.

rows = 8       
cols = 4     # ignores unused board spaces in each row; otherwise would be = 8
             # one unintended benefit of doing so means that it eliminates a 
             # potential bug in which a game piece moves into an unused space
             # because there's no data stored for unused space. display
             # reconstitutes the whole board by expanding the used space and
             # putting in 'x' for unused space

class Pieces:
    def __init__(self, player_id, location):
        self.player_id = player_id
        self.king = False
        self.location = location  #(row,col)
        self.availableMoves = []
        self.mustMoves = []

class Board:
    def __init__(self): 
        self.board = [[Pieces(1,(row,col)) if row < 3 else (0 if row < 5 else Pieces(2,(row,col))) for col in range(cols)] for row in range(rows)]
        self.player_pieces = [12, 12]  # default, when printBoard is run, will override default value
        self.num_empty_turns = 0
        self.boardState = {}
        self.three_same_board_state = False
        self.player_no_avail_moves = [False, False]
        self.currentMoveEat = False   # if current move resulted in an eaten piece
        self.currentMoved = False   # if player has made a move
        self.hasMustMoves = False    # current player has must moves pieces
        self.lastMustMovePiece = 0    # the last piece that eaten

    def checkLocation(self, row, col):
        return self.board[row][col]         # returns Pieces or zero

    def updateLocation(self, location, piece):
        self.board[location[0]][location[1]] = piece

Basically the Piece object would keep info about its player, whether it's a king, its location and its available moves every round. Available moves are split into moves that the piece can do and moves that it must do, i.e. jumping over an enemy piece if it has that option.

The Board object contains the information regarding the checker Pieces location on a 2D array, how many pieces are left for each player, how many "empty" turns are taken without jumping over an enemy piece, keeps track of the distribution of each checker piece on the board each round to test for the tie condition of 3 same board states, see if the player's pieces are all blocked, if the player has moved in the current turn, and did that move result in eating an enemy piece, and if the player has pieces that must be moved (i.e. eating an enemy) and identify which piece ate the enemy to see if it can move again to eat another enemy piece.

This sets up for the remainder of the program, with helper functions to flesh out class objects.

Text Display of Board

For the display of the checker's board, I decided to use a very simple text representation: '1' represents player 1, '2' for player 2, '0' for empty space and 'x' for the in between unused board space. The code shifts the columns to offset the columns in the prior row by 1, creating the staggered placement.

def printBoard(currentBoard):       # this could be a class def of Board
    rowLayout = ""
    boardStateAsString = ""
    playerPieces = [0, 0]
    for row in range(rows):
        for col in range(cols):
            if (row + 1) % 2 == 0:      # row + 1 to offset index starting at 0
                rowLayout += 'x'
            temp = currentBoard.board[row][col]
            if temp.__class__ == Pieces:
                rowLayout += str(temp.player_id)
                playerPieces[temp.player_id-1] += 1 # player_id - 1 to offset to array index
            else:
                rowLayout += str(temp)
            if (row + 1) % 2 == 1:      # row + 1 to offset index starting at 0
                rowLayout += 'x'
        print(rowLayout)
        boardStateAsString += rowLayout
        rowLayout = ""
    currentBoard.player_pieces = playerPieces
    addBoardState(currentBoard, boardStateAsString)

def addBoardState(currentBoard, boardStateAsString):  # this could be a class def of Board
    if boardStateAsString in currentBoard.boardState:
        currentBoard.boardState[boardStateAsString] = currentBoard.boardState[boardStateAsString] + 1
        if currentBoard.boardState[boardStateAsString] == 3:
            currentBoard.three_same_board_state = True
    else:
        currentBoard.boardState[boardStateAsString] = 1

The printBoard function takes in a single argument of the Board object, and prints the text representation. During the looping through of the 2D array representation of the board, the function also takes care of keeping track of the number of player pieces and forming a string representation of the board.

The string representation is then passed to the function addBoardState function and stores it in a dictionary so program can keep track of how many times a board state occurs, and terminates the game in a tie when it detects 3 same board states.

Checking winning conditions

A function was written to check the winning / losing or tie conditions that will be called by the game loop every turn. It basically just accesses flags in the Board object instance that tells the game whether conditions have been. These conditions are checked during different parts of the game. For example, the number of player pieces are refreshed during the printing of the board or updated when an enemy piece is eaten; or if the player has any moves is determined during the looking up moves part of the game. When condition(s) are met, the flags are triggered which then allows the game to check for it at the beginning of a turn.

def checkEndGame(currentBoard):
    if currentBoard.player_pieces[0] <= 0:   # player 1 loses
        return 2    # winner 2
    if currentBoard.player_pieces[1] <= 0:   # player 2 loses
        return 1    # winner 1
    if currentBoard.num_empty_turns >= 100:  # tie
        return 3    # tie
    if currentBoard.three_same_board_state == True:
        return 3
    if currentBoard.player_no_avail_moves[0] == True:
        return 2
    if currentBoard.player_no_avail_moves[1] == True:
        return 1
    return 0        # no end game condition

Moving Pieces

Coding the logic behind moving pieces on the checker board is the last piece (pun intended) of the puzzle before putting them together into the game loop. It is also the most algorithm intense portion of the game.

It starts with a function that looksUpMove, which calls the function pieceMoveOptions, which determines the possible moves for each piece on the checker board for the player whose turn it is. Several helper functions like finding the diagonal spaces, findAdjSpaces, and converting between the collapsed 2D array (8x4) representation of the board to the normal 2D array (8x8) representation are used to facilitate finding diagonal spaces and implement the logic to jump over enemy pieces.

# this function takes in the row and compacted col and returns
# the expanded col number
def expandCompactCol(row,col):
    return row % 2 + col * 2 + 1

def compactExpandCol(row, expandedCol):
    return int((expandedCol - 1 - row % 2) / 2)

# player 1 default direction is down the board (or increasing row number) while
# player 2 default direction is up the board (or decreasing row number)
def findAdjSpaces(piece, direction): # find the diagonal spaces Piece can move to
    row = piece.location[0]
    col = piece.location[1]
    adjRows = []
    adjCols = []
    # default defaults to player 1 available motion
    # down or up direction depends on whether there is pieces to be eaten
    if direction == "default":
        if piece.player_id == 1:   # player 1 can  move down by default and up if king
            if row < rows - 1: adjRows.append(row+1) 
            if piece.king == True:
                if row > 0: adjRows.append(row-1)   # can move backward
        else:     # player 2 can move up by default, down if king
            if row > 0: adjRows.append(row-1)
            if piece.king == True:
                if row < rows - 1: adjRows.append(row+1)
    elif direction == "down":
        if row < rows - 1: adjRows.append(row+1)
    else:
        if row > 0: adjRows.append(row-1)

    expandedCol = expandCompactCol(row,col)
    if expandedCol == 1: adjCols.append(expandedCol + 1)
    elif expandedCol == 8: adjCols.append(expandedCol - 1)
    else:
        adjCols.append(expandedCol - 1)
        adjCols.append(expandedCol + 1)

    listofSpaces = []
    for adjRow in adjRows:
        for adjCol in adjCols:
            listofSpaces.append((adjRow, compactExpandCol(adjRow, adjCol)))

    return listofSpaces

def pieceMoveOptions(currentBoard, row, col, player_id):
    piece = currentBoard.checkLocation(row,col)
    if piece != 0 and piece.player_id == player_id:
        piece.availableMoves = []
        piece.mustMoves = []
        listofSpaces = findAdjSpaces(piece, "default")  # default player movement

        for space in listofSpaces:
            target = currentBoard.checkLocation(space[0],space[1])
            if target != 0:
                if target.player_id != player_id:
                    jumpSpaces = findAdjSpaces(target, "down" if space[0] > row else "up")
                    for jumpSpace in jumpSpaces:
                        jumpTarget = currentBoard.checkLocation(jumpSpace[0],jumpSpace[1])
                        if jumpTarget == 0:
                            jumpSpaceExpandedCol = expandCompactCol(jumpSpace[0],jumpSpace[1])
                            expandedCol = expandCompactCol(row,col)
                            targetExpandedCol = expandCompactCol(space[0],space[1])
                            if (targetExpandedCol < expandedCol and jumpSpaceExpandedCol < targetExpandedCol) or (targetExpandedCol > expandedCol and jumpSpaceExpandedCol > targetExpandedCol):
                                piece.mustMoves.append(jumpSpace)
                else:
                    pass # do nothing if equal
            else:
                piece.availableMoves.append(space)
        printMoves(piece)   # debug
        if piece.mustMoves: currentBoard.hasMustMoves = True
        if piece.availableMoves or piece.mustMoves: return True
    if piece != 0 and piece.player_id != player_id:   # just checks to see if opposing team piece gets to be king from prior round
            if piece.location[0] == rows - 1 and piece.player_id == 1:
                piece.king = True
            if piece.location[0] == 0 and piece.player_id == 2:
                piece.king = True
    return False

# this function looks up possible moves for player 'player_id'
# returns empty if no moves possible (player 'player_id' loses)
# otherwise returns a set of moves possible
# if there are moves to eat enemy pieces, then will exclude non-eating moves
def lookUpMoves(currentBoard, player_id):
    canMove = False
    currentBoard.hasMustMoves = False
    for row in range(rows):
        for col in range(cols):
            canMove = pieceMoveOptions(currentBoard, row, col, player_id) or canMove
    currentBoard.player_no_avail_moves[player_id-1] = not canMove

#debug function
def printMoves(piece):
    message = "Player " + str(piece.player_id) + ", Location: " + str(piece.location) + ", available moves: " + str(piece.availableMoves) + ", must moves: " + str(piece.mustMoves)
    print(message)

Once all possible moves are known for each piece, a function movePiece then determines if the player indicated moves for a piece is valid. If it is then the piece is moved. For a piece jumping over multiple enemy pieces, it is implemented as a while loop rather than recursion, where the player has to manually input that next piece he/she wants to jump over, even if there is only one choice. It simplifies coding logic where there are multiple pathways to chose from.

def movePiece(currentBoard, location_from, location_to):
    piece = currentBoard.checkLocation(location_from[0],location_from[1])
    if piece != 0:
        if piece.mustMoves:
            if location_to in piece.mustMoves:
                piece.location = location_to
                currentBoard.updateLocation(location_to, piece)
                currentBoard.updateLocation(location_from, 0)
                targetRow = -1
                targetCol = -1
                if location_from[0] < location_to[0]:
                    targetRow = location_to[0] - 1
                else: targetRow = location_to[0] + 1
                currentColExpanded = expandCompactCol(location_from[0],location_from[1])
                if location_from[1] < location_to[1]:
                    targetCol = compactExpandCol(targetRow, currentColExpanded + 1)
                else: targetCol = compactExpandCol(targetRow, currentColExpanded - 1)
                targetPiece = currentBoard.checkLocation(targetRow,targetCol)
                currentBoard.updateLocation((targetRow,targetCol),0)
                currentBoard.player_pieces[targetPiece.player_id-1] -= 1
                del targetPiece
                currentBoard.num_empty_turns = 0
                currentBoard.currentMoveEat = True
                currentBoard.lastMustMovePiece = piece
                return True   # a move was made
            else: return False  # a move was not made because location_to not valid
        else:
            if currentBoard.hasMustMoves: return False
            if piece.availableMoves:
                if location_to in piece.availableMoves:
                    piece.location = location_to
                    currentBoard.updateLocation(location_to, piece)
                    currentBoard.updateLocation(location_from, 0)
                    currentBoard.num_empty_turns += 1
                    return True
                else: return False
    return False

Finally, the game loop!

The game loop is relatively straightforward with 2 while loops, one nested in the other. The outermost while loop sets up the board and determines possible moves and player turn, while the inner while loop moves the pieces. If moving the piece results in an enemy being eaten, the inner loop will refresh the board and recalculate the moves of each piece. At this point, if the piece that ate an enemy piece has no more enemy pieces to eat, it will break out of the inner loop to resume the outer loop; otherwise, it will ask the player to eat the next piece and repeat until the piece has no more enemy piece to eat.

# set up board    
myBoard = Board()
player_turn = 1

# game loop
while(checkEndGame(myBoard) == 0):
    print("Player " + str(player_turn) + " turn:")
    printBoard(myBoard)
    lookUpMoves(myBoard, player_turn)
    if not myBoard.player_no_avail_moves[player_turn - 1]:
        myBoard.currentMoved = False
        myBoard.currentMoveEat = False
        while not myBoard.currentMoved or myBoard.currentMoveEat:
            if myBoard.currentMoveEat:
                printBoard(myBoard)
                lookUpMoves(myBoard, player_turn)
                myBoard.currentMoveEat = False
                if not myBoard.lastMustMovePiece.mustMoves:
                    myBoard.lastMustMovePiece = 0
                    break
            selectPiece = input('Select your piece ("e" to exit):')
            if selectPiece == 'e': break
            nextMove = input('Move to where ("e" to exit):')
            if nextMove == 'e': break
            location_from = (int(selectPiece.split('-')[0]),int(selectPiece.split('-')[1]))
            location_to = (int(nextMove.split('-')[0]),int(nextMove.split('-')[1]))
            myBoard.currentMoved = movePiece(myBoard, location_from, location_to)
            if not myBoard.currentMoved: print("Move failed!")
    if player_turn == 1: player_turn = 2
    else: player_turn = 1
    if selectPiece == 'e' or nextMove == 'e': break
print("Game Ended - Winner: " + str(checkEndGame(myBoard)))

When winning / tie conditions are met, the game will stop and print out who won or if it is a tie.

It's a feature, not a bug...

So there is one obvious 'feature' in the program where if the input does not conform to the '#-#' format i.e. 2-1, meaning row 3 column 2, the program will terminate in runtime error as that is required for proper conversion of string input into location tuple. Also if the numbers do not fall within the range of the rows or columns, there is no check for that, and the program will terminate in an out-of-index error.

So that's it!

That's the game. It is a complete game in itself, playable and finishable. While it does not look fancy and the input to the moves have to follow a strict format, the game logic follows the game rules. As mentioned in the very beginning, graphical presentation can be improved, porting to web can be implemented and even coding for an AI opponent can be done. These are possible iterations of the next version if so desired. At this point, however, I am leaving this game in its current state, and moving on to coding other projects. If there is a coding practice that could expand on this code base, I may return to it. Otherwise, hope you enjoy the process of making the game and if there's feedback, feel free to shoot me a message.

Python