Chapter 70
“Perfect... what?”
When a difficult word came up, Arin tilted her head.
“I'll explain it as simply as I can. When Arin plays chess, how can she win? What's the best move right now? That's what she always thinks about, right?”
“Yeah! That's what I always think about.”
“That's the normal way to play a game. But mathematicians go one step further and think about the essence.”
I brought a whiteboard and laid it on the living room floor. Then I scribbled on it.
……………………………………
“Is this a winnable game?”
“Does a guaranteed winning strategy exist?”
“Can the game itself be expressed mathematically?”
……………………………………
Arin read the writing aloud, following along.
“A game you can win...? What does that even mean?”
“Right. I mean, a chess player thinks about how to win each individual game right now, right? But a mathematician digs into what kind of game chess itself actually is.”
Arin's eyes widened slightly.
“Oh... it's like that thing you always say, ‘Mathematics abstracts concrete objects and analyzes them.’ ...It feels like looking down from a higher dimension.”
“Right? That's the idea.”
That's my little sister for you.
Her intuition was lightning fast.
“So mathematicians divide games into types. There are several criteria, but if we go by the amount of information, we can split them like this.”
I wrote two big headings on the whiteboard.
[Perfect Information Game]
[Imperfect Information Game]
“Perfect... imperfect...?”
“Yeah. There's only one criterion: what each player knows?”
I wrote one side first.
……………………………………
[Perfect Information Game] : Chess · Go · Othello
……………………………………
“In these games, you can see all the information about both me and my opponent. Look at the chessboard. You can see where my pieces are and where my opponent's pieces are, all of it, right?”
“Yeah! I can see everything.”
“Nothing is hidden. It's treated as if every player has the same information.”
Arin nodded enthusiastically, then pointed to the other side.
“Then what about imperfect information games? Are they the opposite?”
“Exactly.”
I wrote on the other side.
…………………………………………………
[Imperfect Information Game] : Poker · Joker Draw · Mafia
…………………………………………………
“In these games, you don't know your opponent's hand or role. Only I know my hand, and only the opponent knows theirs.”
“Hmm... so nobody can see everything.”
“Right. No one can know all the information in the game. Each player has different information.”
As a simple analogy.
If a streamer covers the broadcast screen as a countermeasure against stream-sniping, that's an imperfect information game.
And if there's no need to cover the broadcast screen, it's a perfect information game.
Arin looked back and forth between the two lists.
“Aha. In chess you can see everything, but in Joker Draw you can't see the backs of the cards.”
“Exactly! And here's something interesting.”
I held up a finger.
“Depending on whether you can see all the information, the mathematical theory used to study the game changes too.”
Tap tap tap-.
I organized it at the bottom of the whiteboard.
…………………………
[Perfect Information Game]
- Combinatorial game theory
- Search algorithms
- Computational complexity
[Imperfect Information Game]
- Probability theory
- Bayesian inference
- Game theory
- Nash equilibrium
…………………………
“That's about the idea.”
Arin stared at the writing for a moment, then puffed out her cheeks.
“Muu—just the names sound hard.”
“It's only the names that are hard. Once you break them down one by one, they're nothing special.”
I tapped the whiteboard, tap-tap.
“Because everything is visible in perfect information games, mathematics developed toward exhaustively analyzing every possibility. Imperfect information games developed toward guessing what's hidden and calculating probabilities.”
“Aha... visible games and invisible games use completely different ways of thinking from the start.”
As expected, Arin pinpointed the key point exactly.
“Then, sis, what should I learn first?”
Arin asked, fiddling with her medal.
I thought for a moment, then grinned.
“The visible side is simpler, so let's start with perfect information games. And among them—”
I wiped the writing off the whiteboard.
“I'll bring out a game that's the simplest, cleanest, and therefore mathematically fully solved.”
Arin's eyes sparkled as she leaned in close.
“What is it?”
Pop-
I stood up and brought back a set of go stones from the bedroom cabinet.
“It's called Nim. In Korean, it's just the 'stone-removal game.'”
Clatter-clatter-.
I grabbed a handful of black go stones and rolled them across the living room floor.
“The rules are really simple. Listen carefully.”
……………………………………………………
[Stone-Removal Game Rules]
- There are several piles of stones.
- On my turn, I choose one pile and take stones from it.
- I can take as many as I want, but I must take at least one.
- The person who takes the last stone wins!
……………………………………………………
Arin raised her hand while reading the rules.
“Sis, can you take from multiple piles at once?”
“No. Just one pile at a time.”
“Hmm... compared to the board games we've played so far, this looks super easy.”
“And let's decide on one term. I'll call the person who removes stones first the first player, and the one who goes second the second player.”
“First player, second player. O-kay.”
✒️✒️✒️
I snapped off a single go stone and placed it on the floor.
…………
●
…………
“Okay, let's start with the easiest one. One pile, one stone. Arin goes first. Go ahead.”
Swoosh-. Arin picked up the stone.
“…Huh? That's it?”
“Yep. You took the last stone, so Arin wins!”
“Ehh, that was way too easy.”
This time, I placed three stones in one pile.
…………
●●●
…………
“Arin goes first again. What will you do?”
“Hmph, I'll just take all three!”
Swooosh-. Arin swept the stones away.
“I won again!”
“Right? If there's only one pile, the first player just sweeps it all away. So Arin, what feature would a one-pile game have?”
“Does the first player automatically win this?”
“Yeah. With one pile, it's a first-player win. Remember that.”
“Okay. First-player win.”
Arin nodded repeatedly.
“Now I'll increase it to two piles.”
…………
●
●
…………
“Arin still goes first. Try to win.”
“Heheh, I'll win again!”
Arin took one of the stones from the top pile.
…………
●
…………
Then I picked up the one remaining stone.
“I win.”
“…Huh? I lost!”
Arin's eyes went round.
“It's the same if we do it again. Since you can only take from one pile at a time, once you empty one side, the remaining side is automatically mine.”
“Ugh...”
“This is a second-player win. In other words, the player who goes second always wins.”
This time, I placed two stones on each side.
…………
●●
●●
…………
“What about this? Think you can win this time?”
“I won't fall for it this time! I'll take both from the top!”
Arin cleared out the top pile.
…………
●●
…………
Then I wiped out the two stones on the bottom as well.
“…Huh?”
“I win.”
Again from the beginning.
…………
●
●●
…………
…………
●
●
…………
When Arin took one from the top, I took one from the bottom.
When Arin took one more, I took one more too.
The last stone was mine again.
“Sis, why do you keep copying me?”
“Hehe. You noticed? That's the mirror strategy.”
I pointed left and right with both hands.
“If Arin takes two from one side, I take two from the opposite side. If Arin takes one, I take one too. Always keep both sides perfectly matched! Then the piles stay symmetrical, and the last stone always ends up being mine.”
Arin thought for a moment, then clapped her hands with a smack.
“Ah! Then if there are two piles and they're the same, the second player always wins?”
“Exactly. Whether it's (1,1), (2,2), or (3,3), if the two piles are the same, it's always a second-player win.”
“Ah, no wonder! It looked like I was doomed no matter what I did!”
Arin put on a confident expression.
I smirked.
“Really? Then how about this one.”
I set out new stones. This time there were three piles.
…………
●
●●
●●●
…………
“(1, 2, 3). Arin, you're first. Think you can win?”
“Hmph, of course!”
Arin confidently took one stone from the largest pile.
…………
●
●●
●●
…………
I took the pile that had just one stone.
…………
●●
●●
…………
“…Huh?”
It was the same second-player-win shape as before.
Arin blinked.
A few moves later, the last stone was mine.
“I lost... do it again.”
“Okay.”
Once more from the beginning.
This time Arin tried touching the small pile.
…………
●
●●
●●●
…………
…………
●●
●●●
…………
Then I cheekily plucked one stone from the pile with three stones.
…………
●●
●●
…………
The exact same shape as before.
The last stone was mine again.
“Hmm... huh? Wha—?”
Arin rearranged the stones here and there, racking her brain.
“This game is weird.”
Hmm—hmm—.
Arin puffed out her cheeks and groaned for a long while.
Earlier there was a neat rule that 'two identical piles means a second-player win.'
But once there were three piles, her head got all tangled up.
“Sis... no matter how much I calculate, I can't see a winning move. Is this also a second-player win?”
Arin finally looked up at me as if surrendering.
I gathered the scattered stones back into (1, 2, 3) and said,
“That's right.”
“See? It's not that I'm bad, right? Phew—.”
Arin let out a sigh of relief.
Losing at reading ahead bruised Arin's pride, but if the game itself was the problem, she figured that was at least okay.
“But the shapes are complicated, right? Old-time mathematicians worried about the same thing: 'Isn't there a way to tell who wins at a glance?'”
“Is there such a way?”
“Yeah. That's the secret of this game.”
I brought over the whiteboard and wrote on it.
“Let's write the number of stones in each pile in binary. You know binary, right?”
“Yep! The one that only uses 0s and 1s!”
Thanks to my ultra-early education, Arin had already grasped the concept of binary even at age four.
…………
1 = 001
2 = 010
3 = 011
…………
“Now look straight down each column. If there are an odd number of 1s in that column, write 1; if there's an even number, write 0. That's called XOR. It's an operation computers use a lot. In combinatorial game theory, it's also called the Nim-sum.”
“Nim-sum...”
I lined them up vertically and wrote them out.
“Put simply, think of it as writing the numbers in binary and then adding each digit with a rule that says 1+1=0.”
…………
001
010
011
—— (xor)
= 000
…………
“Start from the far right. How many 1s are there?”
“Hmm... 1, 0, 1, so... two!”
“Two is even. So the result is 0. What about the middle column?”
“0, 1, 1, so two! Even again! So 0!”
“That's right. The left column is all 0s. So the result is 000, meaning 0.”
I tapped the circled 0.
“When the XOR of the pile counts comes out to 0, we call that a state with a Nim-sum of 0. And—”
……………………………
Summary.
For Nim, the following holds.
Nim-sum = 0 → second-player win
Nim-sum ≠ 0 → first-player win
……………………………
“This is the essence of the stone-removal game, as analyzed by mathematicians.”
Arin looked back and forth between the whiteboard and the piles of stones.
“Then... (1,2,3) has Nim-sum 0, so...”
“Yep. Second-player win. No matter how hard the first player Arin struggles, it was a game she couldn't win from the start.”
“Gasp! So that's why I kept losing!”
Arin smacked her thigh with her palm.
“Okay, then let's do the opposite. I'll give you a position Arin can actually win.”
I laid out new stones.
…………
●●●
●●●●
●●●●●
…………
“(3, 4, 5). Arin, calculate the Nim-sum.”
“Got it.”
Arin scribbled on the whiteboard.
…………
3 = 011
4 = 100
5 = 101
…………
…………
011
100
101
—— (xor)
= 010
…………
“Only the middle column has an odd number of 1s... 010! Oh, it's not 0!”
“Right. And if it's not 0?”
“First-player... win! Then I can win, right?”
“Yep. But to win, your first move has to make the piles' Nim-sum 0. Because that shape is a second-player win. Which pile should Arin touch on her first move?”
Arin spent a while groaning, then pointed at the biggest pile.
“From the 5-stone pile... hmm... or if I take two from the 3-stone pile...!”
Swoosh-. Arin took two stones from the 3-stone pile, making it (1, 4, 5).
…………
●
●●●●
●●●●●
…………
“Then check for yourself whether this shape really is a second-player win.”
Arin started calculating the binary on her notebook.
…………
1 = 001
4 = 100
5 = 101
…………
…………
001
100
101
—— (xor)
= 000
…………
“000! It became 0! Now you're in a second-player-win state, right?”
“Correct.”
After that, a few moves went back and forth.
No matter where I touched, Arin calmly returned the Nim-sum to 0.
…………
●
●●●●
●●●
…………
“Hmm... here I'll... ah, I'll make the (1,2,3) shape!”
…………
●
●●
●●●
…………
“Then I'll do this.”
…………
●
●●
●
…………
“Then I'll leave only two piles! That makes it a second-player win!”
…………
●
…………
“Well done, Arin.”
…………
●
…………
The last stone went to Arin.
“Yes! I won!”
Arin thrust both arms into the air.
“Sis! Once I learned the game's secret, I won!”
“Hehe. That's the power of math.”
“So amazing!”
Arin's eyes sparkled like stars.
Pat-pat-.
I patted Arin on the head.
✒️✒️✒️
As I patted her head, Arin suddenly looked up.
“Sis.”
“Yeah?”
“Then does chess have a secret like this too? Can you find a way to always win?”
Oh. She took what she'd just learned and immediately applied it to a game she liked.
Her ability to apply things was seriously quick.
“Good question. The stone-removal game we just looked at was one of the simplest cases among perfect information games. But actually—”
I paused for a moment.
“Chess and Go both have answers, in theory.”
“Really?”
Arin widened her eyes in surprise.
“Yeah. Listen carefully. Games like chess and Go, where players take turns, where luck doesn't get involved, where all the information is visible, and where the game must eventually end—those are called 'finite perfect information games.'”
I wrote it on the whiteboard.
……………………………………
[Summary]
Every finite perfect information game must fall into one of the following three categories.
…………
- First-player win
- Second-player win
- Possible to force a draw
……………………………………
It's already fixed as one of those three if both players only make optimal moves.
Arin stared at the summary I'd written.
“Then... before the match even starts, chess is already mathematically determined to be a White win, a Black win, or a draw?”
“Yes. More precisely, if both sides play perfectly, the result is fixed as one of the three. So theoretically, a best strategy for chess that never loses already exists.”
“Whoa... then you don't even need to play chess, do you? If you memorize the answer, you win automatically!”
Arin said excitedly. I shook my head, raising my index finger.
“That's where the twist is. 'An answer exists' and 'you can find that answer' are completely different matters.”
“…Huh? There's an answer, but you can't find it?”
Arin tilted her head, puzzled.
“The stone-removal game has already been completely solved mathematically—who wins from which shape, and what the best move is. You just calculate the Nim-sum and you're done.”
“Like what we just did earlier!”
“Yep. And there's tic-tac-toe too—the one where you place O and X alternately.”
“I know! You win if you make three in a row!”
“That one is also a completely solved game. It has been proven that if both sides play well, it always ends in a draw. And gomoku under the standard rules has also been shown to be a first-player win.”
I took a quick breather.
“But chess has way, way, way too many possible positions.”
I wrote in huge letters on the whiteboard.
……………………………………
[Number of Possible Game States]
Chess ≈ 10⁴⁰
Go ≈ 10¹⁷⁰
……………………………………
“10 to the 40th power. It's a number with forty zeroes after the 1.”
“Whoa, that's insanely huge...”
“Go is even more enormous. It's roughly 10 to the 170th power. And Arin, want to know something interesting?”
“Yeah, yeah!”
“Even if you gathered up every atom in the entire observable universe, you'd only get about 10 to the 80th power.”
Arin dropped her jaw.
“Th... then Go is...?”
“The number of possible Go positions is far, far greater than the number of atoms in the entire universe.”
“Uaaah... I can't even imagine that...”
Smoke practically steamed out of Arin's head.
“So even though we know an answer exists, no computer in the world—no matter how fast—can calculate all of it. Even if you let it run until the universe ends, it still wouldn't finish.”
“Until the universe ends...”
Arin mulled over those words.
The fact that the answer key definitely exists somewhere, yet there may never be a way to open and look at it, seemed strangely fascinating to her.
But I added one more thing there.
“But Arin, I actually think that's a good thing.”
“Whyyyy?”
“Imagine if the answer to chess were completely revealed. If from the first move to the last, everything about how to play to win were all known.”
Arin thought for a moment, then said slowly,
“Hmm... then there's no need to actually play. You'd just memorize the answer.”
“Right. Nobody would play then. There'd be no fun at all.”
I lightly tapped the gold medal Arin had been fidgeting with.
“This medal Arin won last time shines because it's actually from a game where nobody knows the answer yet. People strain their brains and think through each move, and that's where the real competition comes from—that's what makes it a sport.”
Arin quietly looked down at her medal. Then she gave a heh and smiled.
“Heheh. My gold medal is cool, right?”
Cute little thing.
“Okay, let me summarize everything we learned at once.”
……………………………………
[Perfect Information Game]
- Nim, the stone-removal game, is a representative example of a perfect information game that has already been completely solved.
- Using XOR, you can calculate whether it's a first-player win or a second-player win.
- Chess and Go are also perfect information games, so in theory, an answer exists.
- But the number of possibilities is so huge that actually calculating it is almost impossible.
- The fields that study this are combinatorial game theory and computational complexity theory.
……………………………………