Cartesian Coordinates
If you know some basic maths, programming Cartesian coordinates changes a little bit your mindset. Usually, you put the X axis horizontally and the Y axis vertically. Going to the right means a greater value for the X coordinate and going to the left means a lower value; while going up means a higher value for the Y coordinate and going down means a lower value on that coordinate. When we program, it isn't always like that. Usually, the origin (0, 0) is at the top left corner on the screen, and while going to the right still means a greater value for X, going down now means a greater value for Y. It might sound confusing at first, but you get used to it very quickly.
However, this isn't a problem I struggle with when working with a Cartesian coordinate system. I do have experienced a little bit of confusion while I was reverse engineering the Reversi game. The board uses a Cartesian coordinate system, being the top left corner the origin. The problem comes when you have to assign values to the coordinates and then display them.
Let's imagine we want to assign different values to each place on the board. The code could look something like this:
for x in range(row_size):
for y in range(column_size):
matrix[x][y] = value
Imagine that row_size = 2 and column_size = 2. The result would be something like:
matrix[0][0] = value for 0, 0
matrix[0][1] = value for 0, 1
matrix[1][0] = value for 1, 0
matrix[1][1] = value for 1, 1
It makes perfect sense. The first coordinate (x) comes first and then the second one (y). Nevertheless, if we tried to print the board following the same fashion:
for x in range(row_size):
for y in range(column_size):
print_on_board(matrix[x][y])
We end up getting something like this:
|
Value for 0,0
|
Value for 0, 1
|
|
Value for 1, 0
|
Value for 1, 1
|
If we use the previous algorithm, the computer will swap the X and Y axis. We don't want that happening. In order to avoid that we must use the following code:
for y in range(column_size): # Print each row
for x in range(column_size): # Print each value on the same row
print_on_board(matrix[x][y])
This way, we would get the desired result.
AI and Minimax
Chapter 16 of “Invent Your Own Computer Games with Python” by Al Sweigart deals with AI simulations. I've done many simulations in the past, in fact, in this very blog you can look at some I made about the Risk tabletop game. At university I had a few subjects about Artificial Intelligence and I thought it was a good idea to apply something about Game Theory in a game like Reversi. So, I decided to implement my own AI for Reversi. I've implemented the Minimax algorithm.
In very rough terms, Minimax is about choosing the option that gives us more profit taking into account that our adversary will choose the option that will give us the least. Let's imagine that in a certain game I could choose between two options: A and B. If I choose A, my opponent can choose between giving me 3 points or 2 points. If I choose B, the opponent can choose between giving me 20 points or 0. In this example, we minimize damage by choosing option A. Minimax considers that the opponent will choose 0, so it's better to take at 2 (in the worst scenario after going for A) than 0 (even if we know that by choosing B we have a chance of getting 20!). A human being might attempt to choose B hoping that his opponent will choose to give him 20 points by mistake, but that's not the way machines think.
In Reversi, we usually have more than 2 options (legal moves) and the game involves more than just one decision for the player to take (it easily lasts 40 moves). In other words, the depth of the search for the solution is greater. In the previous example, the depth is one. We analyze only one move forward for the player and one for the opponent. My AI implementation will analyze 4 moves forward. The benefit for a move will be the number of tiles turned by that move unless we're talking about a corner. My Minimax implementation will assign an infinite benefit to corner moves (in all simulations that I've made before it's clear that getting the corners is always in our benefit). Being this, implemented in Minimax means that the AI will also avoid the opponent claiming them!
You can download the source code for the simulation here, and if you just want to play against the computer (which will use Minimax) you can download the source code here. Remember that these codes are a variation of the ones in the book.
These are the result for the simulations (X is the book's AI and O is mine):
Welcome to Reversi!
Enter number of games to run: 350
Game #0: X scored 31 points. O scored 33 points.
Game #1: X scored 25 points. O scored 37 points.
Game #2: X scored 37 points. O scored 27 points.
Game #3: X scored 32 points. O scored 31 points.
Game #4: X scored 47 points. O scored 17 points.
Game #5: X scored 34 points. O scored 29 points.
Game #6: X scored 27 points. O scored 37 points.
Game #7: X scored 30 points. O scored 34 points.
Game #8: X scored 21 points. O scored 43 points.
Game #9: X scored 21 points. O scored 41 points.
[skipped for brevity]
Game #340: X scored 26 points. O scored 22 points.
Game #341: X scored 32 points. O scored 32 points.
Game #342: X scored 30 points. O scored 34 points.
Game #343: X scored 32 points. O scored 32 points.
Game #344: X scored 38 points. O scored 26 points.
Game #345: X scored 39 points. O scored 22 points.
Game #346: X scored 20 points. O scored 44 points.
Game #347: X scored 18 points. O scored 46 points.
Game #348: X scored 18 points. O scored 46 points.
Game #349: X scored 21 points. O scored 43 points.
X wins 94 games (26.86%), O wins 243 games (69.43%), ties for 13 games (3.71%) of 350.0 games total.
You can download the whole log here. I didn't run more than 350 games because I don't have that much computation time available and it's a fairly big number anyway. In any case, it seems unquestionable that my AI beats the one shown in the book (it wins almost 70% of the games!).
From ASCII Art to Pygame Art
This is my way of saying "Hello World!" with Pygame (see picture below).
Download the source code here.
No comments:
Post a Comment