EE 476 Final Project Report
Chris Otto
Andy Boyd

 Tic-Tac-Toe Code
 Chess Code
 Initial Include File


        For our final project we decided to make platforms for simple two player games.  This topic was selected because it uses most of what we have learned in EE 476, and it is also interesting and fun.  The games we thought of were tic-tac-toe, blackjack (or any card game), backgammon, and chess.  We realized that we probably would not have the time to emulate all of these games, so our focus is on tic-tac-toe and chess.  Tic-tac-toe being the simplest option, and chess being one of the more complicated.
        We chose to do two player games rather than single player games because of the complexity of AI.  A game with simple AI is not fun to play; it amounts to simply clicking buttons to beat a stupid computer.  A human opponent is much more interesting and challenging a competitor, and we do not believe we could program a challenging AI with the limited chip memory.
        The program starts off by asking you which game, as of now tic-tac-toe or chess, you wish to play.  After choosing, it will start the appropriate game.  Tic-tac-toe could be played on an LED display, but we would need an 8x8 LED display to play chess so we chose to have the viewing interface be a HyperTerminal connection.  The basic boards are as follows:

Fig1: Tic-Tac-Toe                                          Fig2: Chess Board   (Note:  Knight is represented by a K and King by a U)

                                                1       2       3       4        5        6        7       8
1   |   2   |   3                    1[  wR |  wK |  wB |  wU |  wQ |  wB |  wK | wR ]
-------------                        ----------------------------------------------
4   |   5   |   6                   2[  wP  |  wP |  wP |  wP  |  wP  |  wP |  wP  |  wP ]
-------------                        ----------------------------------------------
7   |   8   |   9                   3[        |        |       |         |        |        |        |       ]
                                         4[        |        |       |         |        |        |        |       ]
                                         5[        |        |       |         |        |        |        |       ]
                                         6[        |        |       |         |        |        |        |       ]
                                         7[  bP  |  bP  |  bP |  bP   |  bP  |  bP  |  bP  |  bP ]
                                         8[  bR  |  bK |  bB |  bU  |  bQ |  bB |  bK  | bR ]

        For tic-tac-toe, the users choose a number, which is then replaced by X or O appropriately.   Then the next player chooses a number.  When there are no more spaces left, or a player has three in a row, the game ends and a new game starts.  For chess the users pick one of their pieces and move it according to the rules.  This is accomplished by typing the row and the column of the piece you want to move, and then typing in the row and column of the space you want to move to.  As of now, we plan to implement what was taught to me as “speed chess”, which allows for the king to move into check or not move when in check.  This basically means if you’re not paying attention your king can be captured at any time.  “Speed chess” is also timed, and the first one to hit 5 minutes of time on his clock loses.  We will probably not include this timing feature because the shared keypad and unnatural interface.  Too much time would be wasted fighting for the keypad and typing digits, but the game should still be played fast.  Error messages will be displayed on the LED to prevent scrolling the current board off the HyperTerminal screen.  For both games, after every move the new board will be displayed on the HyperTerminal screen.  If time permits we will build an interface so that both players will have an LED and keypad in front of them and implement a timer for speed chess.

 Algorithms for Tic-Tac-Toe and Chess


Check for previous ownership:
        Each player will have two "spaces owned " registers that will start off cleared. Only the LSB of the second register will be used. When a player tries to take square X (a number between 1 and 9), the program will check bit X of both players’ registers. If neither player has that bit set, the program will set that bit in the player’s registers which means he owns that square. If that bit is set in either player’s registers, an error will be displayed on the LED, and the player will be asked to choose another square.

Check for win or tie condition:
        There are eight possible ways for a player to win: three rows, three columns, and two diagonals. After every move, the "spaces owned" registers will be OR’ed with a winning combination, put into a temporary register, and compared to that winning condition. If they are equal, the program will move to a win condition and the game will end. This will be done eight times for every move (for each possible win condition) and if no win condition exists, the next player will be allowed to go. After 9 moves, if no win condition exists the game will be considered a tie and will end.
        The bit configurations for a win are: (see fig 1)
        Square: 12345678-9     (Note:  The dash signifies the need to look at the second register)


Check for a valid piece:
        When a piece is chosen by grid co-ordinates, the area of memory corresponding to that co-ordinate will be accessed and two bytes will be read into temporary registers. These are the two bytes that correspond to color of piece and nature of the piece. The color of the piece is white (ASCII w) black (ASCII b) or nothing. This bit sequence must equal the color of the player going or he will be asked to choose another piece to move.

Check for valid move:
        After a valid piece is chosen to move, the LED will ask for the space to move to. All four co-ordinates, beginning row and column and ending row and column will be stored in temporary registers. (Labeled begrow, begcol, endrow, and endcol respectively) The nature of the piece determines how that piece can be moved. The pieces are, P(awn), R(ook), B(ishop), K(night), U(King), and Q(ueen). The register that holds the "nature" (It will hold an ASCII P, R, B, K, U or Q) component will be compared to the possible values and will jump to the correct algorithm to check for a correct move. As soon as a valid move is detected (passes an algorithm) the old location of memory is cleared and the new one is loaded with the piece. The correct move algorithms are as follows:

                  Black:    1(endcol = begcol-1) and (endrow = begrow) and (endrow, endcol) does not hold a piece.
                               2(endcol = begcol-1) and (endrow = (begrow-1 or begrow+1)) and (endrow, endcol) does hold an opposite piece.
                               3(endcol = begcol-2) and (endrow = begrow = 7) and (endrow, endcol) and (endrow, endcol-1) do not hold pieces.

                  White:   1(endcol = begcol+1) and (endrow = begrow) and (endrow, endcol) does not hold a piece.
                               2(endcol = begcol+1) and (endrow = (begrow-1 or begrow+1)) and (endrow, endcol) does hold an opposite piece.
                               3(endcol = begcol+2) and (endrow = begrow = 2) and (endrow, endcol) and (endrow, endcol-1) do not hold pieces.

            Rook:     1(endrow = begrow) and not Blocked
                              2(endcol = begcol) and not Blocked
                              case(endrow>begrow+1): check (begrow+1,begcol) . . . (endrow-1,begcol) for pieces
                              case(endrow<begrow-1): check (begrow-1,begcol) . . . (endrow+1,begcol) for pieces
                              case(endcol>begcol+1):   check (begrow, begcol+1) . . . (begrow,endcol-1) for pieces
                              case(endcol<begcol-1):   check (begrow, begcol-1) . . . (begrow, endcol-1) for pieces

            Bishop:   1( | endrow - begrow | = |endcol – begcol | ) and not Blocked
                                        case(endcol>begcol+1): check (begrow+1,begcol+1) . . . (endrow-1,endcol-1)
                                        case(endcol<begcol-1):  check (begrow+1,begcol-1) . . .(endrow-1, endcol+1)
                                        case(endcol>begcol+1): check (begrow-1,begcol+1) . . . (endrow+1,endcol-1)
                                        case(endcol<begcol-1):  check (begrow-1,begcol-1) . . .(endrow+1, endcol+1)

            Knight:   1(endrow = (begrow+2 or begrow-2)) and (endcol = (begcol+1 or begcol-1))
                              2(endcol = (begcol+2 or begcol-2)) and (endrow = (begrow+1 or begrow-1))

            Queen:   1 Valid Bishop move
                              2 Valid Rook move

            King:      1( | endrow – begrow | = ( 1 or 0 ) ) and ( | endcol – begcol | = (1 or 0)) and
                              ((endrow != begrow) or (endcol != begcol))

Design Results

       The program and interface that we designed for tic-tac-toe works very well and there are no visible bugs.  We tested every outcome of the game and it produced the correct response for each input.  This is not surprising given the simplicity of the rules, but certain problems with overlapping registers and program size caused the implementation to be more difficult than was first expected.  The code programs fairly slowly but runs fast enough and is equipped with a delay between key presses and player turns to make sure that it doesn't move to fast for a human to understand and play effectively.
            The interface for chess is identical to the one for tic-tac-toe except for the change in game boards.  The chess board has a few more bugs than the tic-tac-toe game which is to be expected.  The program checks for the appropriate color piece and type in order to determine if the move is legal.  However, the code for blocking pieces was never implemented so it is possible to move through another piece with a legal move (normally only the knight could do this).  Advanced rules - such as the initial 2 space pawn move, L-shaped pawn move at the fourth square out, and Castling - were not implemented due to the amount of program and memory space they would take up.
            The code itself programs very slowly but runs fast enough and includes sufficient delays between moves and key presses.  In general, the design is sufficiently robust to catch mistakes that the players make and to correct them.  However, as in real chess, once a piece is touched, it must be moved somewhere.

Ideas for Improvement

            Given more time, it might be possible to implement a very simple AI for playing tic-tac-toe.  It is possible that this would soon get boring as the AI would become predictable.  However, tic-tac-toe is sufficiently uncomplicated that even a human player may consistently employ the same strategy every time the game is played.  An AI for chess would be virtually impossible with the equipment available, so a computer chess player will not be included in any future versions of the game.  However, with sufficient time and program space, it would be possible to implement additional error checking for invalid moves that are currently allowed.  As previously stated, it would be almost impossible to implement advanced rules due to the vast number of states that the chessboard can take on.
            Also not included in this version were the individual keypads and LCD displays.  It was discovered that it is not possible to hook two keypads up to the same port, so in order to use two keypads, a second port and getkey function would have to be added to the code for both games.  The LCD displays were not included due to the fact that the programming took place on the 8515 board which does not have a power source for the LCD.  In order to use and LCD, such a source would have to be added in, or the code would have to be modified to work on an 8535.

Schematic of our Circuit

The keypad is connected to port A using the following pin connections:
                        PinA0 - Pin5
                        Pin A1- Pin6
                        Pin A2 - Pin7
                        Pin A3 - Pin8
                        Pin A4 - Pin1
                        Pin A5 - Pin2
                        Pin A6 - Pin3
                        Pin A7 - Pin4