1+1=2

 This blog post uses peano axioms to proof that 1+1=2. In case you were not sure that one and one equals two.

We use the following definitions:

• $0$ is a natural number
• $1 = S(0)$
• $2 = S(1)$

With $S$ the successor function.  For the number $0$ and the successor function, the existence of them is enough, their exact definition does not matter. $1$ and $2$ on the other hand, are fully stated by the definitions of $0$ and $S$

Now, let's define addition.

It is an operation with the following two properties:

$$a + 0 = 0\\a + S(b) = S(a+b)$$

So this means:

$$1+1=1+S(0)=S(1+0)=S(1)=2$$

QED.

We can use this pattern to calculate fancier things, like $2+2=4$

$$2+2=2+S(1)=S(2+1)=S(2+S(0))=S(S(2+0))=S(S(2))=S(3)=4$$

And all other kind of additions. 

Further, we can define multiplication as

$$a\times 0 = 0\\a\times S(b) = a + (a\times b)$$

Now is

$$1\times 1 = 1\times S(0) = 1+ (1\times 0)=1+0=1$$

and 

$$2\times 2 = 2\times S(1) = 2+ (2\times 1)=2+ (2\times 1) = 2+(2 \times S(0)) = 2+(2+(2 \times 0)) = 2+(2+0)=2+2=2+S(1)=S(2+1)=S(2+S(0))=S(S(2+0))=S(S(2))=S(3)=4$$

QED

AI playing battleship.

 The game battleship is a two-player game where each player places 5 ships (a size 2 ship, two size three ships, a size 4 ship and a size 5 ship) on a 10 by 10 grid, without showing their configuration to the other players. Then, players take turns each selecting a grid cell, and the other player communicates back if this is a miss or a hit, and if it is a hit, if it fully sinks a ship. The first player that fully sinks all other ships wins.

In this blog post, we will only consider the method to sink the other player's ships as fast as possible, we do not consider strategies to keep our own ships alive.

Intuitively, it might make sense to go for the tiles that our AI thinks have the highest chance to contain a battleship, but this is actually a version of the Multi-armed Bandit problem. Early in the game, we would want to go for squares that give us the most information, not squares that have the highest chance of hitting.

But in practice, this problem does not actually arise for two reasons. Firstly, the chance to hit a tile will be lower than one half in most cases, which means that the squares that give the most information and the squares that have the highest chance to hit align. And secondly, even if a certain tile gives us more information, we will still have to take an extra shot to score that hit later, so unless this information can save us two misses later, it will not be worth it.

In other words, one can see the action of minimising the number of shots as minimizing the number of misses, as the number of hits will always be the same (the number of ship tiles), so every time we need to make the action that minimises the chance on a miss.

Our AI will make use of the greedy strategy, which means that on every turn we will maximise the chance to hit on that turn, we will not try to take actions that maximise further chances to hit. This strategy will still be effective, because scoring hits gives us way more information then scoring misses, so hitting now will increase our chances to hit in the future.

To calculate the chance to hit, one uses the following approach. We take the set of all possible configurations of the enemy ships that have not been ruled out and count for each square how many configurations have a ship on that square divided by the total number of configurations.

It is not possible to calculate all possible states, so we will use Monte Carlo. we simulate 1000 possible configurations and calculate the chances given these simulated configurations. 

In the following video, you can see the AI in action. Each blue square is a miss, each red square is a hit, and the other squares are marked from white to green, where white is low chance to hit and green is a high chance.

Volume of tetrahedron limited by 4 planes

Consider the following puzzle:

Calculate the volume of a tetrahedron enclosed by the following 4 planes
$$a_1x+b_1y+c_1z+d_1=0\\a_2x+b_2y+c_2z+d_2=0\\a_3x+b_3y+c_3z+d_3=0\\a_4x+b_4y+c_4z+d_4=0$$

The easiest way to calculate this volume is by applying a linear transformation to the tetrahedron where the planes of the tetrahedron align to the coordinate planes. It is impossible to find a purely linear transformation that does this, as all linear transformations project the origin, to the origin, but it is possible to find a linear transformation, followed by a translation, to do this. As translations do not change the volume, this will not pose any unsolvable issues.

An example of such a transformation is

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3$$

To find the transformation of a given plane, one has to add the equation of the plane to the system of equations of the transformation. For example, for the first plane this becomes:

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3\\0=a_1x+b_1y+c_1z+d_1$$

Or solved: $u=0$. So the first plane matches the $vw$-plane.

This is analog for the two next planes, but things become interesting for the last plane, where the system becomes:

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3\\0=a_4x+b_4y+c_4z+d_4$$

Now, in our $uvw$ space, we have a tetrahedron enclosed by the coordinate planes, and a 4th plane that is the solution of the above equation. Tetrahedra enclosed by all 3 coordinate planes have the following vertices: $$(0,0,0), (u,0,0), (0,v,0), (0,0,w)$$ Each of these points can be found by solving the system of equations of 3 of the 4 planes. 

Using the first 3 planes obviously gives (0,0,0) as a solution.

Using all of them except the first gives us:

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3\\0=a_4x+b_4y+c_4z+d_4\\v=0\\w=0$$

This easily simplifies to 

$$u=a_1x+b_1y+c_1z+d_1\\0=a_2x+b_2y+c_2z+d_2\\0=a_3x+b_3y+c_3z+d_3\\0=a_4x+b_4y+c_4z+d_4$$

If we call:

$$A_1 =\left[ \begin{matrix} a_1&b_1&c_1&1\\a_2&b_2&c_2&0\\a_3&b_3&c_3&0\\a_4&b_4&c_4&0\end{matrix}\right]\\A_2 =\left[ \begin{matrix} a_1&b_1&c_1&0\\a_2&b_2&c_2&1\\a_3&b_3&c_3&0\\a_4&b_4&c_4&0\end{matrix}\right]\\A_3 =\left[ \begin{matrix} a_1&b_1&c_1&0\\a_2&b_2&c_2&0\\a_3&b_3&c_3&1\\a_4&b_4&c_4&0\end{matrix}\right]\\A_4 =\left[ \begin{matrix} a_1&b_1&c_1&0\\a_2&b_2&c_2&0\\a_3&b_3&c_3&0\\a_4&b_4&c_4&1\end{matrix}\right]$$

$$D = \left[\begin{matrix} d_1\\d_2\\d_3\\d_4 \end{matrix}\right]$$

$$X = \left[\begin{matrix} x\\y\\z\\-u \end{matrix}\right]$$

The system can be rewritten as

$$A_1X+D=0$$

$$X=-A_1^{-1}D $$

Now as 

$$u =  -\left[\begin{matrix} 0&0&0&1 \end{matrix}\right]X$$

$$u =  \left[\begin{matrix} 0&0&0&1 \end{matrix}\right]A_1^{-1}D$$

$$u =  \frac{1}{\det{A_1}}\left[\begin{matrix} 0&0&0&1 \end{matrix}\right]\text{adj}{A_1}D$$

As the bottom row of $\text{adj}{A_1}$ equals

$$\left| \begin{matrix}a_2&b_2&c_2\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|;\left| \begin{matrix} a_1&b_1&c_1\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|;\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_4&b_4&c_4\end{matrix}\right|;\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3\end{matrix}\right|$$

Then 

$$\left[\begin{matrix} 0&0&0&1 \end{matrix}\right]\text{adj}{A_1}D = d_1\det{A_1}+d_2\det{A_2}+d_3\det{A_3}+d_4\det{A_4}$$

If one defines:

$$M =\left[ \begin{matrix} a_1&b_1&c_1&d_1\\a_2&b_2&c_2&d_2\\a_3&b_3&c_3&d_3\\a_4&b_4&c_4&d_4\end{matrix}\right]$$

Then is

$$u = \frac{\det{M}}{\det{A_1}}$$

Analog is 

$$v = \frac{\det{M}}{\det{A_2}}\\w =\frac{\det{M}}{\det{A_3}}$$

Now the volume of the tetrahedron is the surface area of one of the faces time the height divided by 3, so if one takes the face to be the $vw$-plane, the volume is

$$\frac{u}{3} \times \frac{vw}{2} =  \frac{uvw}{6}$$

In $uvw$ space. In $xyz$ space the volume has to be divided by the Jacobian:

$$\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3\end{matrix}\right|$$

which is $\det{A_4}$ so the final volume becomes:

$$\frac{\det{M}^3}{6\det{A_1}\det{A_2}\det{A_3}\det{A_4}}$$

Or expanded:

$$\frac{{\left| \begin{matrix} a_1&b_1&c_1&d_1\\a_2&b_2&c_2&d_2\\a_3&b_3&c_3&d_3\\a_4&b_4&c_4&d_4\end{matrix}\right|^3}}{6\left| \begin{matrix}a_2&b_2&c_2\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|\left| \begin{matrix} a_1&b_1&c_1\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_4&b_4&c_4\end{matrix}\right|\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3\end{matrix}\right|}$$