space and games

I’m investigating the Japanese language.

A Kanji word block is a 3 x 3 block of Kanji characters in which each row and each column forms a word, and no character appears more than once. Thus the word block contains six words in all. Using Jim Breen’s WWWJDIC as my reference, I found that there are 12 possible word blocks. Here is one:

So a person-space-model is a humanoid, a number-value-change is a numeric conversion, and so on.

We show Sam the item.
“What is this?” we ask.
“I don’t know,” says Sam.
We say, “It is the item.”
Again, we ask Sam, “what is this?”
“The item,” Sam repeats.
Sam has received his first lesson.

We show Sam the item.
“What is this?” we ask.
“I’m not sure,” says Sam, “but I think it is the item.”
“Of course it is the item! Why are you not sure?”
Sam has no reply.

The thing is very similar to the item.
We show Sam the thing.
“What is this?” we ask.
“It is the item!” Sam shouts confidently.
“It is not the item! It is the thing!”
Was Sam’s earlier hesitation justified?

We show Lisa the item.
“What is this?” we ask.
“I don’t know,” says Lisa.
We say, “It is the item.”
Again, we ask Lisa, “what is this?”
“The item,” Lisa repeats.
We show Lisa the thing.
“What is this?” we ask.
“I don’t know,” says Lisa.
We say, “It is the thing.”
Again, we ask Lisa, “what is this?”
“The thing,” Lisa repeats.
Lisa has received two lessons.

Google has some very cool n-gram data sets available for download. Alas, the files are quite large. For example, the 3-grams are split into 200 zip files, each weighing in at 440 MB. That’s about 88 GB total.

The 1-grams are much lighter, totaling 2 GB. I was able to reduce this to about 35 MB by throwing away the time information (the original files indicate the year each data point came from). That’s smaller than the original files by a factor of 57.

1-grams in lexicographical order | 1-grams by count | 1-grams by length

The 2-grams, 3-grams, and so on could also be similarly compressed by anyone who can get the files. I’d be happy to help if anyone wants to do this.

The Japanese writing system includes hiragana, katakana, and kanji. While hiragana and katakana represent sounds, kanji represent meanings. There are a lot of good places to start with learning Kanji. The JLPT N5 kanji list is a set of kanji that appear in the first of 5 standardized tests. Here is a list of the 100 most commonly-used Kanji on the internet.

Kanji may represent words by themselves, or they may be combined into larger units of meaning called compounds. I was interested in finding a set of kanji with a lot of combinatorial power — the ability to represent many distinct compounds without using any kanji not in the set.

For this project I used Jim Breen, jisho.org, Python, and a greedy heuristic. This solution is unlikely to be optimal. I’d like to share a truly optimal solution (with proof) later, but I don’t know how long that will take. Here’s what I’ve got now:

Here are the compounds (1309 items):

日, 日日, 直, 直直, 日直, 生, 生生, 生日, 中, 中生, 中日, 直中, 日中, 中中, 生中, 人, 人生, 中人, 人人, 人日, 後, 後生, 後日, 人後, 生後, 直後, 後後, 後人, 前, 人前, 生前, 前後, 前人, 前生, 前日, 中前, 直前, 前前, 一, 一直, 一人, 一生, 一日, 一一, 中一, 一人前, 一日中, 一日一日, 一人一人, 後生一生, 年, 後年, 生年, 前年, 中年, 年後, 年生, 年中, 一年, 年年, 一年生, 一年中, 一年前, 月, 一月, 月日, 年月, 月月, 日月, 前月, 月中, 後月, 人月, 年月日, 生年月日, 半, 一半, 後半, 中半, 半生, 前半, 半月, 半日, 半年, 半半, 生半, 後半生, 半人前, 前半生, 一年半, 半年後, 夜, 月夜, 前夜, 日夜, 半夜, 夜前, 夜中, 一夜, 夜半, 夜夜, 夜直, 後夜, 中夜, 一夜中, 夜夜中, 一日一夜, 長, 生長, 長月, 長年, 年長, 半長, 夜長, 長長, 日長, 長夜, 長生, 人長, 直長, 長日月, 間, 一間, 間中, 月間, 人間, 中間, 日間, 年間, 夜間, 間間, 一年間, 数, 数数, 間数, 数人, 数日, 数年, 中数, 年数, 半数, 人数, 日数, 数間, 数日間, 数日後, 数年間, 数年前, 時, 一時, ひととき, 時間, 人時, 日時, 半時, 時時, 時半, 時人, 時日, 時数, 一時間, 長時間, 数時間, 半時間, 分, 一分, 時分, 中分, 年分, 半分, 分数, 夜分, 数分, 分間, 一分半, 時分時, 数分後, 一人分, 数分間, 何, 何月, 何時, 何人, 何日, 何年, 何分, 何何, 何時間, 何年間, 何年生, 何時何時, 何時時分, 何時何分, 々, 数々, 後々, 人々, 年々, 一々, 直々, 月々, 時々, 中々, 長々, 何々, 半々, 日々, 前々, 間々, 夜々, 夜々中, 本, 一本, 本人, 本数, 本日, 本年, 日本, 本々, 本本, 本分, 本月, 本間, 日本間, 日本人, 日本中, 生一本, 日本一, 中日本, 日本時間, 御, 御前, 御中, 御数, 御人, 御御, 御々, 御生, 御年, 御本, 御分, 手, 一手, 後手, 手間, 手数, 手前, 手本, 中手, 手中, 手長, 本手, 人手, 御手, 長手, 手々, 手手, 御手前, 御手数, 御手手, 後手後手, 大, 一大, 御大, 大手, 大人, 大生, 大日, 大半, 大分, 長大, 大本, 大数, 大御, 大前, 大年, 大人数, 家, 家人, 家中, 家長, 後家, 人家, 生家, 大家, 分家, 本家, 一家, 家々, 家家, 長家, 御家人, 山, 山間, 山中, 人山, 前山, 一山, 山々, 山山, 山家, 山手, 山人, 大山, 本山, 御山, 後山, 山月, 大本山, 小, 小山, 小人, 小数, 小生, 大小, 中小, 小手, 小夜, 小一, 小間, 小家, 大中小, 小人数, 小半日, 小半時, 大小前, 小一時間, 国, 一国, 国家, 国手, 国大, 国中, 小国, 大国, 中国, 半国, 本国, 国々, 国国, 国本, 国人, 山国, 生国, 御国, 中間国, 中国人, 本国人, 国家間, 日本国, 三, 三月, 三国, 三時, 三人, 三直, 三日, 三分, 三本, 三年, 三大, 中三, 三家, 御三時, 三国一, 三大国, 三日月, 御三家, 三日間, 三国人, 三年生, 三日三夜, 下, 下家, 下御, 下国, 下山, 下手, 下人, 下半, 時下, 直下, 年下, 下々, 下下, 手下, 月下, 三下, 下前, 下手人, 三下半, 上, 御上, 山上, 上下, 上手, 上人, 上前, 上長, 上半, 直上, 年上, 上々, 上上, 長上, 上家, 上中下, 上御一人, 一上一下, 上手下手, 下手上手, 身, 一身, 身上, 身長, 身分, 生身, 前身, 半身, 分身, 人身, 中身, 長身, 御身, 身中, 小身, 大身, 三身, 直身, 後身, 一身上, 上半身, 下半身, 足, 一足, 下足, 手足, 上足, 人足, 前足, 足下, 後足, 日足, 小足, 大足, 長足, 足長, 生足, 足半, 足中, 三本足, 御御足, 御々足, 代, 一代, 時代, 上代, 前代, 代人, 代数, 大代, 年代, 代々, 代代, 身代, 三代, 後代, 御代, 手代, 足代, 間代, 本代, 月代, 中生代, 大時代, 大御代, 三国時代, 名, 一名, 下名, 家名, 国名, 人名, 数名, 前名, 大名, 本名, 名家, 名手, 名人, 名前, 名月, 名分, 御名, 名山, 名代, 名数, 小名, 何名, 三名山, 日本三名山, 物, 下物, 何物, 御物, 小物, 上物, 人物, 生物, 代物, 大物, 本物, 名物, 一物, 長物, 物日, 物前, 一人物, 下手物, 小間物, 大人物, 時代物, 年代物, 一生物, の, 本の, 何の, 長の, 分の, 大の, 物の, 月の物, 間の手, 身の上, 下の下, 家の人, 山の手, 国の本, 本の間, 本の名, 手の物, 後の月, 小の月, 大の月, 分の一, 日の本, 中の下, 一日の長, 一家の長, 三分の一, 御手の物, 下の名前, 何の何の, 子, 子年, 子分, 年子, 分子, 一子, 御子, 中子, 日子, 長子, 子月, 小子, 間の子, 人の子, 数の子, 中間子, 一人子, 上の子, 子の時, 下の子, 子の日, 分生子, 一の御子, 生物分子, 女, 下女, 三女, 山女, 子女, 女子, 女人, 女生, 女中, 大女, 長女, 一女, 女手, 女御, 女物, 年女, 小女, 日女, 下女中, 女の子, 女の人, 女子大, 上女中, 女の手, 小女子, 女御子, 女子大生, 学, 家学, 学生, 学長, 学年, 学名, 後学, 小学, 数学, 大学, 中学, 夜学, 国学, 本学, 女学生, 小学生, 人間学, 生物学, 代数学, 大学生, 中学生, 日本学, 中学年, 学生時代, 夜間中学, 女子学生, 女子大学, 小中学生, 分子生物学, 部, 一部, 下部, 学部, 後部, 上部, 前部, 大部, 中部, 部下, 部数, 部長, 部分, 本部, 三部, 小部, 足部, 一部分, 学部生, 学部長, 山間部, 大部分, 夜間部, 女子部, 本部長, 小部分, 学生部長, 学部学生, 中部時間, 文, 一文, 国文, 三文, 上文, 前文, 文学, 文月, 文中, 文部, 名文, 人文, 本文, 文身, 文人, 文名, 文物, 長文, 時文, 下文, 文学部, 国文学, 名文家, 日本文学, 人文学部, 天, 一天, 上天, 中天, 天下, 天国, 天子, 天女, 天上, 天生, 天日, 天分, 天文, 半天, 天人, 後天, 天長, 天の, 天部, 本天, 天一, 天の下, 天下一, 天文家, 天文学, 三日天下, 一人天下, 天下国家, 天上天下, 天一天上, 体, 一体, 三体, 女体, 上体, 人体, 生体, 身体, 体中, 体長, 大体, 天体, 物体, 分体, 文体, 本体, 下体, 国体, 体文, 人体学, 身体中, 中間体, 天体学, 生体学, 半数体, 本体部, 生物体, 気, 一気, 気学, 気前, 気体, 気長, 気分, 上気, 人気, 大気, 中気, 天気, 本気, 夜気, 生気, 女気, 山気, 御天気, 一本気, 上天気, 物の気, 大人気, 山の気, 方, 一方, 下方, 何方, 後方, 前方, 大方, 身方, 御方, 三方, 女方, 上方, 方々, 方方, 子方, 後の方, 長方体, 直方体, 御前方, 天文方, 手前の方, 地, 下地, 山地, 生地, 代地, 大地, 地下, 地上, 地代, 地方, 地名, 分地, 天地, 地文, 地学, 地中, 地物, 地気, 本地, 地子, 人地名, 地方時, 天地人, 地の文, 小天地, 地文学, 本地身, 地方名, 半地下, 中国地方, 中部地方, 心, 一心, 下心, 気心, 手心, 小心, 心気, 心身, 身心, 心地, 心中, 中心, 天心, 物心, 本心, 人心, 心天, 女心, 地心, 心学, 御心, 人心地, 中心地, 心の中, 中心部, 中心体, 中心人物, 一家心中, 心身一体, 中心小体, 目, 一目, 下目, 上目, 名目, 目下, 目上, 目前, 目方, 人目, 長目, 文目, 夜目, 後目, 地目, 大目, 目地, 小目, 年目, 本目, 御目, 天目, 何代目, 日の目, 目の前, 天目山, 御目目, 御目々, 名目上, 時間目, 夜の目, 二, 二子, 二月, 二三, 二手, 二足, 二直, 二日, 二部, 二分, 二方, 二目, 二人, 二心, 一二, 中二, 二女, 二本, 二間, 二時, 二の足, 二国間, 二人分, 二人目, 二人前, 二年生, 二日間, 二足三文, 二分の一, 一日二日, 十, 十一, 十月, 十三, 十手, 十数, 十二, 十日, 十分, 十本, 十目, 二十, 十代, 何十, 数十, 三十, 十年, 十地, 十方, 十夜, 三十日, 十一月, 十三夜, 十二月, 十二時, 十二分, 二十代, 二十日, 十二直, 二十年, 数十年, 十日夜, 十年一日, 十分の一, 十月十日, 色, 気色, 月色, 三色, 色気, 色女, 色目, 天色, 二色, 物色, 夜色, 一色, 色々, 色色, 地色, 女色, 間色, 目色, 色文, 色物, 本色, 生色, 体色, 色身, 色数, 色子, 地方色, 中間色, 目の色, 時代色, 十人十色, 道, 一道, 下道, 気道, 国道, 山道, 小道, 人道, 地道, 中道, 二道, 半道, 本道, 夜道, 天道, 間道, 道中, 道心, 道学, 道家, 道道, 道々, 大道, 色道, 道長, 一本道, 地下道, 何方道, 何の道, 人間道, 上気道, 中山道, 水, 一水, 下水, 山水, 小水, 上水, 水気, 水子, 水上, 水色, 水生, 水中, 水道, 水手, 水分, 大水, 天水, 生水, 手水, 水心, 水物, 水部, 水目, 三水, 二水, 水文, 名水, 下水道, 上水道, 中水道, 地下水, 水道水, 水文学, 水上下, 水の道, 上下水道, 水生生物, 水道の水, 神, 女神, 神身, 身神, 神学, 神代, 神道, 半神, 天神, 神々, 神神, 神子, 神月, 水神, 神人, 神気, 神色, 神体, 神国, 神前, 心神, 色神, 大神, 月神, 神名, 中神, 年神, 御神体, 大御神, 直日神, 天一神, 女神子, 大年神, 神の子, 山の神, 国家神道, 主, 家主, 主家, 主上, 主色, 主体, 主長, 主日, 主部, 主物, 主文, 神主, 水主, 地主, 天主, 道主, 主人, 主神, 国主, 名主, 女主, 御主, 御主人, 主の日, 女主人, 大地主, 女地主, 一家の主, 主の御名, 大国主神, 面, 一面, 月面, 三面, 小面, 上面, 人面, 水面, 前面, 体面, 地面, 直面, 半面, 部面, 文面, 方面, 面子, 面前, 面目, 面々, 面面, 面色, 面体, 面長, 面部, 生面, 天面, 下面, 水面下, 一生面, 水の面, 正, 正月, 正子, 正色, 正数, 正体, 正大, 正中, 正直, 正物, 正文, 正方, 正本, 正面, 正目, 大正, 中正, 正気, 正道, 正々, 正正, 方正, 正長, 文正, 天正, 正身, 小正月, 正の数, 中正面, 大正時代, 大正の代, 目の正月, 二十日正月, 字, 一字, 国字, 字体, 十字, 数字, 正字, 大字, 二字, 文字, 本字, 名字, 字面, 字数, 小字, 字間, 一文字, 十文字, 小文字, 大文字, 御の字, 人文字, 女文字, 大の字, 二文字, 文字間, 神代文字, 一字一字, 御目文字, 中間文字, 名前文字, 小文字名前文字, 大文字名前文字, 金, 御金, 下金, 金物, 金目, 後金, 小金, 正金, 代金, 大金, 天金, 年金, 半金, 金色, 前金, 金子, 金気, 地金, 金山, 金字, 金主, 手金, 月金, 金文, 金神, 水金, 一時金, 月水金, 身代金, 一分金, 金文字, 人の金, 身の代金, 金目の物, 和, 中和, 日和, 和人, 和金, 和上, 和文, 和本, 大和, 和名, 和字, 和気, 和物, 長和, 正和, 文和, 天和, 水和, 和主, 直和, 和国, 和方, 和子, 大和心, 水和物, 大和文, 和文体, 大和時代, 大和の国, 一水和物, 大和国家, 元, 一元, 家元, 元気, 元三, 元手, 元日, 元年, 元方, 元本, 手元, 身元, 地元, 中元, 元金, 足元, 元々, 元元, 国元, 山元, 道元, 目元, 本元, 二元, 天元, 長元, 正元, 元中, 元和, 元文, 元正, 御中元, 三元色, 御手元, 本家本元.

In June I said this on Twitter:

@luqui The board is a graph. A node for each empty point, a node for each group. Legality of a move depends only its radius 2 neighborhood.

@luqui The distance between two points may shrink by at most 2 when a move is played (because groups can be joined). Speed of light is 2.

@luqui Let R be a region of the board. The set of possible states of R after T moves is not affected by anything farther than cT = 2T.

@luqui Note: 2 points may move away from each other FTL (if a group dies), but not towards each other. Moving away is not communicating.

@luqui Information about legal possibilities can’t go FTL, but info about good moves can; strategy now depends on far future possibilities.

I’ll explain this again in a different way. Minimax search is an algorithm for perfect play in any combinatorial game. To solve Go by minimax search would, however, take a very long time, and so it is not a practical method by itself.

One technique that has been useful for Chess is to apply minimax search to a similar game with a new rule. The new rule is this: after n moves, for some particular n, the game will end and the final score will be determined using a board evaluation function. The optimal move in this modified game may then be assumed to be a decent move in the original chess position.

Since Go has a large number of moves available from most game positions, the values of n for which such calculations are practical are quite small. If we could throw out most possible moves (that is, if we could know that they are suboptimal without search), then we could search more deeply.

Enter locality – the fact that it takes a long time for effects on a go board to propagate over a long distance.

(The shading in this diagram shows the distance to the highlighted region, as defined by the metric discussed in the quoted material).

Suppose that our board evaluation function only cares about a small region R of the board, such as the highlighted region shown above. This means we’re now dealing with a local goal instead of the overall goal of winning the game. Let’s just press on, and at a later date we can figure out how local goals relate to winning the game.

If n=1, then the value within a region depends on the set of states that R can be in after one move. To determine which states are possible, we would need the following information:

• If a chain has only one liberty within R, we wish to know if it has an external liberty. This requires looking at points at distance 1 from R.
• If a chain has no liberties within R, then it must have an external liberty; but whether it can be captured depends on if it has two external liberties. This again requires looking at points at distance 1.
• If an empty point in R is bordered only by (WLOG) white stones, then the legality of a black play there may depend on whether it captures a white chain that is itself at distance 1 from R. To answer this question involves looking at points at distance 2 from R.

This is the extent of the information we may need about the rest of the board. So the set of reachable states in R depends only on a radius-2 neighborhood of R.

Now we can proceed by induction. Suppose that the depth-(n-1) value of R depends only on a neighborhood of radius 2(n-1). Then to get the depth n value, we would simply look at all the possible states that the radius 2(n-1) neighborhood can be placed into by one move, and take the max (or min) of their depth-(n-1) values. The set of possible states depends only on a radius 2 neighborhood of the radius 2(n-1) neighborhood – that is, it depends only on a radius 2n neighborhood of R. Thus the depth n value depends only on the depth 2n neighborhood.

Of course, this bound is not very tight; it would be possible to achieve much tighter bounds.

I’m compiling some references to Go research. This is just a start:

The Game of go as a complex network.
A Dynamical Systems Approach to Static Evaluation in Go.
Time symmetric Go.
A Note On Go Endgame And Nonstandard Analysis.
Optimizing GoTools’ Search Heuristics Using Genetic Algorithms.
Computer Go: Knowledge, Search, and Move Decision.
Computer Go as a Sum of Local Games: An Application of Combinatorial Game Theory
When One Eye is Sufficient: A Static Classification

It’s been nearly a year since my last post here. I’d like to get back into blogging, so I’ll start by listing various things I might blog. Here’s your chance to affect what I write about.

The list:

1. My new organization, It Builds Itself.
2. Books, articles, and papers I’m reading.
3. Programs, programming, and programming languages.
4. Go, programs that play Go, math about Go, and statistics about Go.
5. Details, possibly excessive, about my personal life.
6. The singularity and the future of humanity and of the universe (topics about which I know very little).
7. Mathematics that is already widely understood, but which may be new to some folks.
8. Imaginary places, people, and things.

Since this ended up being a pretty short list, I’ll be accepting further suggestions as well.

I haven’t been posting on this blog much lately, but I have been tweeting. If you want to read more of my stuff, follow @spaceandgames.

I’m writing a book about Go strategy. I’ll be comparing moves by professionals to moves by amateurs in the 1-3k range. My hope is that amateur players may improve by trying to imitate the professionals.

Two-Stone Corner Patterns
Three-Stone Corner Patterns
Four-Stone Corner Patterns

Challenge: Design an algorithm that:

• takes a discrete probability distribution and a source of random bits, and returns a sample from the probability distribution.
• if running the algorithm on distribution P₁ with random bits S yields X₁, and running it on (P₂, S) yields X₂, and X₂ ≠ X₁, then P₂(X₂) / P₂(X₁) > P₁(X₂) / P₁(X₁)

I ran into this problem in the context of a computer game I’m developing. Rather than storing every detail of the game world in the map file, I store a random seed that is used to generate most map features. I found that every time I tweaked certain parameters in my code, old map files became unrecognizable.

Thus, we would like a random sampling algorithm that is unlikely to change its output when we make a small change to the underlying probability distribution (assuming we keep our original random seed). In particular, if we increase the probability of one outcome and renormalize the others, then the only way the outcome should change is if it changes to the outcome whose probability we increased.

If you want to solve the problem yourself, this would be a good time to stop reading.

I shared this problem with Michael Dobbins and he solved it for me.

Mike’s method is to associate each face of a simplex with one of the outcomes. We pick a random point inside the simplex, and measure the distance from that point to each of the faces, then divide that distance by the probability of the associated outcome. The lowest number wins.