Connect Four AI
Background
Game AI has a long history—in fact, the field of artificial intelligence (AI) was motivated (in part) by the belief that building programs that could play strategic games well would lead to human-level intelligence.
It turns out that that belief was not true: human-level intelligence is not, fundamentally, about strategic thinking in rule-based contexts like games.
However, the applications of game AI are more than only games. Techniques for finding the best outcome by searching through possible situations (such as game moves) are at the heart of AI and have application in planning problems of many types:
- Robots planning for what actions or motions to make next.
- Decision planning that models or simulates complex interactions among artificial agents (and, sometimes, human ones…).
- Adaptive systems that adjust to user’s responses, e.g., for practicing skills in a new field (education and training).
Overview
The Board Class
Either use your board from before or the starter code below.
The Player Class
The main focus of this project is to implement another class related to Connect Four. You should add the Player class in the same file as the Board class.
The job of the Player class is to evaluate Connect Four board states and decide what move to make. The basic approach is as follows:
- Look at each column on the board. Give each column a numeric score.
-1.0for a column that is full.0.0for a column that, if chosen, results in a loss.50.0for a column that, if chosen, doesn’t immediately lead to a win or loss.100.0for a column that, if chosen, results in a win.
- Make a move using the column with the greatest score. If the maximum score is held by more than one column, one of the following strategies is used:
'LEFT'picks the leftmost high score.'RIGHT'picks the rightmost high score.'RANDOM'picks one of the high scores randomly.
Implementing the Player Class
Your Player class should have at least these three data attributes:
- A one-character string representing the checker, either ‘X’ or ‘O’, being
used by the Connect Four
Player.WarningRemember to be careful to use
'O'the capital letter, not zero! - A string, either
'LEFT','RIGHT', or'RANDOM', representing the tiebreaking type of thePlayer. This is the name for one of the three strategies described above. - A nonnegative integer representing how many moves into the future the player will look in order to evaluate possible moves. We’ll refer to this quantity as
ply.
Your Player class should have the following methods:
def __init__(self, ox, tbt, ply):
This is a constructor for Player objects that takes three arguments. First, it takes in a one-character string ox. This will be either 'X' or 'O'. Second, it takes in tbt, a string representing the tiebreaking type of the Player. It will be one of 'LEFT', 'RIGHT', or 'RANDOM'. Third, ply, is a nonnegative integer representing the number of moves that the player should look into the future when evaluating where to go next.
Inside the constructor, you should set the values of the object’s data attributes. There’s not much else for this method.
def __repr__(self):
This method returns a string representing the Player object that calls it. This should simply print the three important characteristics of the object: its checker string, its tiebreaking type, and its ply.
def opp_ch(self):
This method should return the other kind of checker or playing piece, i.e., the piece being played by self’s opponent. In particular, if self is playing 'X', this method returns 'O' and vice-versa.
def score_board(self, b):
This method should return a single float value representing the score of the input b, which you may assume will be an object of type Board. This should return 100.0 if the Board b is a win for self. It should return 50.0 if it is neither a win nor a loss for self, and it should return 0.0 if it is a loss for self (i.e., the opponent has won).
def tiebreak_move(self, scores):
This method takes in scores, which will be a nonempty list of floating-point numbers. If there is only one highest score in that scores list, this method should return its column number, not the actual score! Note that the column number is the same as the index into the list scores. If there is more than one highest score because of a tie, this method should return the column number of the highest score appropriate to the Player’s tiebreaking type.
Thus, if the tiebreaking type is 'LEFT', then tiebreak_move should return the column of the leftmost highest score (not the score itself). If the tiebreaking type is 'RIGHT', then tiebreak_move should return the column of the rightmost highest score (not the score itself). And if the tiebreaking type is 'RANDOM', then tiebreak_move should return the column of the a randomly-chosen highest score (yet again, not the score itself).
One possible way to write this method is to first create a list of indices at which scores contains its max element. For example, if scores consisted of [50, 50, 50, 50, 50, 50, 50], then max_indices would be [0, 1, 2, 3, 4, 5, 6]. On the other hand, if scores was the list [50, 100, 100, 50, 50, 100, 50], then max_indices would be [1, 2, 5].
def scores_for(self, b):
This method is the heart of the Player class! Its job is to return a list of scores, with the cth score representing the “goodness” of the input board after the player moves to column c. And, “goodness” is measured by what happens in the game after self.ply moves are made.
Admittedly, that is a lot to handle! So, here is a breakdown:
Create a list (maybe called
scores) with length equal to the number of columns in theBoardb, with every element set to50. Remember that you can use list multiplication:[50] * b.width.Iterate over all possible columns:
Base Case If a particular column is full, it assigns a
-1.0score for that column.Base Case If the game has already been won for
self, then there’s no point in making any additional moves (indeed, it’s not allowed!) simply use the appropriate score (100.0) for the current column under consideration.Base Case If the game has already been won for
self.opp_ch(), then there’s also no point in making any additional moves. Simply use the approproate score (0) for the current column under consideration. It’s important that the check forself’s win occurs before the check for the opponent’s win, because there are boards where both are true—butselfgets to move first!Base Case If the object’s
plyis0, no move is made. What’s more, if you’ve handled the “column full” and “game over” cases above, there’s only one score left to give the column with aplyof0.Recursive Case If the object’s
plyis greater than0and the game isn’t over, the code should make a move into the column that is under consideration. This will use some of the methods inBoard. In addition, it’s a good idea to check if the new, resulting board has ended the game. If so, give the column the appropriate score.
Once that move is made, if the game is not over, the crucial task is to determine what scores an opponent would give the resulting board.
This means creating an opponent (which will be of Player class!). How to create an opponent? You can simply establish a new object of type Player! For example, op = Player(self.opp_ch(), ..., ...). It’s safe to assign this to-be-constructed opponent Player the same tiebreaking-style as you use—that is, the same as self.tbt. What is the correct value of ply to give it? Once you’ve created an opposing Player, you should use recursion to obtain the seven scores that the opponent would give to its next move.
However, the scores reported by the opponent are NOT the scores that self should use! After all, the opponent has a different goal than self! Rather, you will want to figure out which score out of the seven the opponent, op, would choose. Then, compute the score you (self) would obtain: this will be 100 minus the opponent’s best score. Finally, assign the resulting score to the value of the current column’s move.
Be sure to delete the checker that had been placed throughout the evaluation of this particular column!
Once all of the possible moves have been evaluated, the scores_for method should return the complete list of scores, one per column. So, in a seven-column board, there will be seven numbers in the list returned.
def next_move(self, b):
This method accepts b, an object of type Board, and returns an integer—namely, the column number that the calling object (of class Player) chooses to move to. This is the primary interface to Player, but it is really just a “wrapper” for the heavy lifting done by the other methods, particularly scores_for. Thus, next_move should use scores_for and tiebreak_move to return its move.
def play_game(self, px, po):
This method calls the next_move method for two objects of type Player in order to play a game. Those objects are named px and po.
Feel free to write play_game on your own, if you’d like the challenge! Or, feel equally free to use the one that’s in the starter code provided above.
Either way, there’s one additional twist to play_game: you should test your Connect Four-playing code by playing games both against itself and against a person. That is, if px or po is the string 'human' instead of an object of type Player, then play_game pauses and asks the user to input the next column to move for that player, with error checking just as in host_game.
Testing the Player Class
__init__ and __repr__
opp_ch
score_board
tiebreak_move
scores_for
0-ply lookahead doesn’t see threats…
1-ply lookahead sees immediate wins (if only it were ‘O’s turn!)
2-ply lookahead sees possible losses (‘X’ better go to column 3…)
3-ply lookahead sees set-up wins (‘X’ sees that col 3 is a win!)
At 3-ply, ‘O’ does not see any danger if it moves to columns on either side…
But at 4-ply, ‘O’ does see the danger! Again, too bad it’s not ‘O’s turn…
next_move
play_game
Some deterministic examples:
Extensions
You can choose one of the three extensions to add to your Connect Four.
Graphics
For this extension, use pygame to create a playable version of Connect Four—along with your AI.
The design of this is up to you, but your result should:
- Allow the user to play either ‘X’ or ‘O’ (however they’re represented).
- Allow the user to choose a difficulty level (the
plylevel at which the AI plays). - Allow the user to tell the computer to play against itself (at two different levels, if desired).
- And, it should play against the user and recognize when the game ends in a win, loss, or tie.
Details are wide open here—we welcome your creatively-themed Connect-Four implementations.
Be sure to include a description of how to play your Connect Four!
Static Board Evaluation for AI
Since n-ply lookahead is the same for every player, AIs vary not based on their search, but on their evaluation of the board at the end of the search—i.e., when the game is neither a win nor a loss.
Our overview, above, suggests weighting those boards at 50 (on a 0-100 scale), but much more sophistication is possible. A function that is more careful about scoring these non-win/non-loss board states is sometimes called the “static board evaluator,” because it looks only at the board’s current status. It’s these static evaluators that distinguish the abilities of two different game AIs. Static board evaluation tries to capture humans’ “intuition” about a game, and it is used by all computer game-players in all types of games, from Hydra, a very good computer chess player to Go-playing programs. Things like computer poker players do the same thing, but they model more than just the game state. The probabilities of future states, along with the tendencies of other players, are modeled as well.
So, for this option, you should allow the user to play in two different modes: plain evaluation (how the AI works now) or savvy evaluation.
With the savvy evaluation, you will implement a static-board-evaluation function that is more sophisticated than the 0-50-100 version.
Here, create a new score_board_tourney function (but save the old one, in case anything goes wrong!)
This new score_board_tourney should return a more accurate evaluation of how good or bad board b is for self.ox—more accurate than the simple 0-50-100 scoring of the default Player used.
The new score_board_tourney(self, b) may NOT look further ahead into possible future moves—rather, it should take into account factors like:
- How central are my pieces compared to my opponents’ pieces?
- Do I have any (unblocked) 2-in-a-row runs? Or does my opponent?
- Similarly for (unblocked) 3-in-a-row runs.
- And any other factor about the current board you might want to compute…
The only constraint on score_board_tourney(self, b) function is that it should return a number (a float) for each board provided, with higher numbers indicating a better board (for self.ox). Since this is evaluating a board and not a column, it’s ok to use negative numbers to represent really bad boards… That said, some people find it easier to reason about board-scores on a 0-100 range (0 = loss, 100 = win). Also, you should assume the board will be 7 columns and 6 rows, as in the standard version of the game.
You’re welcome to use randomness in score_board_tourney(self, b) function, if you’d like.
How to test your score_board_tourney function?
Copy-and-paste your
scores_formethod and name the copyscores_for_tourney. Change the old code:To the new version:
and then play against it yourself or play it against other players you construct from the
Playerclass.
Be sure to print out the scores you’re computing, to see if they match your intuition!
Your Own Game
For this option, revise the rules of Connect Four. Or, even more ambitiously, you’re welcome to create another two-player game—presumably one that uses a 1d or 2d board!
Then, adapt the Board and Player classes to implement your alternative game! Be sure to do this in a different Player and/or Board class: choose a new name that fits!
If you’d like to take this path, we would recommend changing the rules of Connect Four—at least at first. For example, you could add any one of these variations:
- Add a chance (perhaps 10%) that the game randomly ignores the move you choose and chooses a different allowable move…
- Randomly swap an X with an O every once in a while!
- Allow the user to “flip” the board—as if it rotated 180 degrees (and the checkers don’t fall out!)
- Have a row of checkers disappear when it’s entirely full (Tetris-style—leads to interesting strategies!)
- Have gravity go “diagonally” !
- Many other variants are welcome (and, importantly, feasible…)
Be sure to include a note explaining your game and how to play.
If you choose this extension, free to simply add more classes to you Python file—or include a second .py file…