# Minimax Search and the Structure of Cognition!

*(This is a blog post adaptation of a talk I gave at !!Con West 2019!)*

It all started at my old dayjob, where some of my coworkers had an office chess game going. I wanted to participate and be part of the team, but I didn't want to invest the effort in actually learning how to play chess well. So, I did what any programmer would do and wrote a chess engine to do it for me.

(Actually, I felt like writing a chess engine was too much of a cliché, so I decided that *my* program was an AI for a game that *happens* to be exactly like chess, except that everything has different names.)

My program wasn't actually terribly good, but I learned a lot about *how to think*, for the same reason that building a submarine in your garage in a great way to learn how to swim.

Consider a two-player board game like chess—or tic-tac-toe, Reversi, or indeed, *any* two-player, zero-sum, perfect information game. Suppose we know how to calculate how "good" a particular board position is for a player—in chess, this is traditionally done by assigning a point value to each type of piece and totaling up the point values of remaining pieces for each player. Continue reading

# Group Theory for Wellness I

(Part of Math and Wellness Month.)

Groups! A group is a set with an associative binary operation such that there exists an identity element and inverse elements! And my *favorite* thing about groups is that all the time that you spend thinking about groups, is time that you're *not* thinking about pain, betrayal, politics, or moral uncertainty!

Groups have subgroups, which you can totally guess just from the name are subsets of the group that themselves satisfy the group axioms!

The *order* of a finite group is its number of elements, but this is not to be confused with the order of an *element* of a group, which is the smallest integer such that the element raised to that power equals the identity! Both senses of "order" are indicated with vertical bars like an absolute value (|*G*|, |*a*|).

Lagrange proved that the order of a subgroup divides the order of the group of which it is a subgroup! History remains ignorant of how often Lagrange cried.

To show that a nonempty subset *H* of a group is in fact a subgroup, it suffices to show that if *x*, *y* ∈ *H*, then *xy*⁻¹ ∈ *H*.

Exercise #6 in §2.1 of Dummit and Foote *Abstract Algebra* (3rd ed'n) asks us to prove that if *G* is a commutative ("abelian") group, then the *torsion subgroup* {*g* ∈ *G* | |g| < ∞} is in fact a subgroup. I argue as follows: we need to show that if *x* and *y* have finite order, then so does *xy*⁻¹, that is, that (*xy*⁻¹)^*n* equals the identity. But (*xy*⁻¹)^*n* equals (*xy*⁻¹)(*xy*⁻¹)...(*xy*⁻¹), "*n* times"—that is, pretend *n* ≥ 3, and pretend that instead of "..." I wrote zero or more extra copies of "(*xy*⁻¹)" so that the expression has *n* factors. (I usually dislike it when authors use ellipsis notation, which feels so icky and informal compared to a nice Π or Σ, but let me have this one.) Because group operations are associative, we can drop the parens to get *xy*⁻¹ *xy*⁻¹ ... *xy*⁻¹. And because we said the group was commutative, we can reörder the factors to get *xxx*...*y⁻¹y⁻¹y*⁻¹, and *then* we can consolidate into powers to get *x*^*n* y^(−*n*)—but that's the identity if *n* is the least common multiple of |*x*| and |*y*|, which means that *xy*⁻¹ has finite order, which is what I've been trying to tell you this entire time.

# Forgive or Forget ("Or", Not "And"): A Trade-Off in Wellness Engineering

Forgiveness is an important input into Wellness, but contrary to popular belief, Forgiveness is *incompatible* with Forgetting. You can't just Forgive *in general*, you have to Forgive some *specific* sin in particular—but a *vague* description of a particular sin still corresponds to a vast space of possible sins matching that vague description.

A toy example for illustration: if you try to Forgive a three-digit integer with a 2 in the tens place, the moral force of your Forgiveness needs to spread out to cover all 9·10 = 90 possibilities (120, 121, ... 928, 929), which dilutes the amount of Forgiveness received by each integer—except the actual situation is *far* more extreme, because real-world sins are *vastly* more complicated than integers.

To truly Forgive a sin, You need to know *exactly* what the sin was and *exactly* why it happened. In order to withhold punishment, you need to compute what the optimal punishment *would* have been, had you been less merciful.

Thus, bounded agents can only approximate true Forgiveness, and even a poor approximation (*far* below the theoretical limits imposed by quantum uncertainty, which are themselves far below Absolute Forgiveness under the moral law) can be extremely computationally expensive. What we cannot afford to Forgive—where it would be impractical to mourn for weeks and months, analyzing the darkness in pain—we instead Forget.

This is how I will stop being trash, after five months of being trash. The program that sings, *I was wrong; I was wrong—even if my cause was just, I was wrong*, does not terminate. Even as the moral law requires that it finishes its work, the economic law does not permit it: it *must* be killed, its resources reallocated to something else that helps pay the rent: something like math, or whatever Wellness can exist in the presence of sin.

# The Typical Set

(Part of Math and Wellness Month.)

Say you have a biased coin that comes up Heads 80% of the time. (I like to imagine that the Heads side has a portrait of Bernoulli.) Flip it 100 times. The naïve way to report the outcome—just report the sequences of Headses and Tailses—costs 100 bits. But maybe you don't have 100 bits. What to do?

One thing to notice is that because it was a biased coin, some bit sequences are *vastly* more probable than others: "all Tails" has probability 0.2^{100} ≈ 1.268 · 10^{−70}, whereas "all Heads" has probability 0.8^{100} ≈ 2.037 · 10^{−10}, differing by a factor of *sixty orders of magnitude*!!

Even though "all Heads" is the uniquely most probable sequence, you'd still be pretty surprised to see it—there's only *one* such possible outcome, and it only happens a 2.037 · 10^{−10}th of the time. You *probably* expect to get a sequence with *about* twenty Tails in it, and there are *lots* of those, even though each individual one is less probable than "all Heads."

Call the number of times we flip our Bernoulli coin *N*, and call the entropy of the coinflip *H*. (For the 80/20 biased coin, *H* is ⅕ lg 5 + 4/5 lg 5/4 ≈ 0.7219.)

It turns out for sufficiently large *N* (I know, one of *those* theorems, right?), *almost all* of the probability mass is going to live in a subset of 2^{NH} outcomes, each of which have a probability close to 2^{−NH} (and you'll notice that 2^{NH} · 2^{−NH} = 1).

# May Is Math and Wellness Month

(Previously, previously.)

Do you ever spend five months in constant emotional pain waging a desperate and ultimately unsuccessful behind-the-scenes email campaign with the aim of securing a public clarification of a trivial philosophy-of-language issue because you're terrified that your robot cult's inability to correct politically-motivated philosophy errors implies that you've lost the Mandate of Heaven and are therefore unfit to prevent the coming robot apocalypse?

Yeah, me neither.

Did you know that May is Math and Wellness Month (source: me)?? Math and Wellness month is traditionally celebrated by performing super-well at one's dayjob, going to the gym a lot, and studying math in the evenings!

# "Where to Draw the Boundaries?"

# Another Desperate, Fervent Wish for *Star Trek: Discovery*

(Previously, previously, previously, previously, previously.)

future-timeskip episode in which the AI from TOS S2E24 "The Ultimate Computer" starts taking over the galaxy, until being countered by an upload superorganism composed of copies of Lt. Cmdr. Sylvia Tilly

# Concerning Loyalty and Revenge

Retarget loyalty intuitions onto specific humans (never ideologies or collective identities). Retarget revenge intuitions onto patterns of incentives (never specific humans).

# The Right to Life, Conjugated

She's a ward of the state; you have an inalienable right to live; I'm literally more useful alive rather than dead with respect to the values of powerful coalitions.

# Concerning Motives for Cooperation

Always be peaceful and tell the truth to your friends because you love and trust them. Always be peaceful and tell the truth to cops, schoolteachers, psychiatrists, CPS agents, *&c*. because you're outgunned and bad at lying. Don't be confused about your reasons for doing things, even if you always end up doing the same thing.

# Concerning Frame Control Via Salient Scenarios

"We need to institutionalize people in order to prevent them from hurting themselves" has the same memetic-superweapon structure as "We need to torture terrorists to get them to tell us where they've hidden the suitcase nuke." The scenario as stated obviously has consequentialist merit (death is worse than prison, megadeaths are worse than torture), so you'd have to be some kind of *huge asshole*—or a former suspected terrorist—to say, "I claim that this hypothetical scenario is not realized nearly as often as you seem to be implying and therefore falsifiably predict that many of your alleged real-world examples will fall apart on further examination."

# Tit for Half-Tat

"—but I am not a vengeful man."

"..."

"I mean, I'm *proportionately* vengeful, within the bounds of the moral law."

# Object *vs*. Meta Golden Rule

"I know it might seem like a lot to ask, but I wouldn't hesitate to do the same for you if our positions were reversed."

"I don't doubt that. But I can't help but notice that it would be easier for you to say it if the fact that they *aren't* reversed is—somehow—*not a coincidence*."

# Patches Welcome

"You look happy. Good day at work?"

"Yes, the open-source library we're depending on didn't have the functionality we need."

"That sounds like a bad thing."

"No, I mean, it *didn't*."

# April Is Separability Month

It is now April! Did you know that April is one of the months in which every compact metric space is separable?

Proof. Let it be April, and let M be a compact metric space. Because M is compact, it is totally bounded, so for all n∈ℕ, we can cover M with finitely many open balls of radius 1/n. The centers of all such balls are a countable set which we can call C. But C is dense, because an arbitrary point p∈M is a limit point of C: an ε-neighborhood of p must contain the center of one the balls in our covering of M with ε/2-balls. Thus M contains a countable dense subset.

# Best Alternative to a Negotiated Ontology

"I can't stand being apart any longer. You win. Whatever your demands are, I'll meet them."

"I want you to stop thinking of everything as a negotiation and relate to me as a human being."

"Okay, maybe not that one."

# Binge-Purge

```
$ history | grep freeciv
605 freeciv
606 sudo apt-get install freeciv
607 sudo apt-get remove freeciv
652 rm -rf ~/.freeciv/
706 sudo apt-get install freeciv
722 sudo apt-get remove freeciv
735 rm -rf ~/.freeciv/
752 sudo apt-get install freeciv
754 sudo apt-get remove freeciv
768 rm -rf ~/.freeciv/
785 history | grep freeciv
```

# Some Shuffling Required

"I'm going to need about 600 bits of entropy for this. Can you go the store and pick up some playing cards for me? Let's see, six hundred divided by log-base-two fifty-two-factorial—yes, three packs should be enough."

*(Later, opening them ...)*

"What the—!?"

# "Give Anything"

As a freshman on my high school's cross country team, our captain told me that to be a good runner, you needed to love pain.

I objected: a great runner could love to *race*, I said, and endure the pain only for the sake of competing and winning.

It's only fifteen years later (practically one foot in the grave), that I now see that *I was wrong* and he was right.

You can run out of habit or you can run because Coach would notice if you skip practice, but you cannot run because of the *strictly instrumental effect* that not-running would have on your goals. Our minds aren't built that way; what is separable conceptually is not separable *architecturally*.

Ultimately, to not sacrifice the gift, you have to love pain. You have to love life.