### 31

Count: 0

Geoffrey Mott-Smith Thirty-One Game: This a an example taken from the Ferguson book on Game Theory.

In this game the 2 players alternate moves and in each turn they have to take a card from the ones available and add it to a pile, the first one to make it sum more than 31 loses.

This is what it’s called a Combinatorial Game since the player have sets of moves and there are is no chance involved (and also finishes in a finite number of step and there is always a winner and a loser). In particular, this type of games are called Substraction Games. The problem here is that we have a limited use for each number, if that weren’t the case, the implementation would be trivial.

So for solving this problem we will classify the positions of the game in Winner or Looser positions, from the end to the firsts possible moves, using dynamic programming.

There is a great tutorial on how to implement these kind of games in topcoder at http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames

Richard Feynmann: a genius, a storyteller, a joker… maybe someday I will write a post about him.

The Appolonius Cone: In this geometrical construction we can see the 4 types of Conic Section. This demo is made in Processing. (source code available here)

To do this, we need to intersect lines and planes in 3 dimensions. As in this case we can put the coordinates wherever we want, we can choose them to make our code simpler. So we choose $$(0,0,0)$$ as the cone’s vertex and $${y=1}$$ as plane where the base is, and we also choose 1 as the base radius.
The planes we will use will be parallel to the z-axis (the depth one), so they have a trivial representation as a linear function in 2d (except the vertical plane, but we will deal with that later) : $$y=mx+b$$

class SpecialPlane {
float m, b; // Plane: {(x,y,z) / m*x+b = y}


As all the lines that we will use to intersect pass through the origin (i.e. the cone’s vertex), we will only need to know which other point is coming through. In this case that will be $$(\cos \theta,1,\sin \theta)$$ where $$\theta$$ sweeps al the angles between $$0$$ and $$2\pi$$. Finally with a little of Linear Algebra we deduce the formula:

PVector intersect(float lx, float ly) {
float f = -b / (m*lx-1);
return new PVector(f * lx, f, f * ly);
}