## Semi-Autonomous Robotics: (2012) My 1st Software Project

I’m experimenting with committing past projects to github.

Over the summer (2012) at George Washington University Robotics Lab – Positronics Divison (with Roxana Leonetie as my mentor and Gregory Colella as my research partner), we wrote a package for the PR2 using ROS stacks and Python. In short, the PR2 completes a task moving a dowel into a hole (using only force proprioception) as a response to dynamic stimuli.

If you are unfamiliar with the PR2:

Greg was relatively new to Python (an experienced Java coder), and I learned to code the same summer that we completed the project (previously, I had dabbled in mainly math and physics). Bear this in mind while viewing our project.

This is an early demo I simulated in gazebo of the PR2 learning to replicate arm movements (a major part of the project).

## Reframing the Gluten Scanner

A lesson that every scientist (or any person in a fast-paced creative field) learns: be glad when we find out that our research idea has already been done.

The situation can be re-framed as follows:

1. It’s awesome that there are others working just as hard as you to better the world.
2. Reassurance that you’re not idiotic.
3. You can now devote your precious time to developing your other projects.

I learned this lesson in 2011. After proving myself competent by assisting others in the lab (George Washington University Robotics Lab, Positronics Division), I was encouraged to pursue an independent research project using the PR2 as the research platform.
I excitedly came up with a list of ideas, then grew progressively more disappointed as I proceeded to research each idea further.
In the crowded lab, I said aloud, “It seems that almost every project I come up with has either already been proposed or wouldn’t be funded”.
To which the senior engineer in the lab (whom had not spoken to me before) responded, “Welcome to science!”.

Sidenote: I ended up programming the PR2 to autonomously navigate and complete a task using only force proprioception.

One of the main projects that I’ve been working on is a gluten scanner.

The scanner allows those with food allergies to avoid accidentally poisoning themselves. This is done in one of two ways:

## Raman Spectroscopy Method

• Identify the minima and maxima on the absorption spectrum of a given protein (currently gluten) with a 1D array of IR / Vis lasers and an Avalanche photodiode Si(c).
• Perform differential data analysis to determine if the food is contaminated.

This scanner would be able to analyse the food ~>1cm in depth without effecting the food, whereas (if desired) taking a small sample out of the food at an opportune sampling point allows for deeper results.

Originally planning on taking spectroscopic approach, I found that it was incredibly noisy (see below) to detect gluten in a vinegar solution [gluten is insoluble in water], let alone amongst protein rich food!

Thank you, Sunnyvale Biocurious, for training Paul on the spectrophotometer!

Realizing the specificity of the antigen-binding sites on antibodies, I came up with the following biomarker approach to significantly increase the accuracy of my device.

## Biomarker Method

Gluten is a protein composite of gliadin and glutenin (stuck together with a starch). G12 and A1 are antibodies that bind to gliadin (a highly immunotoxic 33-mer peptide).

Although A1 has a higher sensitivity to gluten (0.33ppm) than G12 (0.5ppm), most Celiac patients have a 20ppm poisoning threshold (far below both thresholds). G12 is far less expensive, and thus the better option for regular consumer use if you aren’t willing to synthesize your own antibodies in bulk.

Anti-gliadin antibodies can be paired with a colorimetric assay to form a biomarker-based detector in the form of: a toothpick-sized detector to poke into food || the gluten-detecting equivalent of litmus strips.

 G12 (Image credit: PDB)

In the past few days, I found that there are a set of devices, GlutenTox, which use my planned approach. Since this realization, I’ve also come across 6sensorlabs, and the TellSpec.

It seems to me that these solutions are not cost-effective enough to be sustainable for daily use. This is likely because antibodies are expensive unless you bulk synthesize them.

## How Stockfish Works: An Evaluation of the Databases Behind the Top Open-Source Chess Engine

This is a paper I wrote my 3rd year of university as I was working on my Machine Learning-based Braille translator research. Enjoy!

Abstract

Playing chess has been on the forefront of AI research since Alan Turing and his students proposed chess playing machines. The game of chess is a domain of human thought where very limited sets of rules yield inexhaustible depths, challenges, frustration and beauty. The playing strategies of AI and human players have diverged proportional to the increase of available computing power, namely speed and storage space.
Human players recognize and aim to achieve particular patterns; typically, they perform a deep search weighted towards moves that lead to such desired patterns, transferring past knowledge and adapting it to their present situation. AI chess is mostly played by parsing through a huge database, with broad search algorithms used to search for the next optimal move.

All chess engines work by looking at a heuristically determined subset of the legal moves stemming from a given position and evaluating numbers to represent the new position’s relative value obtained by making those moves; then, recursively doing the same thing for the resulting positions. This is done using an evaluation function. An efficient evaluation function provides a better toolbox to guide the chess tree search, which improves the strength and speed of the AI player.

Stockfish is the top-ranked open-source chess engine, and I will be evaluating its elaborate use of databases; in particular, how Stockfish represents the state of the chessboard, evaluates the static board positions, uses its search algorithm, and uses past moves to optimize its next move.
Keywords: Chess, AI Chess, Search Techniques, Chess algorithms, Databases, Alpha-Beta Pruning, Stockfish, Stockfish 2.3.1

INTRODUCTION

Application Domain

It is important to distinguish between computer chess research and research using chess as a test bed. The latter expands the user community past chess enthusiasts to AI developers. In AI, the real-time evaluation and categorization of a dynamic environment is crucial to maintaining functionality while performing a task. This environment can be categorized using preset labels and rules or adapted to based purely on experience. Stockfish’s evaluation of chess positions, based not only on material properties (i.e., “I have more pieces than you”) but on the relationships and structures that exist between said material (i.e., “My piece is protected by two other pieces, and is threatening your unprotected piece.”), is useful in the domain of autonomous systems which must quickly evaluate the stability of groups of objects interacting within set rules.

Project Motivation

The narrow view of this project’s motivation is to improve the strength of AI chess players. This engine’s effectiveness depends on proper tagging, passing, evaluating, and searching of chess positions.

The main issues faced by AI chess players are:

• Storing and evaluating data efficiently
• Proceeding with the recursive search of moves

For most chess positions, computers cannot look ahead to all final possible positions. Instead, they must look ahead a few plies (a “ply” refers to one turn taken by one of the players. “Turn” is problematic since it means different things in different traditions. For example, in standard chess terminology, one move consists of a turn by each player; therefore a ply in chess is a half-move.) and then evaluate the final board position. The algorithm that evaluates final board positions is the evaluation function, which differs between different chess engines.

While the human method of analyzing alternatives seems to involve selecting a few promising lines of play and exploring them, computers are necessarily exhaustive rather than selective, so refinement techniques have been (and continue to be) developed.

Stockfish uses a complicated set of analysis functions depending on what material is on the board. By applying small changes and refinements (i.e. using categorical analysis) to alpha-beta pruning, there is a measurable difference in the time efficiency of pruning, without disregarding interesting nodes. Stockfish continues to expand as additions and tweaks are added by various developers.
Science Usage
The user requirements for Stockfish are mercifully little, for it is an open-source cross-platform engine. The only pre-requisites to using Stockfish are downloading the source code from their website. It may be run from the commandline or a UCI-Compatible GUI.

Goals

The ultimate goal of Stockfish is to unite the chess-program-developer community, and continue to a build stronger, faster chess engine.
This includes, among other things, a goal to improve the effectiveness of search evaluations. By creating an efficient board representation, this provides a better toolbox to guide the chess tree search, which improves the AI.

Alpha-beta pruning is just a complicated-sounding name for “Don’t check moves which cannot possibly have an effect on the outcome of your search.” The alpha-beta algorithm used in recursive search continues be improved. These enhancements come from the fact that if you restrict the window of scores that are interesting, you can achieve more cutoffs. The latest technique of move ordering is applied outside of the search, using iterative deepening boosted by a transposition table.

Results

Stockfish has clearly demonstrated that simple, brute-force approaches should not be quickly discarded. Additionally, iterative techniques, in particular, ideas developed for alpha-beta search and iterative deepening, are applicable to other search domains. Stockfish has clearly demonstrated the inadequacy of conventional AI techniques for real-time computation. Stockfish does not use AI languages or knowledge representation methods, for these conventions are too slow for a real-time, high-performance application.

I have found that Stockfish represents the state of the chessboard using bitboards, it evaluates the static board positions using a categorical and statistical representation and uses an advanced alpha-beta search algorithm. In order to not analyze the same position several times, a transposition table is used. This is essentially memorization applied to the search function.

Design and Schema

The design of Stockfish is based on the interaction of various nodes (pictured in Schema).

A move search in Stockfish consists of 21 steps.

Step 1. Initialize node

Step 2. Check for aborted search and immediate draw. Enforce node limit here. (This only works with 1 search thread, as of Stockfish 2.3.1.)

Step 3. Mate distance pruning. Even if we mate at the next move our score would be at best mate_in ($$\text{ss}\rightarrow\text{ply}+1$$), but if alpha is already bigger because a shorter mate was found upward in the tree then there is no need to search further, we will never beat current alpha. Same logic but with reversed signs applies also in the opposite condition of being mated instead of giving mate, in this case return a fail-high score.

Step 4. Transposition table lookup. We don’t want the score of a partial search to overwrite a previous full search. We use a different position key in case of an excluded move.

Step 5. Evaluate the position statically and update parent’s gain statistics

Step 6. Razoring (is omitted in PV nodes)

Step 7. Static null move pruning (is omitted in PV nodes). We’re betting that the opponent doesn’t have a move that will reduce the score by more than futility-margin (depth) if we do a null move.

Step 8. Null move search with verification search

Step 9. ProbCut. If we have a very good capture and a reduced search returns a value much above beta, we can (almost) safely prune the previous move.

Step 10. Internal iterative deepening.

Step 11. Loop through moves. Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs

Step 12. Extend checks and also dangerous moves

13. Futility pruning.

Step 14. Make the move

Step 15. Reduced depth search (LMR). If the move fails high will be re-searched at full depth.

Step 16. Full depth search, when LMR is skipped or fails high.

Step 17. Undo move

Step 18. Check for new best move

Step 19. Check for split

Step 20. Check for mate and stalemate

Step 21. Update tables. Update transposition table entry, killers and history

Stockfish begins by developing a legal-move tree, whence it must evaluate the resulting board positions. That is, the computer has to look at the pieces on the board and decide whether that arrangement of pieces is “good” or “bad.” The way it does this is by using an evaluation function. Since it is so important to evaluate the best move first, it might be worthwhile to execute a shallower search first and then use the resulting alpha/beta cutoff values as start values for a deeper search.

The chess evaluation function becomes more and more complicated by adding things like board position, control of the center, vulnerability of the king to check, vulnerability of the opponent’s queen, and tons of other parameters. No matter how complicated the function gets, however, it is condensed down to a single number that represents the “goodness” of that board position.

The main rules that govern the evaluation of position in Stockfish are as follows.

Pawn Structure

1. Penalize doubled, backward and blocked pawns.
3. Encourage control of the center of the board.

Piece Placement

1. Encourage knights to occupy the center of the board.
2. Encourage queens and rooks to defend each other and attack.
3. Encourage 7th rank attacks for rooks.

Passed Pawns

1. These deserve a special treatment as they are so important.
2. Check for safety from opposing king and enemy pieces.
3. Add enormous incentives for passed pawns near promotion.

King Safety

1. Encourage the king to stay to the corner in the middlegame.
2. Try to retain and effective pawn shield.
3. Try to stop enemy pieces from getting near to the king.

The same position will commonly occur from different move orders, thus most chess engines (including Stockfish) have a trasposition table (position cache). This is implemented using a hash table using the chess position as its key. Using a position cache instead of a hash table negates the need to evaluate large sub trees over and over again.

Alpha-beta pruning, without enhancements nor extensions, is represented in psuedo-Python below.

def alphaBetaMax (alpha, beta, depthleft):
if (depthleft == 0): return evaluate()
for (all moves):
score = alphaBetaMin(alpha, beta, depthleft - 1 )
if( score >= beta):
return beta   #fail hard beta-cutoff
if( score > alpha ):
alpha = score #alpha acts like max in MiniMax
return alpha
def alphaBetaMin(alpha, beta, depthleft )
if ( depthleft == 0): return -evaluate()
for (all moves):
score = alphaBetaMax( alpha, beta, depthleft - 1 )
if( score <= alpha ):
return alpha #fail hard alpha-cutoff
if( score < beta ):
beta = score  # beta acts like min in MiniMax
return beta
score = alphaBetaMax(-oo, +oo, depth)
print score

This schema shows the input with the current position, and ends with the next move, in order to avoid over-powering the simple nature of Stockfish by showing both method names and method parameters, I have created a representation of the overall use of databases in Stockfish.

Contents of Database

The contents of a typical chess engine database is past moves (moves that have been done in the past, very useful for the opening game), current moves (moves that are legal from a chess board’s current position), and legal moves (rules governing the movement of each type of chess piece). Stockfish uses bitboard representation. Bitboards are a wonderful method of speeding up various operations on chessboards by representing the board by a set of 64 bit numbers.

A brief explanation of Bitboards is as follows: Supposing, for example, we generate a 64 bit number which represents the pawn structure on the chess board. We do this by starting at a8, and moving across then down in the sense a8,b8,c8,…,h8,a7,b7,c7,…,g1,h1. For each square, we put a ‘1’ if there is a pawn, or a ‘0’ otherwise. Then we have just one number on which we can perform all sorts of useful operations. Once we have a bitboard with all the possible destination squares set to ‘1’, we now have to cycle through them one by one. To do this, we require two routines. Firstly we require a routine which locates the position of the first bit in the bitboard which is set, and secondly we need a simple macro which then sets this bit to zero.

10 Questions

Any chess player, human or AI, must answer the following question: What is the “best” move I can make next?. This answer is highly subjective, and depends entirely on what constitutes a “good” position. As humans, we easily recognize patterns, apply our past experience to current games, and use our intuition to judge the quality of play. However, a chess evaluator must find the strength of possible positions in a mechanical way, using a set of parameters (similar to the following questions) to describe and evaluate the strength of a given position.

Query 1) What is the position of all pieces on the board?

Query 2) What legal moves can each piece make from this position?

Query 3) What are relationships between pieces on the board? Are structures threatened or pieces undefended?

Query 4) Is there a strong pawn structure and effective pawn shield?

Query 5) Is the King mobile, well protected, and not in check?

Query 6) Is the center of the board occupied?

Query 7) Are any major pieces blocked?

Query 8) Are there passed pawns near promotion?

Query 9) Are bishops occupying major diagonals?

Query 10) What is the material difference between players?

After these 10 questions have been answered, the chess evaluator can score a position, and feed this score into the chess tree to optimize the $$\alpha-\beta$$ pruning that follows.

Algebraic Chess Notation

Readers are encouraged to explore additional background information provided by the online book Building Skills in Python.

SOURCES

1. H. Nasreddine and H. S. Poh, “Using an evolutionary algorithm for the tuning of a chess evaluation function based on a dynamic boundary strategy”, 2005. http://www.cs.nott.ac.uk/~gxk/papers/ieeecis2006.pdf.
2. J. S. T. Anthony Marsland, Feng-hsiung Hsu and D. E. Wilkins, “The role of chess in artificial intelligence research”, http://ijcai.org/Past%20Proceedings/IJCAI-91-VOL1/PDF/084.pdf
3. M. Strejczek, “Some aspects of chess programming”, http://www.top-5000.nl/ps/SomeAspectsOfChessProgramming.pdf.
4. Wikipedia, “Ply(game theory)”, http://en.wikipedia.org/wiki/Ply_%28game_theory%29.
5. T. Romstad, M. Costalba, J. Kiiski, D. Yang, S. Spitaleri, and J. Albett, “Stockfish about,” http://stockfishchess.org/about/.
6. O. David-Tabibi, M. Koppel, and N. S. Netanyahu, “Optimizing selective search in chess”, http://www-kd.iai.uni-bonn.de/icml2010mlg/papers/DavidTabibiEtAl.pdf.
7. T. Anantharaman, M. S. Campbell, and F. hsiung Hsu, “Singular extensions: Adding selectivity to brute-force searching”, Artificial Intelligence , pp. 99–109, 1990.
8. I. Chernev, Logical Chess, Move By Move – Only Chess Book That Explains Every Move Of Every Game, 1957.
9. D. Levy and M. Newborn, How Computers Play Chess,, Computer Science Press, New York, 1990.
10. C. Frayn, “Computer chess programming theory”, 2005. http://www.frayn.net/beowulf/theory.html.

## A Method to Not Prove the Collatz Conjecture

Number theory is the cocaine of mathematics. The following resulted not from my intention to prove the conjecture, but from the drive to deeply understand its underlying structure.

After obsessively thinking about it for a few weeks, I came up with a possible approach out of the blue.

I scribbled the proof down at the breakfast table on Christmas day, and this rushed, unedited transcription of thought to paper led to assumptions and oversights that I could not justify when I revisited my scribblings.

As I was transcribing my proof from messy scribbles in my notebook into LaTeX, I found errors (described below). I encourage the reader to attempt to find the errors before they are explained!

In the spirit of How Not to Prove the Poincare Conjecture, I present the following:

Claim:

$$\forall n \in \mathbb{N}$$ the number sequence

n_{i+1} =
\begin{cases}
n_i/2, & \text{if }n_i\text{ is even} \\
3n_i+1, & \text{if }n_i\text{ is odd}
\end{cases}

will always contain the closed chain $$4 \rightarrow 2 \rightarrow 1 \rightarrow 4$$.

Proof:
Let $$f \equiv$$ the product factor between $$n_i$$ and $$n_{i+1}$$

If $$n_i$$ is odd:

$$n_{i+1} = 3n_i+1$$

$$n_{i+1} = fn_i$$

$$f_{i, i+1} = \frac{3n_{i+1}}{n_i} \Leftrightarrow f_{i+1, i} = \frac{n_i}{3n_i+1}$$ [Eq. 1]

Let $$n_1 \rightarrow n_2 \rightarrow \ldots \rightarrow n_{g-1} \rightarrow n_g$$ be any Collatz sequence, started by an arbitrary number $$n_1 \in \mathbb{N}$$ and ended after $$g-1$$ steps on a number $$n_g \in \mathbb{N}$$.

Every even number has an odd number somewhere in it’s sequence, so we will assume that $$n_1$$ is always odd.

A number sequence is an open chain when $$n_i \neq n_j, i \neq j$$ for $$g-1$$ steps. (In other words, there are no repeated numbers in the number sequence.) The chain has $$e$$ even and $$o$$ odd steps.

For the total factor between $$n_1$$ and $$n_g$$ after $$g-1$$ steps for an open chain, it follows from Eq. 1 that

$$2^e\prod_{j=1}^o\frac{n_j}{3n_j+1} = \frac{n_1}{n_g}$$ where $$j$$ is the $$j^{th}$$ odd number in the sequence. [Eq. 2]

A number sequence is a closed chain if $$n_g = n_1$$ and $$n_i \neq n_j, i \neq j$$; $$i, j \in [2, g-1]$$ for $$g$$ steps.

The total factor between $$n_i$$ and $$n_g$$ for closed chains is thus

$$2^e\prod_{j=1}^o\frac{n_j}{3n_j+1} = 1$$

This proof will demonstrate that no other closed chain exists and no open chain exists with endless length.

Let’s reverse engineer it. We start at the last element of the sequence with $$g$$ steps and show that given $$n_g = 1$$ we can reach all odd numbers > 1 by the inverse Collatz sequence.

Using the definition [Eq. 2] of an open chain

$$2^e\prod_{j=1}^o\frac{n_j}{3n_j+1} = \frac{n_1}{n_g} = n_1$$

Let’s do a proof by exception. If we have no other odd numbers apart from 1 in our sequence ($$o =0$$), it follows that

$$2^{e_{g}} = n_1$$

$$o = 0$$ is the only open chain with only even steps. We will address this abnormality later in the [attempted] proof.

Let $$o =1$$

$$2^{e_{0}}\frac{n_1}{3n_1 + 1} = n_1 \Rightarrow n_1 = \frac{2^{e_{1}}-1}{3}$$

Let $$o = 2$$

$$2^{e_{2}}\frac{n_1}{3n_1+1}\frac{n_2}{3n_2+1} \Rightarrow n_1 = \frac{2^{e_{2} – e_{1}}(n_2-1)}{3}$$.

Let $$o=3$$

$$2^{e_{3}}\frac{n_1}{3n_1+1}\frac{n_2}{3n_2+1}\frac{n_3}{3n_3+1} = n_1$$

$$2^{e_{3} – (e_{2} – e_{g-1})}\frac{n_1}{3n_1+1}n_2 = n_1$$

and so on.

It follows in general

$$n_1 = \frac{2^{x}n_2-1}{3}, x \in \mathbb{N}$$ [Eq.3]

ERROR EXPLANATION:

The $$o=2$$ simplification doesn’t work. I use the $$o=1$$ equation to substitute in a simpler form for $$n_2$$, but that equation only holds when $$n_1$$ is the end of a cycle. In this case $$n_2$$ would not be the end of a cycle, thus the $$o=1$$ equation for $$n_1$$ cannot be plugged in for $$n_2$$.The same follows for $$o=3$$ etc.

I did the following:
$$2^{e_2}[\frac{n_1}{(3n_1 + 1)}][\frac{n_2}{(3n_2 + 1)}] = n_1$$
$$2^{e_2}[\frac{n_2}{(3n_2 + 1)}] = 3n_1 + 1$$
$$n_1 = \frac{(2^{e_2}[\frac{n_2}{(3n_2 + 1)}] – 1)}{3}$$

from $$o=1$$:

$$2^{e_1}[\frac{n_1}{(3n_1 + 1)}] = n_1$$
$$\frac{n_1}{(3n_1 + 1)} = \frac{n_1}{2^{e_1}}$$
sub in 2 for 1 $$\leftarrow$$ DOES NOT FOLLOW
$$\frac{n_2}{(3n_2 + 1)} = \frac{n_2}{2^{e_1}}$$ $$\leftarrow$$ DOES NOT FOLLOW

sub in that mess:

$$n_1 = \frac{(2^{e_2}[\frac{n_2}{(3n_2 + 1)}] – 1)}{3}$$
$$n_1 = \frac{(2^{e_2}[{n_2}{2^{e_1}}] – 1)}{3}$$ $$\leftarrow$$ DOES NOT FOLLOW
$$n_1 = \frac{[2^{(e_2-e_1)}n_2 – 1]}{3}$$

Even if that did work, I have several arithmetic errors. If we plug in 2’s for 1’s in the $$o=1$$ equation and solve for $$\frac{n_2}{(3n_2 + 1)}$$, the result should be $$\frac{n_2}{2^{e_2}}$$ rather than $$\frac{n_2}{2^{e_1}}$$.

Further, even if $$\frac{n_2}{2^{e_1}}$$ was the right thing to plug in for $$\frac{n_2}{(3n_2 + 1)}$$ the result in $$o=2$$ should be $$\frac{[2^{(e_2-e_1)}n_2 – 1}{3}$$ (i.e., no parentheses around “$$n_2 – 1$$”). I correct this in $$o=3$$. The rest of the proof depends on finding solutions to [Eq. 3], which I’ve just shown to be moot. Nevertheless, back to the attempted proof…

So when do integer solutions to [Eq. 3] exist? Let’s partition the set of odd natural number into 3 disjoint subsets. $$1^{st}$$ subset is set of all odds which are multiples of 3. There are no solutions for this subset, since

$$n_1 = \frac{2^x3_j-1}{3} = 2^xj – \frac{1}{3}$$, $$j \in \mathbb{N}$$

The second subset is given by $$n_{3ep} = 6i_{ep} + 1$$, $$i_{ep} \in \mathbb{N}$$ which solves the recurrence formula [Eq. 3] for even powers $$x_{ep}$$.

The third subset is given by $$n_{3op} = 6i_{op} – 1$$, $$i_{op} \in \mathbb{N}$$ which solves the recurrence formula [Eq. 3] for odd powers $$x_{op}$$.

With these two subsets satisfying the recursion formula, we can get all start numbers $$n_1$$ of Collatz sequences generated by their direct follower. But, addressing the previous anomaly, we have one exception to our recurrence formula. The case $$n_2,n_1 = 1,1$$ gives us $$4 \rightarrow 2 \rightarrow 1 \rightarrow 4$$. Here, the only odd number (1) in the sequence is the factor between $$n_1$$ and $$n_g$$, for $$4 \rightarrow 2 \rightarrow 1 \rightarrow 4$$ is a closed chain. This sequence continues to iterate on itself and is an exception to the recurrence relations.

ERROR EXPLANATION:

My 3 subsets are ill defined and not mutually exhaustive.
Subset 1 is clear because $$n_2\mod 3 = 0$$ will never satisfy [Eq. 3].
For the second and third subsets, I state that $$2^x\mod 3 = 1$$ when $$x$$ is even and $$2^x\mod 3 = 2$$ when $$x$$ is odd. Which is sound.
Subset 2 ($$x$$ even): $$n_2 = (6i + 1)$$, therefore $$[(2^x)(n_2) – 1]\mod 3 = [2^x\mod 3][(6i + 1) \mod 3] – (1 \mod 3)$$
$$= (1 \mod 3)(1 \mod 3) – (1 \mod 3)$$
$$= (1 \mod 3) – (1 \mod 3) = 0 \mod 3$$ which satisfies [Eq. 3].

Subset 3 ($$x$$ odd): $$n_2 = (6i – 1)$$, therefore $$[(2^x)(n_2) – 1] \mod 3 = [2^x \mod 3][(6i – 1) \mod 3] – (1 mod 3)$$
$$= (2 \mod 3)(2 \mod 3) – (1 \mod 3)$$
$$= (1 \mod 3) – (1 \mod 3) = 0 \mod 3$$ which satisfies [Eq. 3].

It was pointed out to me that I could have used $$3i + 1$$ and $$3i – 1$$ instead of $$6i + 1$$ and $$6i – 1$$ to convey the same result (it’s just mod 3).

In my approach, we find not 3 but 5 disjoint subsets:
1. $$n_2 \mod 3 = 0$$, no solution
2. $$n_2 \mod 3 = 1$$ and $$x$$ even, solution
3. $$n_2 \mod 3 = 1$$ and $$x$$ odd, no solution
4. $$n_2 \mod 3 = 2$$ and $$x$$ even, no solution
5. $$n_2 \mod 3 = 2$$ and $$x$$ odd, solution

These subsets are both mutually exclusive and mutually exhaustive.

I wrapped up the [incorrect] proof as follows:

The conjecture is true for all odd numbers. Every even number has an odd number somewhere in its sequence. $$\Rightarrow$$ The conjecture is true for all evens. $$\Rightarrow$$ The conjecture is true for all $$n \in \mathbb{N}.$$ QED

## HackMIT: Polyglass

I attended HackMIT 2013 and had an absolute blast! Kartik Talwar, Spencer Hewett and I make a fantastic team.

In the turmoil that followed the hackathon (taking a weekend off of schoolwork and research has consequences), it slipped my mind to post our project!

We created Polyglass. A Google Glass application that analyzes the video in slow motion using the Eulerian magnification algorithm to calculate the human pulse from a video frame in quasi-real-time. Using video alone, we achieve the same functionality as a polygraph.

The picture below is a demo of our project; it compares the original video frame to the frame processed by Eulerian Magnification. This processing is an implementation of the Eulerian Magnification framework published by MIT.

Portions of our source are on Kartik’s github.

## CAMEL Poster

The poster I’m using to present my research creating CAMEL is finally finished (full-size version: CAMEL_poster).

In order to condense the entirety of my paper into a viewer-friendly poster, I decided to make diagrams to describe the program’s inner workings in layman’s terms.

If you like the format of this poster: all code used in this project is on github.

#### Introduction to CAMEL

• machine learning program that uses Braille as a language platform. CAMEL is an acronym of ContextuAl MachinE Learning.
• uses context of unknown symbols to deduce meaning and compress information.
• provided the meaning of an initial set of symbols (a dictionary, or dict). CAMEL deduces meanings of unknowns and adds these meanings to the dict.
• grows more accurate as the dict increases in size andoptions. Some symbols differ in meaning depending on their context. These translation options are stored in the dict in the form of Map[String, TranslationOptions].

#### What is Grade 2 Braille

• As English words are composed of letters, Braille words are composed of Braille cells.
• Contractions are special characters used to reduce the length of words.
• Some contractions stand for a whole word. For example: ‘for’ = braille{{for}}; ‘and’ = braille{{and}}; ‘the’ = braille{{the}}.
• Other contractions stand for a group of letters within a word. In the example below, the contraction ‘ing’ is used in the word ‘sing’ and as an ending in the word ‘playing.’ {ing} ; ‘s’ + {ing} = s{ing}; ‘play’ + {ing} = play{ing}
• Grade 1 Braille is uncontracted Braille.

#### Binary Braille

• The Braille alphabet is depicted by a cell that contains six raised/flat dots, numbered one through six beginning with the dot in the upper left-hand corner with the number descending the columns (see figure below).
• To simplify the calculation, I let “0″ = flat, “1″ = raised.
• The 3×2 matrix (Braille cell) is represented as a 1×6 bitstring (Binary Braille).
• Thus, the letter “c”

#### String Processing Method

CAMEL deduces the complex grammar rules of Grade 2 Braille given partially translated text.

CAMEL learns new symbols by taking 2 input text files (Braille text and corresponding English text), and analyzing them until all unknowns are identified, their meanings are found, and said symbols and their meanings are added to the dictionary.

#### Methods of Tagging and Text Extraction

CAMEL must Tag Unknowns & Compare to English(Extract Chunks) to infer symbol meaning. Four different tag types were used: end, front, mid, and full-word.

Below are examples of how these different types of tags were each used to extract meaning.

#### Using Contracted Braille as a Platform

An example of this process infers the symbols that represent en and in using the word penguin (contracted to p{en}gu{in} in Grade 2 Braille).

### Safety of Community

• commercial application in development that will prevent future mislabeling, such as this sign: labeled “Electrical Room” the Braille translates to “stairwell”

### Proof of Concept

• 1st successful automated program that learns compressed Braille
• translation system is effective for arbitrary symbol systems
• language platform easily changed

#### Acknowledgements

The most difficult part of the poster was creating a mature acknowledgements section; I was very tempted to thank…

• insomnia for allowing me to code at 2 am
• coffee for powering me through the day after coding at 2am
• my friend for introducing me to the instant protein-rich “meal” that is trail mix
• my research partner that refused to code in C++, which forced me to learn Python
• Guido van Rossum for inventing said language
• my parents for putting up with me when I immerse myself in research
• my friends for putting up with me when I stop in the middle of a conversation to write down ideas and/or zone-out thinking

Although these were essential to my completion of this project, I think it’s best to not include these points in the poster.