Developing a Developer: Weekly Report 4

I've read the second part of the 17^th chapter (which covers animations) and the entire 18^th chapter (which covers input). This week I've decided to change the Reverse Engineering phase I did in the previous weeks. Now, either I improve the program (in the way I did making a new AI for Reversi) or I made my own program. In fact, I've done many pygame tests this week and I think the best way to show my current skills is through a video.

Rotating Ball

You can download the script here.

It's just a ball that bounces across the screen. The most interesting part about it is that I used polar coordinates for the mark that gives the impression of rotation and them I transform them into Cartesian coordinates in the following way:

x = r * cos(o)

y = r * sin(o)

x, y = Cartesian coordinates

r = distance from the centre of the ball to the centre of the small mark (which is a circle, by the way)

o = angle that constantly increments or decrements depending on the rotation direction

Spiral

You can download the script here.

OK, drawing a ball is easy, because Pygame has a built-in function called “pygame.draw.circle” which does the job for us. In order to draw a spiral, I've implemented a class which contains the formula of the spiral and remembers the value of the always incrementing angle in polar coordinates. Outside this class, in the game loop the angle is incremented and a straight line is drawn from the previous point to the new point calculated using the nextPoint method in the spiral class.

There are a few more sophistications that you can find in the source code, but I find particularly interesting the precision attribute in the spiral class. This attributes set the increment of the angle in polar coordinates and thus it will determine the smoothness of the line. It might be confusing, but since the precision attribute determines the increment of the angle, the slower it's value the higher the actual precision is going to be (counterintuitive, my mistake). See the pictures below.

Spiral: PRECISION = 1

Spiral: PRECISION = 0.005

Balls and Input

You can download the script here.

I basically take the rotating ball I've explained above and wrapped it into a class. Then, each time the player clicks on the screen, I call to the class constructor and create a new ball with new attributes. That way, I can have many rotating balls with different attributes such as speed, direction, rotation direction, etc. I confess I enjoy clicking and clicking insanely into the screen.

clickBall.py

Platforms

You can download the script here.

In this test I've had many headaches. It works with both input and collision detection in the context of a platforms game. The code is a little bit long to explain everything here, so I'll explain directly the most difficult function:

def controlFalling(self, rects):

    # control jumping

    if self.jumping:

        self.rect.top -= self.JUMPSPEED

        self.jumped += self.JUMPSPEED

        if self.jumped >= self.MAXJUMP:

            self.jumping = False

            self.falling = True

        # check if we hurt our head with some sort of ceiling

        collisionCeiling = 0

        for r in rects:

            if self.rect.colliderect(r):

                collisionCeiling = r.bottom

        # if this is the case, correct position

        if collisionCeiling > self.rect.top:

            self.rect.top = collisionCeiling

            self.jumping = False

            self.falling = True

    # fall

    else:

        self.rect.bottom += self.FALLINGSPEED

    # see if rects collide and detect current ground

    collisionGround = self.floorY

    for r in rects:

        if self.rect.colliderect(r):

            collisionGround = r.top

    # if the object is in the ground, correct it's position

    if collisionGround < self.rect.bottom:

        self.rect.bottom = collisionGround

        self.falling = False

 

There are two cases to consider.

a) The object is jumping

b) The object is falling

In both cases, I firstly move the object (upwards if it's jumping and backwards if it's falling) and then I see if it's colliding with something. If this is the case, I correct the position of the object, for I don't want to display it overlapping with anything. In the case of jumping, we also stop the jumping boolean attribute of the player, because the player must fall (although he could grab something in the ceiling and hang... Mmmm... Maybe for another test).

Developing a Developer: Weekly Report 3

I'm on chapter 17. The Pygame part has started. This week has been interesting.


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.

Risk simulation: conquering a territory

In previous posts I've showed the probabilities of succeeding in a single attack. In today's post, we'll see how difficult is to conquer an enemy territory. Just as a reminder, you can download the game instructions here. For this simulation, you can download my Python script here.

The simulation will tell you the chances of conquering a territory given the total amount of attackers and defenders. The defenders will be the number of armies in the enemy territory. The attackers will be a number of armies the attacking player wish to risk. So, if you have 7 armies in a territory that is going to attack an enemy territory but you want to make sure that you leave always 4 armies in your territory, you would set the attackers argument to 3 (i.e. 7 – 4 = 3).

During the simulation, I will assume that the attacker will attack with the maximum amount of armies he's willing to risk. The defender will act in the same way (we've concluded in previous posts that it's better to attack using as many dice as possible).

As I did in a previous post, here the simulation will be repeated a number of times to return more accurate data.

Let's prove our intuition. The probability of succeeding in a single attack with one dice against one defender is 41.6667%. So, if I run the program with one attacker and one defender I should conquer the territory a 41.6667% percent of the times or so.

As you can see, the conquest rate is 41.682% (very close to 41.6667%) in a population of one million simulations. However, we already knew that (the result was predicted). Let's try more complex scenarios:

As one should expect, the more armies defending a territory, the harder is going to be the conquest. I've been puzzled for a minute with the results on the losses. In the second to last simulation on the image above, the probability of conquering the territory is around 29.813%, but the defender expects more losses than the attacker. After thinking about it, I find it logical, because even thought the probability of conquest is below 50%, it is taken into account more cases in which the defender losses more armies (i.e. in case of conquest the defender will lose more armies and even if the attacker doesn't conquer the territory, there is also a case in which the defender loses 6 armies, more than the attacker).

We can also conclude that more armies involved in the attempt of conquest will be translated in more casualties (in both sides).

Finally, we already know that attacking with 3 dices will be a likely victory (whether the defenders uses 1 or 2 dices). In the past, I've experienced situations in which two players put many armies in only one territory menacing the other player but never attacking and expending many reinforcements in the business... They were wrong. Be the first one to attack. Let's see it with big numbers:

It took my computer a while to finish this one! Conclusion: as we wanted to prove, even if the enemy outnumbers (not by a huge amount of armies) you, it's better to start the attack.

Warehouse simulation

Today I'll share with you a warehouse simulation I had to do a month ago.

Let's consider a warehouse of a specific product whose sale price is 2€ per unit. Customer visits are distributed like a Poisson process (0.5 customers per hour) and the amount of products that each customer wants follows this distribution:

Request	1 unit	2 units	3 units	4 units
Probability	0.3	0.4	0.2	0.1

In order to satisfy the demand, the owner of the warehouse keeps a stock of products. When the inventory is low, he asks the distributor for more units. The orders policy is periodic. When the inventory is fewer than 30 and there aren't any pending orders, the owner asks for more units in a way that the inventory would end up having 100 units.

In each order there's a base price of 10€ (it doesn't matter the amount of units the owner asked). Additionally the cost per unit included in the order will depend on the amount of units asked. If the amount of units requested is less than 50, the price will be 1€/unit. However if the owner asks 50 or more units, the price would be 75 cents per unit.

The delivery time follows a normal distribution (with a mean of 48 hours and a standard deviation of 0.8 hours). The delivery will be paid as soon as it arrives. An agreement with the provider entitles us with a discount of 0.01% for every three hours of delay in the delivery. On the other hand, it will be 0.01% more expensive for every three hours it arrives sooner.

The owner of the warehouse spends 0.1€ per product each hour (due to physical storage, refrigeration, …).

If the customer asks for a greater amount than what is available, the warehouse sells all it has.

a) Simulate the behaviour of the warehouse during 5 months. Estimate the expected profits, the proportion of completely satisfied customers and the percentage of time the inventory remains zero. Let's assume the initial inventory is 70 units of product.

b) Represent graphically the evolution of the inventory level during the mentioned 5 months.

c) Try to identify what changes you could implement to improve the behaviour of the inventory model (get more profits and more satisfied customers).

For the first question, I've programmed a Python script. In order to run it, you need to have installed the NumPy library. I'll show you the output of a few simulations:

 

This is the graph that represents the evolution of the inventory. For this question, I commented the final part of the code (when the results of the simulation are printed) and put at the end of each iteration a line of code that printed in one line the stock available. Then, I used LibreOffice to plot the graphic. Maybe I should use better tools and techniques the next time.

For the last question. There's an obvious way to reduce the losses: sell all the stock and forget about new orders. That way, we don't have order expenses and we keep maintenance to a minimum. Of course, we'll have a lot of potential losses (a lot of unsatisfied clients), but it's the best way to solve this problem that I've found so far (maintenance is too expensive!). Nevertheless, I challenge the reader to get better results. Mine are these:

Don't change the product sale price, that's cheating.

Risk simulation: attacker vs defender

Risk is a very famous strategy board game. In the game, you conquer your opponent's territories by attacking them with armies. However, you can lose them in the attempt. In order to represent this uncertainty, the game is played with dice.

Quoting Wikipedia, these are the rules for attacking a territory:

When it's a player's turn to attack, he or she can only attack territories that are adjacent or connected by a sea-lane to his or her own territory. A battle's outcome is decided by rolling die. The attacking player attacks with one, two, or three armies, rolling a corresponding one, two or three dice. At least one army must remain behind in the attacking territory not involved in the attack, as a territory may never be left unoccupied. Before the attacker rolls, the defender must choose to resist the attack with either one or two armies (using at most the number of armies currently occupying the defended territory) by rolling one or two dice. Each player's highest die is compared, as is their second-highest die (if both players roll more than one). In each comparison, the highest number wins. The defender wins in the event of a tie. With each die comparison, the loser removes one army from his territory from the game board. Any extra dice are disregarded and do not affect the results.

I've made a Python script that simulates a single attack. Download it here.

Run the script like this:

python risk.py -a number1 -d number2 [-n number3]

Examples:

python risk.py -a 2 -d 1

Simulate a situation in which the attacker will use two armies and the defender only one.

python risk.py -a 2 -d 1 -n 1000

The same as previous, but this time the experiment will be repeated 1000 times and the program will report to the user the number of wins as well as it's percentage. Remember, the more you repeat the experiment, the more accurate the results will be.

Since I want solid information, I will simulate each one of the 6 cases 1000000 times. I takes a few seconds in my computer (Intel® Core™2 Duo CPU T5750 @ 2.00GHz × 2 and 3.0 GiB of memory).

Cases in which the defender uses a single die:

Cases in which the defender uses two dice:

NOTE 1: In the output of the program, a "tie" is when both players lose one army. Remember that in each die comparison, the defender will win the ties. So rolling 5 for the attacker and 5 for the defender counts as a win for the defender. What I call "ties" in the simulation would be something like this:
Attacker roll 6 and 1.
Defender roll 5 and 2.
Defender loses 1 army (6 beats 5) and attacker loses 1 army (2 beats 1).

NOTE 2: The simulation doesn't tell you if you've conquered the territory. For example, if you have 4 armies and you lose one trying to conquer the defender, you still will be able to use two armies to strike again. This situation is not contemplated. It only simulates the first attack.

In conclusion:

- When the defender uses 2 dice, there's a great chance for both opponents to lose one army (at least more than I was expecting, for me this is a surprise). Never defend with one army if you have the chance. In the past, I used two dice to make the game more dynamic, although I had doubts about if it was always the right decision. Now science tells me I have to use two armies to defend my territory. The probability of a tie is so high that it significantly whips away the security of the enemy.

- Attack the weak with all the might of your empire! If you can attack with three armies and the enemy territory is protected only by one, smash it!

- I've lived the situation in which both opponents start putting armies to threaten an enemy territory and the other one puts the same amount only to return the threat, but no one attacks (possibly in the belief that defending is more profitable than attacking). Wrong. If the situation arises, start attacking with three armies. Obviously, stop when you lose the possibility of attacking with three armies if the defender can still cast two dice.

- Don't attack with only one army.

- Always use as many dice as you can (unless you're splitting your army for some reason, but keep in mind chances are you're going to be less efficient).

These information is very poor and it won't increase significantly the chances of wining the entire game. However, it's a start. I might post more about this in the future.