6
$\begingroup$

Throughout this year, I have been in charge of a linear algebra course aimed at engineering school. In this course, I asked my students to work on a final project involving finding a winning strategy for the "Lights Out" game - https://en.wikipedia.org/wiki/Lights_Out_(game).

This project was very beneficial for them because the following was required:

  1. Solve the problem using linear algebra techniques for the 3x3 case.
  2. Program the solution for an nxn board in Python.
  3. Implement it physically using Arduino for the 4x4 case.

I would like to repeat the experience, but not exactly the same one.

My question is, does anyone know of any games that can be solved using linear algebra tools? Or do you know of any interesting projects to work on?

Thank you in advance.

$\endgroup$
1
  • 2
    $\begingroup$ Computer graphics make heavy use of linear algebra. Are you interested in projects involving that? $\endgroup$
    – TomKern
    Nov 4, 2023 at 17:48

3 Answers 3

1
$\begingroup$

Since this is for engineering students, perhaps the realm of Markov Decision Processes would be of interest. The canonical game is gridworld.

enter image description here

A standard source is the textbook Artificial Intelligence: A Modern Approach by Russell and Norvig. In the fourth edition, gridword is analyzed in Chapter 17. There are many, many resources on the web. Many resources!

The game involves an agent that attempts to navigate to the reward state in a probabilistic environment, where sometimes it stochastically veers off at right angles.

Finding the optimal policy to maximize rewards uses the Bellman Equation. If we have $n$ states $s$ and an arbitrary policy $\pi$, then we have a linear system of $n$ equations in $n$ unknowns for the state-values $V^{\pi}(s)$ of the policy.

The linear system looks like this:

$$V^{\pi}(s) = R(s, \pi(s)) + \gamma \sum_{s' \in S} P(s' | s, \pi(s)) V^{\pi}(s') $$

Here the coefficients $ P(s' | s, \pi(s))$ are related to the transition probabilities of the environment, and $R(s, \pi(s))$ are inhomogeneous terms related to the rewards for state-action pairs. The so-called "discount factor" is denoted by $\gamma$.

Policy iteration is an algorithm to find the optimal policy. We start with a random policy $\pi$ and solve the linear system for $V^{\pi}$. Then follows "policy improvement" that involves adjusting $\pi$ so the actions point to the highest value $V^{\pi}$. Now that we have a new and improved policy $\pi_1$, we solve the resulting linear system for the new policy. We repeat until the policy converges.

When the number of states is large, the system of linear inhomogeneous equations is solved using iterative numerical methods. But when the number of states is not overwhelming, we can solve the linear system using methods taught in a standard linear algebra course.

Admittedly, it takes some effort to understand the context of the problem because of the notation and concepts. But it is a very nice application of solving linear systems, and gridworld is the "hello world" for reinforcement learning.

$\endgroup$
1
$\begingroup$

This one is similar, but maybe slightly more general: light switch subsets. One feature of these problems is that a solution can be found just using row reduction, however, one has to work over $Z/2Z$ to reflect the on/off properties. Some possible benefits of this:

  • By translating each row operation to "switches and bulbs" this can help visualize what these row operations are doing. I could imagine making a cool animation as well.
  • It can help students to think about whether or not their favorite RREF algorithm will work with a number system other than the real numbers. For $Z/2Z$ there is never any need for division, but what would happen for $Z/4Z$? What would a "reduced" form look like over this system.
  • Implementing a RREF algorithm over $Z/2Z$ in Python can be a fun project.
  • If the students have taken an algorithms class this helps them experience how "fast" RREF is as compared with taking all subsets of lightswitches.
$\endgroup$
1
$\begingroup$

When I was teaching linear algebra, I made 3 HTML/javascript games for students:

  1. Switches and lightbulbs

This is pretty much what Adam described and the interface should be self-explanatory

  1. Intersection traffic counters

The goal is to determine how many vehicles went through the intersection in each particular way from the entrance and exit counter readings. The point was that it is generally impossible if the left turn from the side road into the main horizontal road is allowed but if you prohibit it (by clicking on the sign), the linear system becomes well-posed.

  1. Hill cipher

The allowed text symbols are the 26 lowercase letters of the Latin alphabet, period, question mark, and star (The last one will replace everything else when parsing and will be added if the text length is not divisible by 3). The ciphering/deciphering is done in groups of 3 using the matrix specified by the user (all computations are modulo 29).

This is just to give you some ideas. You can play with these in various ways or you can ask students to write something similar from scratch or mimicking the existing code. The choice is yours. :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.