Welcome to CGS (short for Capstone Game Suite)!!! Here you will find an amazing experience in which you can relive your childhood by playing fun board games in a virtual environment. Forget the clutter of those clunky cardboard boxes that the board games come in, and create an account on the CGS server to get started! Currently available games include Othello, Connect4, and Traditional Checkers. You can either find a friend to play with and use the default ‘Human’ mode, or you can put your skills to the test and take on the computer by switching into ‘AI’ mode! Beware, it makes its moves quickly and is extremely smart, due to the artificial intelligence practices incorporated into its decision making. Also, the higher the difficulty level that you choose, the longer it will take for the computer to make a move and the more the application will drain your computer’s battery. Bump up to difficulty 3 at your own risk :). Tired of playing for the day, but want to pick up where you left off tomorrow? Have no fear, CGS autosaves your game to your profile when you exit. Just be sure not to switch game modes, as that will toggle a reset of your progress. Your account also saves your game records when playing against a friend or the computer. I hope you enjoy reliving your childhood through these games and that they spark an interest in the wonders of computer science and artificial intelligence/decision making.
To get started, ensure you have a stable internet connection, and open up the cgs.py file
If you already have an account then click login, if you do not have an account then click create account
If you are logging in then enter your username and password into the designated boxes. After you have entered your information click the green ‘Login’ button to enter your information. If you enter incorrect information then an error message will be displayed on the screen in red and the entry boxes will be emptied. Try again. Be patient while logging in. The rainbow mouse may appear.
If you are creating an account then enter the username and password (into the corresponding boxes) that you desire. Then click the green ‘Create Account’ button. If an account with the given username already exists, or if the username is less than two characters or greater than seven characters then an error message will be displayed on the screen in red and the entry boxes will be emptied. Try again. Be patient while logging in. The rainbow mouse may appear.
Once you either login or create an account successfully, you will be re-directed to the home page of the CGS app. It shows your username in the top left corner. It also has three buttons corresponding to the three games currently available. Next to each game button are two record keepers that will keep track of your win, losses, and ties (respectively) for when you play in ‘Human’ mode (left) and in ‘AI’ mode (right). Those will be updated as soon as a winner (or tie) is established in any of the games that you play. To logout and exit the app, either click the green ‘Logout’ button in the top right corner or the red ‘X’ button in the top left corner. Both methods work the same way. Upon logging out, any ongoing game or change in your win/loss/tie records will be updated on the google sheet that houses all of the Capstone Game Suite user data.
To get started playing one of the games —
Simply click on the game button of your choice, and a new screen with a blank board will open unless you exited in the middle of a game last time and are resuming that same one.
Clearing a resumed game that you no longer wish to play —
Click the green ‘New Game’ button on the left panel of the screen. This will wipe the existing board.
Exiting out of the specific came and back to the main menu of game options —
Click the green ‘EXIT’ button on the left panel of the screen. This will autosave your progress. The red Quit button on the top left corner of the screen (built into your mac) will be disabled while on a specific game page, and will only work when the user is on the main menu.
To change the game mode you are playing in —
CAUTION — Changing the game mode will clear any existing game and you will not be able to resume it at another time. The game will by default open to ‘Human’ mode in which two humans alternate turns. To toggle the ‘AI’ mode in which the AI goes first and then you (the user) takes a turn, click the blue ‘AI’ button on the left panel of the screen. To switch back into ‘Human’ mode, simply click the blue ‘Human’ button on the left panel of the screen that is adjacent to the ‘AI’ one. Warning — this will wipe your current game.
To change the difficulty of AI you are playing against —
When you switch into playing against the AI (see above), the difficulty menu bar will automatically appear in purple underneath the mode selector. To alternate between modes, simply click the purple *, **, or *** buttons. One star represents an AI that searches in the future to a level of two. Two stars searches to a level of four, and three stars searches to a level of six. You can alternate between AI difficulties throughout the game without losing your progress. The higher the difficulty level that you choose, the longer it will take for the computer to make a move and the more the application will drain your computer’s battery. Bump up to difficulty 3 at your own risk :).
To start a new game after a winner has been determined —
Click the green ‘New Game’ button on the left panel of the screen. This will wipe the existing board.
Instructions for each game
Connect4
The goal of Connect4 is to place four of your pieces next to each other (vertically, horizontally, or diagonally). Each player will take their turn (the AI always goes first), trying to achieve this four-in-a-row. A user can drop one of their pieces per turn in any of the columns that are not already filled. Sounds simple? Put your skills to the test by playing in ‘AI’ mode. Warning — this game is very addicting. Whoever’s turn it is will be shortly displayed in the column dropper box after each turn.
Othello
The goal of Othello is to fill the board with your pieces. The game starts with four pieces in the center (two black and two white). When it is your turn, you may only place a piece that is adjacent to an opponent’s piece and therefore ‘flips’ the in- between pieces that belong to your opponent to your color. It can happen that by placing a piece, you create ‘sandwiches’ in multiple directions. In this case all of the in-betweens of all of the sandwiches are flipped to your color. CGS’s built in function shows you all of your permitted moves and places a number on each move (representing the number of pieces that you will gain from selecting that move). If a player has no available moves, their turn will be automatically skipped. The game is over when neither player has a legal move or when the board is full. At either of those points, the number of pieces on the board for each player is counted and the player with the greater number of pieces wins. Beware — the AI is looking into the future and not just at the present, so do not be surprised if it does not select the move that would award it the most pieces. Also, Othello is a fast paced game in which the suspected winner can chance very quickly. Whoever’s turn it is will be displayed at the top of the game board.
Checkers
The goal of Checkers is to jump over and capture all of your opponents pieces. The game starts with one player at one end and the other player at the other end. Each player will begin with 12 of their own pieces, laid out on the dark squares on their side of the board. Pieces can only be moved to and from the dark squares. Regular pieces (which you start with) can only move forward (towards the opposite end). You can click on any of your pieces to see the available moves. If a ‘capture’ move is available, it must be taken (all other moves will be hidden automatically by the computer). You may only jump over your opponent’s pieces (one jump per turn), and when you do, your collected counter at the side of your ‘home base’ will increase. The piece that you jumped over will be removed from the board. If your piece reaches the opposite row of the board, it will be crowned as a king. At this point, that piece gains the ability to move backward and forward. The game will continue until either one of the players has collected all of the other players’ pieces or until both players have 11 pieces left in which a tie is called, or until one player forces another player to have no moves (then that player who forced it wins). Whoever’s turn it is will be displayed at the bottom of the game board.
Slideshow Instructions
User has stable wifi connection, has used basic user interfaces with login/logout systems, and has python interpreter installed to run the cgs.py file
No sound effects while using game, moves do not fade in over a period of time — they just appear, no change password or delete account feature, no feature deciding who goes first, no offline feature and limited games.
All features mentioned above in the instructions should work. Logging in and out does take a few seconds though, so be patient. All single player games should work flawlessly. The Connect4 AI should as well. The Othello AI is pretty good but sometimes miscounts the number of moves or forgets one of the sandwiches if there are multiple. Still debugging this. I have not done extensive testing on the checkers AI, but conceptually it is sound.
In order to create more games, program them in their own python documents and add buttons that call the ‘main’ function of the given game/file name. Pass it the screen variable which is the pygame window. Further difficulty levels can easily be added by adding a button within the left_panel_event and draw_records functions. For these new buttons, simply change the number associated with the difficulty which will change the search depth of the minimax algorithm.
in-code documentation and function docstrings
Link to user data google sheet -- Check it out, its pretty cool!
Standard account dictionaries
['username', 'password', 'connect4_record_ai', 'connect4_record', ‘checkers_record_ai', 'checkers_record', 'othello_record_ai', 'othello_record', 'current_checkers', ‘current_connect4', ‘current_othello’]
game records — [wins, losses, ties]
current games —[[data model/board], turn, mode, difficulty]
status — 1 = logged in somewhere, 0 = not logged in anywhere
Connect4 Model
[[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
0= white (nobody), 1= user (red) , 2= opponent/AI (yellow)
Othello Model
[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 2, 1, 0, 0, 0], [0, 0, 0, 1, 2, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
0= green (nobody), 1= user (white) , 2= opponent/AI (black)
Checkers Model
[[0, 1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0], [0, 1, 0, 1, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 2, 0, 2, 0, 2, 0], [0, 2, 0, 2, 0, 2, 0, 2], [2, 0, 2, 0, 2, 0, 2, 0]]
0= (nobody), 1= user (blue) , 2= opponent/AI (black)
cgs.py file (functions that draw)
draw_homescreen --draws screen of login/create account
draw_main_page --draws menu page with game options
login --draws login/create account page where user enters data
draw_records --draws left panel for each game
Game Files
Each game has its own update_board function which takes care of the view and calls the various functions to update the screen.
Cgs.py -- functions dealing with retrieving/saving data to and from google sheet and local logged_in file
save_data,get_data_from_drive,serial, save_progress, setup_drive, left_panel_event (alters model for each game depending on left panel event)
functions that login and create account
submit_data, create_account
each game has its own move_piece or drop_piece function which alters the game model
connect4 --- def drop_piece(board_in, piece, column) — (drops the given piece into the given column in the given board)
othello --- def make_move(board, box, piece, options, middles) — (puts the piece onto the box and cross references with the options and middles lists to flip all of the in-between pieces)
checkers --- def move_piece(array, highlighted, box, switch, piece) — (takes the piece (whose turn it is) and the highlighted piece and moves it to the box and captures any switch if it exists. will also automatically switch to king)
Minimax in general —
The minimax algorithm is incorporated in order to build out a tree (to a designated depth) of all potential options and score each one of those options and then choose the best path accordingly. In the tree, the levels of its branches alternate from representing the AI and the user. The algorithm simultaneously tries to maximize the AI score when it is the AI’s turn and minimize the AI score when it is the user’s turn. Essentially, it is assuming that both the AI and the user are going to be making the best possible established decisions. This results in the algorithm being able to traverse the tree and find the best path to take and current move to make. Alpha beta pruning which is not currently being used in the checkers AI is used to set a ‘bar’ such that if it is exceeded, the tree building can stop and the current move that triggered the exceeding can be made. This is implemented in order to reduce runtime and improve efficiency of the AI decision maker.
Connect4 Example tree:
Scoring Mechanisms
Connect4
Every four piece combination is evaluated (vertical, horizontal, diagonal) and score according to its favorability. Four AI pieces receives 800, 3 AI pieces and 1 user piece receives 400, 2 AI pieces and 2 user pieces receives 2. 3 user pieces and 1 AI piece receives -350, and 4 user pieces receives -800. The scoring mechanism is set up to favor offense (getting four in a row) than defense (preventing user four in a row) as the absolute value of the best board for AI (800) is greater than the absolute value of the best board for the user (700).
Othello
The heuristic for the Othello AI is quite simple but effective. There were more complex considerations that I had added, but this simple approach had the best middle ground of accuracy and efficiency. It evaluates a board simply based on the number of AI pieces on the board. Because othello has to do with flipping and there is a direct correlation between pieces on the board and winning, this logic is coherent. However, because the algorithm searches to a designated depth and finds the best overall path, the AI may not pick the move that gains it the most pieces on that turn. It will pick the move that will result in the most pieces in the future. When it is the user’s turn in the minimax, it is trying to minimize the number of pieces that the AI has on the board. Essentially, the user is playing defense and the AI is playing offense.
Checkers
The heuristic for the Checkers AI, like the Othello one, looks at the entire board and scores it. The initial score is calculated as the total number of AI pieces minus the total number of user pieces. However, each regular piece is worth 3 points and each king is worth 5. Next, the piece positioning is taken into account according to the following board (right). A user piece contributes the corresponding negative value to the overall score. An AI piece contributes a positive score. This positioning prevents captures from taking place. Finally, the number of pieces that the ai has captured is multiplied by 10 and added to the score while the number of pieces that the user has captured is multiplied by 10 and subtracted from the score. This is in order to prevent the algorithm from choosing a path that is positionally adequate but not sound if you are trying to prevent captures. The initial board would have a score of zero after all of these calculations.
I think in addition to the complications that I left out, the next games to be added should be 3D connect4 using matplotlib to graph an interactive 3D environment and Super checkers. Eventually, chess should be incorporated as well. New features could include playing against other people across the internet or offering an offline mode so users can play on the plane. Also, improving the alpha beta pruning of the minimax algorithms will help with battery drainage.
import Pygame as pg, import Pickle, from math import pi, from random import randint, import sys, from passlib.hash import pbkdf2_sha256, import gspread, import ast, from oauth2client.service_account import ServiceAccountCredentials
pygame 1.9.4 -- Hello from the pygame community. https://www.pygame.org/contribute.html
NA
I did lots of boundary and edge condition testing for the three games where I basically tried to break the program. I will discuss some of the changes that I had to make to my program throughout the testing. Regarding connect4, I had to consider what would happen after a user selected a full column. Should their turn be skipped? Should it be an unavailable option? I sided with the second approach. I also had to incorporate a tie game scorekeeper (applies to all games). Regarding Othello, I was originally under different assumptions in terms of the rules and spent lots of hours figuring out a problem that was not actually a problem. It was a cool feature however that allowed the user to select the best sandwich instead of just institution the mega sandwich rule. I also had to incorporate what would happen when a user had no moves. I decided to implement the Othello rules as opposed to reversi and made it so the program automatically skips your turn if you have no moves. If both players have no moves then the game is over. Regarding checkers, I had to incorporate a function to show all available moves for those who don't know how to play. I also had to incorporate how to deal with a player who has no moves. I decided that at that moment, they lose. Lastly, I had to incorporate function to prevent users from selecting a non-capturing move when one exists.
The black box testing that I conducted was through sharing my program with friends and letting them interact with it. I watched every move they made and observed any confusion they may have had. A few things that I found and either fixed or did not are: People rely on the enter button to submit their information after they have typed it into the boxes. I wanted to implement and enter button but decided it was not worth my time because it would require re-arranging the entire function and how events are processed. Also, people were confused about how to switch the mode and difficulties of the game so I changed the colors of the menus and also implemented a feature that highlights the currently selected option. Regarding Othello, users were confused with what happened when their turn was skipped because it is not painted to the screen but rather printed in the console. This is something I want to fix but deemed not a priority right now. Regarding Connect4, my testers would get upset when the AI won because they could not see where the four in a row was so I added function to draw black dots on the winning four in a row move.
My positive testing included making various different accounts and playing games and scoring wins/losses/and ties using all of those accounts. There were some cases where positive testing failed because the score boards were being added to indefinitely after somebody won but hadn't yet restarted the game.
The biggest example of negative testing was in my development of the login/logout system. There is no built in typing interface in Pygame, so it was definitely a challenge figuring that out. I realized that in my programming of the typing interface I did not account for key clicks of command, option, tab, etc. I wrongfully assumed that the user would only enter letters and numbers for their username and password. For example, if you try to do CMD A to select all the text in the text window, it will simply add more text because the command prompts do not apply. Other examples of negative testing including making faulty or illegal moves within games.
To some degree. I spent so much time on this project and definitely would have done a lot of things differently. I was so focused on the design of the program and the interface features that I lost track of time and ultimately was not able to produce the strongest AIs. I definitely strengthened my previous connect4 which was one of my goals. I was also able to implement a great AI for that game. Othello pretty much met the goals that I set. There are some glitches that I have yet to fix as time just crept up like crazy. Checkers is good, but the AI has completely stumped me. I have plaid around with so many scoring mechanisms and it seems like the more I work on it, the worse it gets. In terms of learning and personal growth, I definitely achieved the goals. There are so many lessons that I learned throughout the development that I wish I had documented. Things like programming functions in different files before implementing them into the program, creating printing functions for testing the model, the importance of documentation, and the difficulties in incorporating new modules with skimpy documentation. There were also lots of pycharm tricks that I discovered which will surely help me later on and next year.
My goals changed in that I realized it was more important to focus on the games and the quality than the breadth of the app. I quickly realized super checkers and and 3d connect4 would simply be too much work to implement. Also, some of the cool features like parental controls and sound effects I decided were too extra. Honestly, I also started to feel a sense of burnout which contributed to a kind of slacking off. I am still proud of my program but because I was working on it for so long and got caught up in some of the less important aspects, my overall dedication suffered. This is definitely a lesson I will take with me in my future compsci pursuits.
As I mentioned, a sense of burnout started to develop around April after I finished Connect4 and most of Othello. Also, as my end of the year workload started to pick up, I became really limited in how much time I could devote to programming. Prior to April I had more long periods of time in which I could be very productive and get lots of the program done. I realized that I have difficulty getting part of the code done in a 30 minute sitting. I need time to process the issue that needs to be fixed and then figure out a solution. Most of my work was done between the hours of 10 PM and 1 AM in bed before bed. With all of that in mind, I still vowed to create the three games and some sort of AI decision making process for them.
Along with everything mentioned above, I started to realize that I was spending so much time on the program and only making small steps. I realized this was because I only worked on it at times when I was very tired and out of it. Also, I would get very carried away with researching packages and refactoring code blocks instead of innovating.
I did not expect the AIs, specifically for Checkers to be so difficult to create. Part of this was because I was running low on time, but I thought that coming up with the heuristics and implementing alpha beta pruning methods to increase productivity would be easier. I overcame this problem by watching lots of videos and downloading college course slide decks on these topics, but I still struggled in understanding and implementing these systems. Also, I was not as familiar with the rules of the games as I should have been when I started programming. This lead to lots of unnecessary work.
The AI issues were unanticipated because I had no idea what I was getting myself into when I pledged to create them. I am fascinated by the concept of artificial intelligence, so I figured why not start doing research now. Also, from a conceptual perspective, the articles that I have read and code that I have seen is relatively simple. But, applying the concepts to my situations was a laborious task and truly highlighted the accuracy of Hofstader's Law. With regard to the rules, there are so many different ways to play these games, and I used to play Othello with different rules than most I guess. Also, I guess I just forgot the fact that in Checkers you have to take the capture move if it exists.
To some degree. The AI encounter was less in my control, but I probably should have heeded to the advice and cautioning of Dr. Sharfman more than I did. He proposed implementing a heuristic or even random move generator as opposed to a minimax based approach. The game errors highlight for me how I did not get enough input from friends and family along the way. I personally prefer working alone but I definitely see why sometimes it is better to have multiple eyes looking over something.
There is not that much I would do differently. In terms of planning and setting goals, I do not think I was unrealistic with myself. There were obviously things that got in the way of me fulfilling all of the goals that I set forth, but I think its better to over achieve then settle. I would have tried to stay on par with my schedule a little bit better. I was doing pretty well and then all of the trips in march and the ACT in April and whole lot of other things got in the way and kind of disrupted the flow that I had going. I did not take into consideration how much harder 11th grade gets as it goes on.
I would definitely use a very similar plan, except I would have liked to achieve the same level of excellence with my checkers AI as I did with the connect4 one. I also would have wanted to implement 3D connect4 and super checkers. I think those would be awesome games that could be unique to the CGS app. Lastly, I would add all of the UI enhancements that I discussed in my proposal. These included sound effects, parental controls, unlocking prizes, screen-time usage updates, and other cool things. Lastly, I would create an offline version so users can play even if they do not have wifi.
Yes and so much more. I learned so much from this project. So many tips and tricks for programming an app with multiple files and even little things that can often go unnoticed and are considered subconscious learning. On top of these more literal learning elements, I also learned how to create a proposal, construct a plan, conduct research, and pace myself throughout a long project.
I think a huge part of the reason this project was ‘successful’ is because it was so open ended. There were few check-ins and you really had to be on top of your game without reminders. Also, because everyone was allowed to build something that they thought was cool and interesting, there was a greater personal stake in it which ultimately leads to more efficient and productive learning.
NA
A few of the specific computer science lessons that I learned were creating print functions so you can easily turn on and off the printing of the model during testing, writing functions and small blocks of code in a separate file in order to check that they work before implementing into the larger system, writing good documentation, sticking to familiar and simple variable names (I had many errors in spelling sandwiches differently), developing a program to print the model at any given moment, and a function to display the model in the user interface at any given moment. Another big thing I learned was how to refactor. Because my program has multiple files and lots of overlap, I was able to scan through all the files and functions and compile some of them into shared ones. This was super cool and really highlighted the efficiency of repurposing code blocks into re-callable functions.
As previously mentioned, the lessons of how to plan out an entire 6 month project was super informative. Learning how to write inspiring and persuasive proposals, as well as detailed game-plans that are honest and accurate is not an easy skill. This project served as great practice. Next, undertaking personal research and finding ways to incorporate your interests into your work was another general lesson derived. Lastly, time management was huge. When working alone (which I prefer), there is nobody pushing you to work you to your best self. This means that there is a huge element of personal responsibility in keeping up with your schedule and ensuring that you do not fall behind on small issues.
This project has taught me so much. Whether it is how do deal with and anticipate problems or more profound computer science topics and algorithms, this experience has been one of sheer transcendence. I have never worked on a project for six months and completely on my own. It has been super empowering and transformative. I learned to embrace the grind of the completing the nitty gritty and the importance of intentional and well thought out programming. The hours and hours and hours and hours of work put into it did not necessarily manifest only in the project itself, but also in the countless ‘little things’ that I picked up on and have incorporated into my work ethic, ultimately highlighting the self growth proponents of this project and the tangible lessons that I will carry with me in my future computer science endeavors. The power of learning from experience is the major takeaway for me. Having to pitch an idea, construct a game-plan, conduct research, plan a timeline, and program an entire app, all while adhering to strict personal deadlines has been the pinnacle of my entire education thus far. I have studied the scientific method in class, but implementing it into my life by taking on a serious project was so awesome. I commend your flexibility in the project and truly allowing every student to do something that they want to do. I could not have imagined a better way to end of the year and showcase all of the material that I have learned. Thank you for this incredible experience!