Theory

The game board consists of a pattern of red dots overlaid with a pattern of green dots. Each player takes turns connecting any adjacent pair of dots, either horizontally or vertically.

The human player plays from left to right on the green dots, while the computer plays from top to bottom on the red dots. The player who first makes a continuous line from one side of the board to the other is the winner.

The work done by Prof. Claude Shannon with 'BIRD CAGE', which used an electrical circuit of small light bulbs, and switches to open-circuit or short-circuit each bulb, with the machine's move being determined by observing which bulb was the brightest, suggests that electrical circuit analysis could be used to determine the computer's moves.

Therefore, the game board can be represented as a network of identical-value resistors, instead of light bulbs, with a voltage source applied across it.

The human plays by open-circuiting a resistor. The computer plays by short-circuiting a resistor. The game is won when the network is completely open-circuited or completely short-circuited.

The computer's move can be determined by using network analysis to calculate which resistor has the highest voltage across it (or the highest current flowing through it).

To do this, we need to calculate the currents flowing through each resistor.

Kirchoff's Voltage Law states that the sum of the voltages around a closed loop is zero.

Ohms Law states that V = IR, therefore the voltage across R₁ is (I₀ - I₁) x R₁, where I₀ is the current flowing around loop 0, and I₁ is the current flowing around loop 1.

The sum of the voltages around loop 0, then, is (I₀-I₁)R₁+(I₀-I₂)R₂+(I₀-I₃)R₃+(I₀-I₄)R₄ - V = 0

This can be rewritten as:
I₀(R₁+R₂+R₃+R₄) - I₁R₁ - I₂R₂ - I₃R₃ - I₄R₄ = V

For loop 2, we get: I₁(R₁+R₅+R₈) - I₀R₁ - I₂R₅ - I₅R₈ = 0. Doing this for each loop in the network gives us a set of simultaneous linear equations which can be expressed in matrix form as: [R]*[I]=[V], or:

Now we can use matrix algebra to solve the equations and obtain the currents I₀ through I₁₂.

In the game BridjIt, we use the Gaussian elimination method. Once we have all the loop currents, we can calculate the actual current flowing through each resistor. For example, the current flowing through R₁ is I₀ - I₁ and the current flowing through R₁₃ is I₆ - I₇

All we have to do now, is note which resistor has the maximum amount of current flowing through it, and instruct the computer to make its move.