SET Game Visual Solver

For those of you that have never played SET® before, SET® is a fast-paced game involving 81 unique cards with different combinations of four characteristics (color [red, green, or purple], shape [diamond, oval, or squiggle], shading [hollow, shaded, or filled], and number [1, 2, or 3]). The point of the game is to find as many 3-card “sets” as possible. If the three cards are either all the same or all different in each of the four characteristics, you know you’ve found a set. Twelve cards are presented on the table at a time, and are continually replenished when a set is taken out, until no cards remain in the deck. Sometimes, however, there are no sets in the twelve cards, in which case 3 more cards are dealt. But, how do you know if there really is no set? I aim to solve this problem using image processing software and eventually create a set recognition mobile application.

So, what determines a set? Let’s take the example below (although it is probably one of the most difficult sets in the game). Looking at the cards in terms of the four characteristics, we have the following: color – red, green, and purple (all different); shape – diamond, oval, and squiggle (all different); shading – filled, hollow, shaded (all different); number – 1, 2, 3 (all different). If the cards were exactly the same, but all red, this would also be considered a set, because, in terms of color, they are all the same.

 

There’s the simplified breakdown of how I used an image processing algorithm to determine sets from ordinary jpeg images:

Step 1: Convert the image to black and white and invert the image to calculate the number of shapes per card

Step 2: Compare the pixel surface area of one of the symbols on each card to determine the shape

Step 3: Normalize the RGB color of the images with an equation to figure out the color

Step 4: Convert the images to gray scale and apply a border detection to determine the shading

Step 5: Run the simple algorithm that deduces the sets

For more details, check out the paper I wrote.

BlackJack Hitting vs. Standing chances

Who has never thought about beating the house in a Casino? As the MIT students said in their documentary Breaking Vegas, it’s not all about the money; but about the feeling of beating a huge corporation in their own game.

It’s very easy to find online the basic strategy for BlackJack, i.e., the correct decision when the only information that you have about the game are your cards, and the dealers facing card. Understanding by correct decision, the one that would minimize your losing chances. Even with this basic strategy the odds against the house are negative, but greatly reduced to a mere -3 $ per 100$ played (aprox). Of course the Breaking Vegas students didn’t just played basic strategy, they also counted cards and played in a team not to raise any attention from the Big Brother.

For this post, I wrote a small Python notebook that computes what are the chances for the different combinations of cards and strategies in their most simplified way, standing and hitting.

The full notebook: https://github.com/Koff/blackjack/blob/master/blackjack_simulation.ipynb

And the results in two images:

 

On the Y-Axis, the starting score of the player, and on the X-Axis, the dealer’s facing up card (11 being the Ace). The color and values represent the chances of winning if the following the strategy.

APAC Country List

This is probably the most stupid post of this website up to the moment, but I couldn’t find the information anywhere else; so here it is, the list of country codes for the Asia Pacific region (APAC) and it’s two letters ISO equivalent.

Australia,AU
Brunei,BN
Cambodia,KH
People's Republic of China,CN
Hong Kong,HK
Macau,MO
Fiji,FJ
Indonesia,ID
Japan,JP
Kiribati,KI
North Korea,KP
South Korea,KR
Laos,LA
Malaysia,MY
Marshall Islands,MH
Federated States of Micronesia,FM
Nauru,NR
New Zealand,NZ
Palau,PW
Papua New Guinea,PG
Philippines,PH
Samoa,AS
Singapore,SG
Solomon Islands,SB
Thailand,TH
Timor-Leste,TP
Tonga,TO
Republic of China (Taiwan),TW
Tuvalu,TV
Vanuatu,VU
Vietnam,VT

Maybe it will save someone’s 5 mins.

Car Accelerometer Project using Proteus

In this post, I am presenting one of the projects I did for a class. The idea was that we could set up a micro-controller with two accelerometers on a car so we could get the tilt angles of the car in two axes. The accelerometers output is a PWM where the acceleration measured by each of them is encoded in g’s units (1 g is the gravity acceleration of the earth).

pic_16f88
PIC 16F88

Our micro-controller has to be programmed so we can capture (we will use the Capture pins for this) the two PWM’s generated by the accelerometers, and perform the following tasks:

  1. Calculate the tilting angle in that axis: knowing the duty of the PWM to calculate the tilt angle we do as follows: 2πarcsin((X1X1+X20.5)8)2∗π∗arcsin⁡((X1X1+X2−0.5)∗8). So after capturing the PWM’s duty we should do this operation.
  2. Average the last three angle measurements: The accelerometers measurements are usually noisy, so we want to average the last 5 measures. To do this we simply create a five element array and a pointer to this array so we can keep track of where the last angle was added. In the following task, when I talk about angles I am referring to the average of the angles.
  3. Print the tilt angles to an LCD: A standard two-lines LCD is connected to the uController and we have to output the tilting values previously calculated.
  4. Generate two PMW’s encoding the angle: Once we have calculated the angles we have to also encode them into PWM with a duty of 50% representing an angle of zero degrees and for each degree negative or positive we should add or subtract respectively 1% of the duty. That way an angle of 13 deg. should be encoded as a duty of 63%. This PWM should have a total period of 1 msec.
  5. Record the angles in a EEPROM: To keep historical data, it can be useful in case of accident or other problems, sort of simple black box for cars. To communicate with the EEPROM we will use i2Ci2C.

At the end of this post you can download the source code and the schematic files for Proteus. The schematic looks like this:

As you can see there is another PIC in the figure with two buttons, this PIC generates the PWM’s that the accelerometers would create (Proteus doesn’t include a model for accelerometers). Pressing the buttons you can change the duty generated by the PIC so it would be like tilting the vehicle.

Capturing the PWM’s

The core of the project. To do this we are going to use the CCP modules, CCP stands for Capture Compare, (…) and they are useful because we can set them so when a raising or falling edge is detected (using an interruption) we can activate a timer and capture the next raising or falling edge. This way, we can compute the duty of the two PMW’s.

Let’s take a look at the code.

setup_ccp1(CCP_CAPTURE_RE); // Set-up CCP1 to capture raising
setup_ccp2(CCP_CAPTURE_RE); // Set-up CCP2 to capture raising
setup_timer_1(T1_INTERNAL); // Set-up timer 1, associated to the CCP
 
enable_interrupts(INT_CCP1); // Activate all the interruptions
enable_interrupts(INT_CCP2);
enable_interrupts(GLOBAL);

First, we have to set up the PIC so we can capture the Raising Edge, you can set it up to capture the Falling Edge, it doesn’t matter as long as you set it up to something. Then we also have to set up the timer 1; we would use this timer to compute the duty. In my case. I set it up to the internal clock (10 MHz) so it’s fast enough without overflowing in a period of the PWM.

                _      __     ___    _____   _      _____   __     _  
               | |    |  |   |   |  |     | | |    |     | |  |   | |
PWM Signal     | |    |  |   |   |  |     | | |    |     | |  |   | | 
             __| |____|  |___|   |__|     |_| |____|     |_|  |___| |__
Data            0       1      2       4     0        4      1     0

 

Let’s declare the variables we will need for the first PWM’s input:

long fall_1;    // Used to store the instant when the accelerometer 1 falls
long raise_1;   // Used to store the instant when the accelerometer 1 raises   
long X1; // X1 represents the duty (time the pulse is on high) for acce 1
long X2;  // X2 represents the time the pulse is on low for the accelerometer 1
float aceleracin1=0.0; // Accel1, measured in G's calculated from X1 and X2
float angulo1 = 0; // Angle 1 stores the tilt angle of veh. in one of the axis 
int1 change1=0;    // Bool variable to store the current state of the pulse, fo the accelerometer 1

Once we have our variables declared we can use them in the main loop. The math done can be found in the datasheet of the accelerometer (Page 9).

aceleracion1 = (float)1.0*X1/(X1+X2); // Calculate the accel1 in G's from X1 and X2.
aceleracion1 = (aceleracion1 - 0.5)*8;// This transformation is necessary to correctly compute the angle.
angulo1 = 57*asin(aceleracion1);// angle 1 is:(180/pi) * arcsin(accelaration1)

And here is how we calculate the angle from X1 and X2…. But wait, we haven’t set those values! Will do it right now! Programming a microcontroller is a different paradigm from programming in regular C in our PC. Here we are much closer to the hardware and much more constrained in terms of resources. To capture the PWM’s we will use the CCP pins, these pins will call an interruption every time their value is changed, this is a great and easy way of capturing the pulse duty as we can capture the rise and fall of the signal!

The code for the interruption is as follows:

#INT_CCP1                                                                           // Capture HIGH and LOW times of the accelerometer 1
interrupcion_ccp1()
{
   if (change1 == 0)           
   {
      fall_1 = CCP_1; // Capture the moment the CCP_1 goes from high to low.
      change1 = 1;    // Now we get ready to capture hight to low
      setup_ccp1(CCP_CAPTURE_FE);  // Set-up to capture Falling Edge
   }
   else
   {
      X1 = fall_1 - raise_1;  // Calculate X1 as fall1 - raise1. X1 stores the time the pulse stayed on high
      raise_1 = CCP_1;        // Capture the new raising time
      X2 = raise_1 - fall_1;  // Calculate X2 as the time from the previous fall and the actual just captured raise1
      
      change1 = 0;            // Now we are ready to capture the low to high
      setup_ccp1(CCP_CAPTURE_RE);  // set-up to capture the Raising Edge
   }
}

Now it should work! We have to still do the same for the other accelerometer, the code is equivalent just changing the inputs and the variables names to refer to the other data. I will not write it explicitly here but as mentioned above the source code is at the bottom of this post.

Window Average

Now that we now how to capture on pulse duty and calculate is the corresponding angle let’s make something easier but important. Let’s build a five element array where we keep the 5 most recent values. That way we can average that array removing the impact of noise and other artifacts. The following code will do just that:

float bufferAngulo1[5] = {0,0,0,0,0};   // Buffer to record the 5 most recent values of angle 1
float bufferAngulo2[5] = {0,0,0,0,0};   // Buffer to record the 5 most recent values of angle 2
float mediaAngulo1=0;                   // Average of the angle 1
float mediaAngulo2=0;                   // Average of the angle 2
 
int8 punteroBuffer1=0;                  // Pointer for bufferAngulo1
int8 punteroBuffer2=0;                  // Pointer for bufferAngulo2

This will initialize all the variables. Let’s populate them with the data. In the main loop we should add:

bufferAngulo1[punteroBuffer1] = angulo1;    // New element to the buffer
bufferAngulo2[punteroBuffer2] = angulo2;
 
mediaAngulo1 = (bufferAngulo1[0]+bufferAngulo1[1]+bufferAngulo1[2]+bufferAngulo1[3]+bufferAngulo1[4])/5; // Average of the buffer. For loop to be avoided because of delays caused
mediaAngulo2 = (bufferAngulo2[0]+bufferAngulo2[1]+bufferAngulo2[2]+bufferAngulo2[3]+bufferAngulo2[4])/5;
 
punteroBuffer1=punteroBuffer1+1;// Increment the pointers
punteroBuffer2=punteroBuffer2+1;
 
if (punteroBuffer1 >= 4) // Reset the pointers in case they reached the end of the buffer
{
    punteroBuffer1 = 0;                                                    
}
if (punteroBuffer2 >= 4) // Reset also the second pointer to the buffer.
{
    punteroBuffer2 = 0;
}

There you go, this one was easy. We have our buffer and a pointer to the most recently modified item in it so we know where to store the next data. When we make it to the end of the buffer we point to the beginning, making it like a circular buffer. We also calculate the average of the buffer. We avoid using a for loop as it can hurt the performance.

LCD

Now we should be able to display the results on the LCD connected to our micro-controller. This is fairly easy because the LCD manufacturer provides a library to make it’s access easy. So with a simple #include lcd.h we can use the functions printf on the screen. The code in the main loop should look like this:

lcd_putc('\f');  // This flushes the screen
printf(lcd_putc, "Angle 1: %3.1f",mediaAngulo1);
lcd_putc('\n');                     // Print the average of the buffer to the LCD
printf(lcd_putc, "Angle 2: %3.1f",mediaAngulo2);

One lest tick on the to-do list to go.

Generate the PWM’s

Turn off the PWM generation. Let’s recall what we had to do. We have to generate two PWM with period 100 msec. Each of them is going to encode one angle assigning a 50% duty to an angle of zero deg. and adding (or subtracting) a perceptual point for each degree.

As before let’s declare the variables that we are going to use:

int8 pwmOut1H = 0;  // Time that the output PWM 1 should stay in HIGH
int8 pwmOut1L = 0;  // Time that the output PWM 1 should stay in LOW
int8 pwmOut2H = 0;  // Time that the output PWM 2 should stay in HIGH
int8 pwmOut2L = 0;  // Time that the output PWM 2 should stay in LOW

Now inside the main loop, we should populate the variables with its right values:

pwmOut1H = (int) (50.0+angulo1); // The angle is encoded as a PWM where 50% duty represents 0 deg. so for example 40% duty represents -10 deg. angle in this axis
pwmOut1L = 100 - pwmOut1H; // The time that the PWM should be in LOW, is 100 (total width) minus the time that it should stay in HIGH
pwmOut2H = (int) (50.0+angulo2);// The angle is encoded as a PWM where 50% duty represents 0 deg. so for example 60% duty represents +10 deg. angle in this axis
pwmOut2L = 100 - pwmOut2H;

So by now, we have the values that we want our variables to be on HIGH and LOW. But we still have to output these values on the outputs. We will use the timer2 interruption to do that. This timer is setup so it will overflow every msec. since the period is 100 msec. we should a precision of 1 in 100, not great but not too bad either!

With this timer interruption overflowing we will check to see if how much time we have left to stay HIGH or LOW and set the output accordingly. Let’s get to the code.

#INT_TIMER2
interrupcion_timer2()           // This interruption is used to change the PWM at the output that encode the angles
{
   pwmOutCounter1 = pwmOutCounter1 + 1;     // Increment both counters
   pwmOutCounter2 = pwmOutCounter2 +
   // PWM 1
   if (pwmOutCounter1 <= pwmOut1H)           // If we havent reached the time that PMW1 is supposed to stay in high, then we keep it in high
   {
       output_bit( PIN_A0, 1);           // Keep PIN A0 in HIGH
   }
      
   if ((pwmOutCounter1 > pwmOut1H) && (pwmOutCounter1 < pwmOut1H+pwmOut1L) // In case the counter has been enough time on HIGH but has not been enough time on LOW we keep it to low
   {
       output_bit( PIN_A0, 0);      // Keep PIN A0 in LOW
   }
 
   if (pwmOutCounter1 >= pwmOut1H+pwmOut1L)  // In case we have arrived to the end we set the counter to zero to start over
   {
       pwmOutCounter1 = 0;
   }
}

The code is straight forward. Every millisecond we check where we are in terms of time and we select the outputs accordingly.

EEPROM

The last part of our project is to write the average of the last 5-measurements into an EEPROM via i2C. To do this we are going to use a library to simplify the code. We will call the write function every second; for this we will set-up the timer 3 to overflow every second. We do this with the following code:

#include <2416.C>    // Library for the EEPROM
long int address = 0;   // address to write in the EEPROM, set to 0 to start at the beginning of the memory
setup_timer_3(T3_INTERNAL | T3_DIV_BY_8);  // Use timer 3 to write to the EEPROM when overflow

Now we have an interrupt every second, so we will need to write the code to write into the EEPROM. We will use the variable address to keep track of the last position written. The code:

#INT_TIMER3                                    
interrpcion_timer3()
{
   write_ext_eeprom(address, (signed int)mediaAngulo1);             // Write the average of the angle 1 to the EEPROM
   address = address + 1;                               // Point to the next memory position
   write_ext_eeprom(address, (signed int)mediaAngulo2);             // Write the average of the angle 2 to the EEPROM
   address = address + 1;                           // Point to the next memory position
 
   if (address >= 0x7FF)
   {
      address = 0;                              // If the end of the memory is reached, start overwriting from the beginning
   }
}

This concludes my small project. The source code can be download in here. You should open the files with proteus. I added another PIC and some switches to emulate the pulses coming from the accelerometers.

Hope you enjoyed!