第1次熱潮的內容與預言

011960〜1966 · 日本

每次分辨1個音

機器從哪裡分辨日語「a」和「i」的差別？

1960年，京都大學的坂井利之等人正在研究，用來辨識人的聲音並轉成文字。根據當時的報導，目標是能辨識日語100個單音節（一次1個音）的裝置。母音靠聲音中2個強烈共振的頻率峰（第1、第2共振峰）的位置來辨識，子音則結合波形穿過0的次數等資訊來辨識。

右邊的圖是以2個峰的頻率為座標軸的平面。「a、i、u、e、o」分別聚集在各自的小島上。移動一個點，離它最近的小島所代表的母音就是答案。增加雜訊，就會開始在島與島之間判斷錯誤。

答案＝使 √((F1−F1ₖ)² ＋ (F2−F2ₖ)²)最小的母音k

F1, F2: 聲音的第1、第2個峰的高度（頻率）
F1ₖ, F2ₖ: 母音k所在小島的中心（本站設定的大致數值）

日語中相當於的詞，在論文中從1962年起就能找到。1966年東北大學的研討會，主題直接使用英語，京都大學讀取文字的「辨識機器」等演講吸引了超過200人參加。

聲音的波形，以及穿過0的次數

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_vowel_formant.py

# u04 声の 2 つの周波数の山で母音を聞き分ける（音声タイプライターの考え方）
#
# どの出来事か：1960 年、京都大学の坂井利之たちの「音声タイプライター」（記録 kyoto_phonetic_typewriter_1960）。
#   当時の記事によると、母音は声の響きの山（第 1・第 2 ホルマント）の位置で、
#   子音は波が 0 を横切る回数などを組み合わせて識別しようとしていた。
# 仕組み：
#   ① 2 つの高さの波を足して「母音らしい音」を作る（山の高さは、このサイトが決めたおおよその数）。
#   ② 音の中にどの高さの波がどれだけ入っているかを、1 つずつ掛け算して足して調べる（離散フーリエ変換）。
#   ③ 大きい山 2 つの周波数（F1, F2）を取り出し、いちばん近い母音の島を答えにする。
#   ④ 子音のような雑音は、0 を横切る回数が母音よりずっと多い。
# 試してみよう：
#   - NOISE を 0.5 → 1.5 → 3.0 と上げると、どこから母音を間違え始めるか
#   - ISLANDS の数値を動かして、島どうしを近づけるとどうなるか

import math
import random

random.seed(1960)
RATE = 8000          # 1 秒に何回、音を記録するか
N = 400              # 1 つの音で使う記録の数（0.05 秒）
NOISE = 0.8          # 足す雑音の強さ
# 母音の島の中心（F1, F2。単位はヘルツ）。仕組みを示すための、このサイトのおおよその数
ISLANDS = {"あ": (800, 1250), "い": (300, 2300), "う": (330, 1350), "え": (500, 1900), "お": (500, 850)}

def make_sound(f1, f2, noise):
    """2 つの周波数の波を足した音。雑音も少し足す。"""
    return [math.sin(2 * math.pi * f1 * t / RATE) + 0.7 * math.sin(2 * math.pi * f2 * t / RATE)
            + noise * random.gauss(0, 1) for t in range(N)]

def spectrum(x, lo=200, hi=3000, step=50):
    """周波数 f の成分の大きさ（振幅）を、f を 50 ヘルツずつ変えて調べる。"""
    out = []
    for f in range(lo, hi + 1, step):
        re = sum(v * math.cos(2 * math.pi * f * t / RATE) for t, v in enumerate(x))
        im = sum(v * math.sin(2 * math.pi * f * t / RATE) for t, v in enumerate(x))
        out.append((f, math.hypot(re, im)))
    return out

def two_peaks(spec):
    """いちばん大きい山と、そこから 300 ヘルツ以上離れた 2 番目の山。低い方を F1 とする。"""
    s = sorted(spec, key=lambda p: -p[1])
    a = s[0][0]
    b = next(f for f, _ in s if abs(f - a) >= 300)
    return min(a, b), max(a, b)

def nearest(f1, f2):
    return min(ISLANDS, key=lambda k: math.hypot(f1 - ISLANDS[k][0], f2 - ISLANDS[k][1]))

def zero_cross(x):
    return sum(1 for a, b in zip(x, x[1:]) if (a < 0) != (b < 0))

print("母音を 1 つずつ識別する（雑音の強さ", NOISE, "）")
print("  正解  見つけた F1   F2    判定")
ok = 0
for i in range(10):
    v = random.choice(list(ISLANDS))
    c1, c2 = ISLANDS[v]
    f1, f2 = c1 + random.gauss(0, 40), c2 + random.gauss(0, 80)   # 人による声の違い
    p1, p2 = two_peaks(spectrum(make_sound(f1, f2, NOISE)))
    ans = nearest(p1, p2)
    ok += ans == v
    print(f"  {v}     {p1:5d} {p2:5d}    {ans} {'○' if ans == v else '×'}")
print(f"  正しく聞き分けた：{ok} / 10")

print("\n雑音を強くすると？（各 30 回）")
for noise in (0.5, 1.5, 3.0, 5.0):
    ok = 0
    for _ in range(30):
        v = random.choice(list(ISLANDS))
        p1, p2 = two_peaks(spectrum(make_sound(*ISLANDS[v], noise)))
        ok += nearest(p1, p2) == v
    print(f"  雑音 {noise:3.1f}：{'■' * ok}{'□' * (30 - ok)} {ok}/30")

print("\n0 を横切る回数（0.05 秒の間）")
vowel = make_sound(*ISLANDS["あ"], 0.05)
hiss = [random.gauss(0, 1) for _ in range(N)]   # 「すー」のような雑音の音
print(f"  母音「あ」：{zero_cross(vowel):4d} 回")
print(f"  雑音の音  ：{zero_cross(hiss):4d} 回  ← ずっと多い。母音か、雑音のような子音かの手がかりになる")

021961〜1969 · 機器人

記住動作並反覆執行的手臂

最早在工廠工作的機器人，的是什麼？

1961年獲准的Devol專利，構想用能記住動作步驟（程式），並能更換步驟的手臂，取代凸輪（利用旋轉板的形狀，只能產生固定動作的零件），並稱它為。同一年，Unimation公司的機器人進入通用汽車的工廠，取出模具裡的高溫零件並堆疊起來。

在右邊的圖裡換一換步驟吧。手臂只是依序經過教給它的各個點，並不知道這些動作的目的。1969年，川崎重工業完成日本第一台國產工業機器人「川崎Unimate 2000型」，在日本以引起了很大的迴響。

x＝L₁cos θ₁ ＋L₂cos(θ₁＋θ₂)

x: 手臂末端的水平位置（垂直位置y的形式相同，只要把cos換成sin）
θ₁, θ₂: 2個關節的角度（作為步驟記住的數值）
L₁, L₂: 手臂的長度

1963年1月1日，電視動畫開播，有心靈的機器人少年每週出現在電視上。工廠的機器人則是反覆執行記住的動作的手臂。

以為知道的事常見說法：是日本第一部電視動畫
原始資料中：放送圖書館和製作公司的說法是。在它之前，也有過短篇的日本國產電視動畫。

031962〜2007 · 遊戲

西洋跳棋真的了嗎

「解決」一個遊戲，是什麼意思？

1962年，IBM的Samuel所寫的西洋跳棋程式（在8×8棋盤上跳過棋子來吃子的遊戲），贏了盲人棋手Nealey 1局，西洋跳棋便被報導為。1965年，貝爾曼寫道：（譯）。

解決一個遊戲，是指在任何局面下，雙方都走出最佳的一步時，能確定結果是勝、負還是和棋。可靠的方法是從終局往回推（逆向分析）。在右邊的取石子遊戲裡，按「往回推1步」吧。輪到自己時，石子有0個的人就輸了。只要有一步能把會輸的局面交給對手，自己就能贏。

西洋跳棋的局面約有5×10²⁰ 種。2007年，亞伯達大學的團隊透過從1989年開始的計算，證明雙方都走得完美時，結果會是和棋。

局面的值＝勝（至少有1步能走到負的局面）／負（每一步都走到勝的局面）

局面: 某個時刻的棋盤狀態
一步: 走向下一個局面的一步棋

以為知道的事常見說法：1962年Samuel的程式戰勝了西洋跳棋大師，所以西洋跳棋已解決
原始資料中：贏的只有1局，對手的等級比大師低一級。隔年再交手，對手一局也沒輸就贏了，1965年程式又對世界錦標賽的2名選手8戰全敗。真正解決是在2007年。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_retrograde_stones.py

# u04 ゲームを「解く」：終わりの局面から逆にたどる（後ろ向きの解析）
#
# どの出来事か：1962 年、サミュエルのチェッカーのプログラムの 1 勝（記録 samuel_nealey_game_1962）、
#   1965 年のベルマンの見通し「10 年以内に…完全に決着のつくゲームになる」（記録 bellman_checkers_prediction_1965）、
#   2007 年にチェッカーが解かれたこと（記録 checkers_solved_2007）。
#   2007 年の論文は、終わりの局面から逆にたどる方法（retrograde analysis）で、
#   駒が 10 個以下の局面を全部調べた、と書いている。
# 仕組み：石取りゲーム（石が n 個。自分の手番で 1〜K 個取る。最後の石を取ると勝ち）を、
#   石 0 個（手番の人の負け）から逆にたどって、全部の局面に「勝ち・負け」の印をつける。
#   ・負けの局面へ行ける手が 1 つでもあれば、その局面は「勝ち」
#   ・どの手も勝ちの局面へ進むなら、その局面は「負け」
# 試してみよう：
#   - K（1 回に取れる数）を 2・4・5 に変えて、負けの局面の並び方を見る
#   - 2 つの山のゲーム（ニム）の表で、負けの局面がどこに並ぶか見る

K = 3
N = 30

# ---- 1 つの山 ----
value = {0: "負け"}                     # 石 0 個で手番になった人は、もう取れないので負け
for n in range(1, N + 1):
    value[n] = "勝ち" if any(value[n - k] == "負け" for k in range(1, min(K, n) + 1)) else "負け"
print(f"石取りゲーム（1 回に 1〜{K} 個）を、石 0 個から逆にたどった結果：")
for n in range(0, N + 1):
    print(f"  石 {n:2d} 個：{'●' if value[n] == '勝ち' else '○'} {value[n]}（手番の人から見て）")
lose = [n for n in range(N + 1) if value[n] == "負け"]
print("  負けの局面：", lose, f"→ {K + 1} の倍数のみ")
print("  勝ちの局面では、相手に『負け』の局面を渡す手を打てばよい。これが『解けた』ということ。\n")

# ---- 2 つの山（ニム：どちらかの山から 1 個以上いくつでも取る）----
M = 7
val2 = {}
for total in range(0, 2 * M + 1):          # 石の合計が少ない局面から順に（逆にたどる）
    for a in range(0, M + 1):
        b = total - a
        if not 0 <= b <= M:
            continue
        nxt = [(a - k, b) for k in range(1, a + 1)] + [(a, b - k) for k in range(1, b + 1)]
        val2[(a, b)] = any(val2[p] is False for p in nxt)   # True=勝ち False=負け
print("2 つの山のゲーム（ニム）の表：横＝山 A の数、縦＝山 B の数（○＝手番の人の負け）")
print("      " + " ".join(str(a) for a in range(M + 1)))
for b in range(M + 1):
    print(f"  B={b} " + " ".join("●" if val2[(a, b)] else "○" for a in range(M + 1)))
print(f"  局面の数：{(M + 1) ** 2}。負けの局面は、2 つの山が同じ数の時だけ。\n")

# ---- チェッカーの局面数（2007 年の論文の数）----
checkers_all = 500_995_484_682_338_672_639      # 駒 1〜24 個の局面の合計（2007 年の論文の表 1）
checkers_db = 3.9e13                             # 終わりから逆にたどって調べた、駒 10 個以下の局面
speed = 1_000_000                                # 仮に 1 秒に 100 万局面調べるとすると
for name, n in (("この石取りゲーム", N + 1), ("2 つの山のゲーム", (M + 1) ** 2),
                ("チェッカーの駒 10 個以下", checkers_db), ("チェッカー全局面", checkers_all)):
    sec = n / speed
    t = f"{sec:.6f} 秒" if sec < 60 else (f"{sec / 86400:,.0f} 日" if sec < 3.15e7 else f"{sec / 3.15e7:,.1f} 年")
    print(f"  {name:<16} 局面 {n:>12.3g}　1 秒に 100 万ずつなら {t}")
print("  チェッカーは、全部の局面を調べずに、関係のある局面だけをたどる工夫を重ねて、2007 年に解かれた。")

041964 · 應用題

把應用題改寫成式子來解

機器怎麼把「比……便宜15%」改寫成式子？

1964年，MIT的研究生Bobrow在博士論文中，製作了能讀取英語代數應用題並求解的程式STUDENT。他把高中1年級課本中的一部分應用題，改寫成STUDENT能讀取的英語形式來測試。

STUDENT並不思考句子的意思。它把英語的is當成等號，percent less than當成乘法，也就是把固定的說法換成式子的組成部分。在右邊的圖裡按「前進1步」吧。式子不夠時，它會補上這類已知的關係，並把所做的假設告訴使用者。規則裡沒有的說法，就算意思相同，也無法改寫成式子。

69.70＝（1 − 15/100）× 標價

is: 改成等號
percent less than: 改成 ×（1 − p/100）
sum of: 改成加法

Bobrow把這種說法，定義為，並依照這個定義使用。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_student_equations.py

# u04 STUDENT のまね：決まった言い回しを式の部品に置き換えて、文章題を解く
#
# どの出来事か：1964 年、MIT のボブローの博士論文のプログラム STUDENT（記録 bobrow_student_1964）。
#   STUDENT は、制限つきの英語の代数の文章題を読み、「is」を等号にするなど、決まった言い回しを式に直して解いた。
#   式が足りない時は「距離＝速さ×時間」のような知っている関係を補い、置いた仮定を利用者に伝えた。
# このサンプルの問題文は、論文の図 1 の問題をもとに、このサイトが「区切った日本語」で作った例（論文の文の訳ではない）。
# 仕組み：
#   ① 決まった言い回しの置き換え（例：「2 つ の 数」→「一方 の 数 と もう一方 の 数」）
#   ② 文ごとに、決まりの形（は・より〜パーセント 安い・の〜倍・の 和 は・次 の 数）に当てはめて式にする
#   ③ 式を連立方程式として解く。式が足りなければ、知っている関係を補ってもう一度解く
#   文の意味は考えていない。形が決まりに合わなければ、誤った式ができるか、解けなくなる。
# 試してみよう：
#   - PROBLEMS の数を変えて解き直す
#   - 最後の「決まりに無い言い方」の問題を、決まりに合う形に書き直して解かせる

import re
from fractions import Fraction as F

PROBLEMS = [
    "ラジオ の 値段 は 69.70 ドル 。 この 値段 は 表示 の 値段 より 15 パーセント 安い 。 表示 の 値段 を 求めよ 。",
    "2 つ の 数 の 和 は 111 。 一方 の 数 は もう一方 の 数 の 次 の 数 。 2 つ の 数 を 求めよ 。",
    "ニューヨーク から ロサンゼルス まで の 距離 は 3000 マイル 。 ジェット機 の 速さ は 時速 600 マイル 。 "
    "ジェット機 で ニューヨーク から ロサンゼルス まで かかる 時間 を 求めよ 。",
    "ビル の 父 の おじ の 年齢 は ビル の 父 の 年齢 の 2 倍 。 2 年後 ビル の 父 の 年齢 は ビル の 年齢 の 3 倍 。 "
    "ビル の 父 の おじ の 年齢 と ビル の 父 の 年齢 と ビル の 年齢 の 和 は 92 。 ビル の 年齢 を 求めよ 。",
    "ラジオ は 表示 の 値段 から 15 パーセント 値引き されて 69.70 ドル 。 表示 の 値段 を 求めよ 。",   # 決まりに無い言い方
]
IDIOMS = [("2 つ の 数 の 和", "一方 の 数 と もう一方 の 数 の 和"), ("2 つ の 数 を 求めよ", "一方 の 数 と もう一方 の 数 を 求めよ")]
KNOWN = [("距離", "速さ", "時間")]     # 知っている関係：距離 ＝ 速さ × 時間
NUM = r"(\d+(?:\.\d+)?)"

def name(s):
    return s.replace(" ", "")

def lin(var=None, k=1, c=0):
    """1 次式：{変数: 係数, None: 定数項}"""
    e = {None: F(c)}
    if var:
        e[var] = e.get(var, 0) + F(k)
    return e

def add(*es):
    out = {}
    for e in es:
        for v, k in e.items():
            out[v] = out.get(v, 0) + k
    return out

def scale(e, k):
    return {v: c * F(k) for v, c in e.items()}

def to_eq(sentence, last):
    """1 文を式（左辺−右辺＝0）に変換する。どの決まりを使ったかも返す。"""
    s = sentence
    m = re.fullmatch(r"(.+?) は (.+?) より " + NUM + r" パーセント 安い", s)
    if m:
        x, y, p = resolve(m.group(1), last), name(m.group(2)), F(m.group(3))
        return add(lin(x), scale(lin(y), -(1 - p / 100))), f"「より〜パーセント 安い」→ {x} ＝ (1 − {p}/100) × {y}"
    m = re.fullmatch(r"(.+?) は (.+) の 次 の 数", s)
    if m:
        x, y = name(m.group(1)), name(m.group(2))
        return add(lin(x), scale(lin(y), -1), lin(c=-1)), f"「次 の 数」→ {x} ＝ {y} ＋ 1"
    m = re.fullmatch(NUM + r" 年後 (.+?) は (.+) の " + NUM + r" 倍", s)
    if m:
        n, x, y, k = F(m.group(1)), name(m.group(2)), name(m.group(3)), F(m.group(4))
        return add(lin(x, c=n), scale(lin(y, c=n), -k)), f"「〜年後 … の〜倍」→ {x} ＋ {n} ＝ {k} × ({y} ＋ {n})"
    m = re.fullmatch(r"(.+?) は (.+) の " + NUM + r" 倍", s)
    if m:
        x, y, k = name(m.group(1)), name(m.group(2)), F(m.group(3))
        return add(lin(x), scale(lin(y), -k)), f"「の〜倍」→ {x} ＝ {k} × {y}"
    m = re.fullmatch(r"(.+) の 和 は " + NUM, s)
    if m:
        parts = [name(p) for p in m.group(1).split(" と ")]
        return add(*[lin(p) for p in parts], lin(c=-F(m.group(2)))), f"「の 和 は」→ {' ＋ '.join(parts)} ＝ {m.group(2)}"
    m = re.fullmatch(r"(.+?) は (?:時速 )?" + NUM + r"(?: \S+)?", s)
    if m:
        x = name(m.group(1))
        return add(lin(x), lin(c=-F(m.group(2)))), f"「は」→ {x} ＝ {m.group(2)}"
    m = re.fullmatch(r"(.+?) は (.+)", s)
    if m:
        x, y = name(m.group(1)), name(m.group(2))
        return add(lin(x), scale(lin(y), -1)), f"「は」→ {x} ＝ {y}　（意味は考えずに、そのまま等号にした）"
    return None, "決まりに合う形がない"

def resolve(phrase, last):
    """「この 値段」→ 直前に現れた「値段」を含む語（前の文の主語）"""
    m = re.fullmatch(r"この (\S+)", phrase)
    if m:
        for v in reversed(last):
            if m.group(1) in v:
                return v
    return name(phrase)

def solve(eqs):
    """連立 1 次方程式を掃き出し法で解き、求まった変数の値を返す。"""
    vars_ = sorted({v for e in eqs for v in e if v is not None})
    rows = [[e.get(v, F(0)) for v in vars_] + [-e.get(None, F(0))] for e in eqs]
    known, r = {}, 0
    pivots = []
    for c in range(len(vars_)):
        p = next((i for i in range(r, len(rows)) if rows[i][c] != 0), None)
        if p is None:
            continue
        rows[r], rows[p] = rows[p], rows[r]
        rows[r] = [x / rows[r][c] for x in rows[r]]
        for i in range(len(rows)):
            if i != r and rows[i][c] != 0:
                rows[i] = [a - rows[i][c] * b for a, b in zip(rows[i], rows[r])]
        pivots.append((r, c))
        r += 1
    for rr, c in pivots:
        if all(rows[rr][j] == 0 for j in range(len(vars_)) if j != c):
            known[vars_[c]] = rows[rr][-1]
    return known

def show(v):
    return f"{float(v):g}"

for no, text in enumerate(PROBLEMS, 1):
    print(f"━━ 問題 {no}：{name(text)}")
    for a, b in IDIOMS:
        if a in text:
            text = text.replace(a, b)
            print(f"   言い回しを置き換え：「{name(a)}」→「{name(b)}」")
    sentences = [s.strip() for s in text.split("。") if s.strip()]
    goal, eqs, last = [], [], []
    for s in sentences:
        m = re.fullmatch(r"(.+) を 求めよ", s)
        if m:
            goal = [name(p) for p in m.group(1).split(" と ")]
            continue
        e, why = to_eq(s, last)
        print(f"   文「{name(s)}」 {why}")
        if e:
            eqs.append(e)
            last += [v for v in e if v]
    known = solve(eqs) if eqs else {}
    if not all(g in known for g in goal):
        for rel in KNOWN:
            slots = {}
            for w in rel:
                hit = [v for v in set(last) | set(goal) if w in v]
                if hit:
                    slots[w] = hit[0]
            if len(slots) == len(rel):
                print(f"   式が足りない → 知っている関係を使う：{rel[0]} ＝ {rel[1]} × {rel[2]}")
                for w, v in slots.items():
                    print(f"     仮定：{w} は「{v}」のこと")
                d, sp, t = (slots[w] for w in rel)
                vals = {**known}
                if d in vals and sp in vals:
                    known[t] = vals[d] / vals[sp]
                elif d in vals and t in vals:
                    known[sp] = vals[d] / vals[t]
                elif sp in vals and t in vals:
                    known[d] = vals[sp] * vals[t]
    for g in goal:
        print(f"   答え：{g} は {show(known[g])}" if g in known else f"   答え：{g} は求められなかった（式が足りず、知っている関係にも合わない）")
    print()

051966 · 對話

揭開ELIZA的運作方式

用文字和人對話的程式，究竟了什麼？

1966年1月，MIT的Weizenbaum發表了介紹ELIZA的論文。這個程式讓人能用文字和電腦對話。ELIZA會在輸入的句子裡尋找關鍵字，用該關鍵字的拆分規則把句子分成幾個部分，再用重組規則產生回覆。沒有關鍵字時，就回一句沒有實質內容的應答。

關鍵字有優先順序。論文的例子把everybody的優先順序設得比I高，這樣就能針對everybody回應，反問是指誰。在右邊的圖裡輸入一句話，就能看到找到的關鍵字和使用的規則。整套關鍵字和規則（腳本），是與程式分開的資料；換掉它，對話對象的角色就會改變。

(0 YOU 0 ME) → (WHAT MAKES YOU THINK I 3 YOU)

0: 可以放入任意數量詞語的部分
3: 把拆分出的第3個部分原樣放進去（論文的例子）

論文發表時，最大的腳本也只有約50個關鍵字。除了英語，也有威爾斯語和德語的腳本。

以為知道的事常見說法：ELIZA是為了製作能像人一樣對話的AI而開發的
原始資料中：論文開頭寫道：（譯），接著又寫：（譯）。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_eliza_ja.py

# u04 ELIZA の仕組み：キーワードを見つけて、決まり通りに組みかえて返す（種明かしつき）
#
# どの出来事か：1966 年 1 月、ワイゼンバウムの論文（記録 eliza_1966）。
#   ELIZA は、入力された文からキーワードを探す。
#   キーワードごとの「分け方の決まり」で文を分解し、「組みかえの決まり」で返事を作る。
#   キーワードがなければ、つなぎの返事を返す。
#   論文のねらいの 1 つは、すごそうに見えるプログラムの種明かしだった。
# このサンプルの決まり（SCRIPT）は、論文の仕組みにならって日本語で作った例（論文の台本の訳ではない）。
# 試してみよう：
#   - TALK に自分の文を足して、どの決まりが使われたかを見る
#   - SCRIPT に新しいキーワードを足す（順位 rank が大きいほど優先される）
#   - 「みんな」の順位を 1 にすると、最後の文への返事がどう変わるか（論文の everybody と I の例）
#   - 組みかえの「{2}」の前後のかぎかっこを消すと、返事の日本語が不自然になることがある。
#     ELIZA は言葉の意味も文法も知らず、切り取った文字列を当てはめているだけだから

import re

SCRIPT = [
    # (キーワード, 順位, 分け方（正規表現）, 組みかえの候補)
    ("みんな", 6, r"(.*)", ["だれか、特定の人のことを思いうかべていますか？"]),   # 論文の例：everybody を I より高い順位に
    ("いつも", 5, r"(.*)", ["たとえば、どんな時ですか？", "いつも、ですか。"]),
    ("母", 4, r"(.*)母(.*)", ["お母さんのことを、もう少し話してください。", "家族のことで、ほかに思い浮かぶことは？"]),
    ("私は", 3, r"(.*)私は(.*)です", ["あなたが「{2}」と感じるのは、なぜですか？", "「{2}」と感じるようになったのは、いつからですか？"]),
    ("私は", 3, r"(.*)私は(.*)", ["あなたは「{2}」のですね。"]),
    ("悲しい", 3, r"(.*)", ["悲しいと聞いて、残念です。", "何があったのか、話してくれますか？"]),
    ("あなた", 2, r"(.*)あなた(.*)", ["私のことより、あなたのことを話しましょう。"]),
]
NO_KEYWORD = ["続けてください。", "それで？", "もう少しくわしく話してください。"]

used = {}       # 同じ決まりの組みかえ候補を順番に使うための記録
fallback = [0]

def reply(sentence):
    hits = [(kw, rank, pat, outs) for kw, rank, pat, outs in SCRIPT if kw in sentence]
    for kw, rank, pat, outs in sorted(hits, key=lambda h: -h[1]):
        m = re.fullmatch(pat, sentence.rstrip("。！？"))
        if not m:
            continue   # 分け方の決まりに合わなければ、次の決まりへ
        n = used.get((kw, pat), 0)
        used[(kw, pat)] = n + 1
        template = outs[n % len(outs)]
        parts = {str(i): g for i, g in enumerate(m.groups(), 1)}
        text = template.format(*[""] + [parts.get(str(i), "") for i in range(1, 4)])
        return text, f"キーワード「{kw}」（順位 {rank}）・分け方 {pat}・組みかえ {n % len(outs) + 1} 番"
    text = NO_KEYWORD[fallback[0] % len(NO_KEYWORD)]
    fallback[0] += 1
    return text, "キーワードなし → つなぎの返事"

TALK = [
    "人はみんな同じです。",
    "いつも何かで私を困らせるんです。",
    "私は悲しいです。",
    "母が心配しています。",
    "あなたは機械ですね。",
    "私は本当は元気です。",
    "私はみんなに笑われている気がします。",
]
for line in TALK:
    answer, why = reply(line)
    print(f"人  ：{line}")
    print(f"ELIZA：{answer}")
    print(f"   （種明かし：{why}）")

061964年還是1966年 · 日本的教材

ELIZA是哪一年的成果

年表上的「1964年」，指的是哪件事的年份？

高中「資訊Ⅱ（日本高中資訊科目）」的教師教材（2020年），表中寫著。這張表從2016年日本政府的調查研究報告，轉載到總務省的白皮書，再轉載到教材中。

把原始資料放在一起看：Weizenbaum的論文在1965年9月被接受，刊登在1966年1月號。當時MIT的年報（1964年7月〜1965年7月的那份）寫道，讓人和電腦用自然語言對話的系統，是在這段期間開始開發的。找到的原始程式是1965年的版本。

按右邊的標籤，就會顯示那一年發生的是什麼事。1964年有可能是開始開發的時期，但不是完成或發表的年份。教材的表格和論文，寫的是不同的時間點。知道年份指的是哪件事，就能正確理解這兩個數字。

英語資料的年份也有差異。IEEE的電腦先驅介紹寫著，也把論文期刊的年份寫成1965年（實際刊登在1966年）。

071965 · 化學

列出所有候選，再用規則篩選

可能的答案有幾百萬種時，專家怎麼縮小範圍？

史丹佛大學的Lederberg製作了DENDRAL這套步驟（1964年），從化學式出發，以樹狀形式列出所有可能的分子結構。從1965年起，Feigenbaum等人把化學家的經驗知識寫成的規則，納入程式來篩選候選。這些知識用來解讀質譜分析（打碎分子，再測量碎片重量的方法）的資料。某種化合物的14,715,813種結構，經質譜分析篩成1,284,792種，再加上另一種測量（核磁共振），就縮小到只剩1種。

右邊的圖把這個想法縮小呈現。先列出只含碳的所有骨架，預測碎片的重量，再刪掉與實測重量不符的結構。

列出 → 預測 → 比較（只留下符合的）

碎片的重量: 含k個碳的碎片，以14k＋1計算（本站的簡化規則。真正的質譜分析更複雜）

1970年的論文寫道：（譯）。

以為知道的事常見說法：第一個專家系統是MYCIN（1972年）
原始資料中：日本的白皮書這樣寫，但把專家經驗知識寫成規則並納入程式的DENDRAL，從1965年就開始了，比它更早。開發者自己也在1993年的論文標題中，把DENDRAL稱為。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_dendral_isomers.py

# u04 DENDRAL の考え方：候補の構造を全部作り、測ったデータと合わないものを消す
#
# どの出来事か：1965 年からの DENDRAL（記録 dendral_1965）。レダーバーグの、分子の構造を木の形で全部数え上げる手順に、
#   化学者の経験の知識（質量分析のデータの読み方）を「もし〜なら」の規則で組み込み、候補を絞った。
#   Nilsson（2010）の例：14,715,813 の候補 → 質量分析で 1,284,792 → 別の測定（核磁気共鳴）も使うと 1 つ。
# このサンプルの仕組み（このサイトが小さくした例。実際の質量分析はもっと複雑）：
#   ① 作る：炭素 n 個の、枝分かれした骨組み（アルカン）の構造を全部作る（同じ構造は 1 つにまとめる）
#   ② 予想する：結合を 1 か所切ったときの、2 つのかけらの炭素の数（重さ 14k＋1 の山になる）
#   ③ 比べる：測った山の並びと予想が合わない構造を消す。まだ残れば、別の測定で絞る
#      （ここでは「CH₃・CH₂・CH・C の炭素がそれぞれ何個あるか」が分かる測定とした。本物の核磁気共鳴を単純にしたもの）
# 試してみよう：
#   - N を 6・8・9 に変える（候補の数は 5・18・35 と増える）
#   - TARGET を別の番号にして、どの構造なら 1 つに絞れるか調べる

N = 7          # 炭素の数
TARGET = 2     # 「正体の分からない分子」にする構造の番号（0から）

def canon(adj, root, parent=-1):
    """木の形を、根から見た文字列にする（形が同じなら同じ文字列になる）。"""
    return "(" + "".join(sorted(canon(adj, c, root) for c in adj[root] if c != parent)) + ")"

def centers(adj):
    n = len(adj)
    deg = [len(a) for a in adj]
    leaves = [i for i in range(n) if deg[i] <= 1]
    left = n
    while left > 2:
        left -= len(leaves)
        nxt = []
        for v in leaves:
            for u in adj[v]:
                deg[u] -= 1
                if deg[u] == 1:
                    nxt.append(u)
            deg[v] = 0
        leaves = nxt
    return leaves if leaves else [0]

def key(adj):
    return min(canon(adj, c) for c in centers(adj))

def grow(n):
    """炭素1個から始め、結合数が4未満の炭素に1個ずつ足していく。"""
    level = {key([[]]): [[]]}
    for _ in range(n - 1):
        nxt = {}
        for adj in level.values():
            for v in range(len(adj)):
                if len(adj[v]) < 4:
                    new = [list(a) for a in adj] + [[v]]
                    new[v].append(len(adj))
                    nxt.setdefault(key(new), new)
        level = nxt
    return list(level.values())

def pieces(adj):
    """結合を 1 か所切ったときの、かけらの炭素の数（小さい方, 大きい方）のリスト。"""
    n, out = len(adj), []
    for v in range(n):
        for u in adj[v]:
            if u > v:
                seen, stack = {v}, [v]
                while stack:
                    x = stack.pop()
                    for y in adj[x]:
                        if y not in seen and not (x == v and y == u):
                            seen.add(y)
                            stack.append(y)
                a = len(seen)
                out.append(tuple(sorted((a, n - a))))
    return sorted(out)

def kinds(adj):
    """CH₃（結合数1）・CH₂（2）・CH（3）・C（4）の炭素がそれぞれ何個あるか。"""
    return tuple(sum(1 for a in adj if len(a) == k) for k in (1, 2, 3, 4))

print("炭素の数と、考えられる骨組みの構造の数")
for n in range(1, 11):
    print(f"  炭素 {n:2d} 個：{len(grow(n)):3d} 通り")

cands = grow(N)
target = cands[TARGET]
spec = pieces(target)
print(f"\n正体の分からない分子（炭素 {N} 個）を測った山（かけらの炭素の数の組）：")
print("  ", " ".join(f"{a}+{b}" for a, b in spec), " → 重さの山：", sorted({14 * k + 1 for ab in spec for k in ab}))
print(f"\n① 作る：候補 {len(cands)} 通り")
left = [c for c in cands if pieces(c) == spec]
print(f"② かけらの予想が合うものだけ残す：{len(left)} 通り")
k = kinds(target)
left2 = [c for c in left if kinds(c) == k]
print(f"③ 別の測定（CH₃ {k[0]}・CH₂ {k[1]}・CH {k[2]}・C {k[3]} 個）も合うものだけ：{len(left2)} 通り")
print("   残った構造（炭素どうしの結合）：")
for c in left2:
    print("   ", [(v, u) for v in range(len(c)) for u in c[v] if u > v])

print("\nどの構造なら、かけらの山だけで 1 つに絞れるか：")
same = {}
for c in cands:
    same.setdefault(tuple(pieces(c)), []).append(c)
for i, c in enumerate(cands):
    k = len(same[tuple(pieces(c))])
    print(f"  構造 {i}：炭素の種類 {kinds(c)}　かけらの山が同じ構造 {k} 通り{'  ← 山だけで 1 つに絞れる' if k == 1 else ''}")

081965 · 集合

「高個子」從幾cm開始？

無法明確決定是否屬於某個集合，能用數字表示嗎？

1965年，加州大學柏克萊分校的Zadeh發表了論文。或，是否屬於其中的界線並不明確。不過，這樣的集合在人辨識形狀、互相傳達資訊時，扮演著重要的角色。因此，Zadeh用0到1之間的數（隸屬程度），表示某個對象在多大程度上屬於這個集合。

在右邊的圖裡調整身高吧。一般的集合，在某個身高會突然從0切換成1。模糊集合的隸屬程度則會平順地增加。論文把「或」定義為取較大的值，「且」取較小的值，「非」則是用1減去原值。

或＝Max[μ_A, μ_B]　且＝Min[μ_A, μ_B]　非＝1 − μ_A

μ_A: 屬於集合A的程度（0〜1）

隸屬程度的形狀（160 cm時是0、185 cm時是1），是本站設定的範例。由誰、怎麼決定，要依使用情境各自約定。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_fuzzy_tall.py

# u04 ファジィ集合：「背の高い人」の集まりを、0〜1 の度合いで表す
#
# どの出来事か：1965 年、ザデーの論文「ファジィ集合」（記録 zadeh_fuzzy_sets_1965）。
#   「背の高い男の人の集まり」のように、入るか入らないかの境目がはっきりしない集まりを、
#   要素がその集まりにどれくらい属しているか（所属の度合い、0〜1）で表した。
#   論文は、2 つのファジィ集合の「または」を大きい方（Max）、「かつ」を小さい方（Min）、
#   「〜でない」を 1 から引いた数、と決めている。
# 仕組み：度合いの形（下の tall・medium）は、このサイトが決めた例。誰がどう決めるかは、使う場面ごとの約束になる。
# 試してみよう：
#   - tall の 160・185 を変えると、どの身長の度合いが変わるか
#   - ふつうの集合（175 cm 以上なら 1）と比べて、174 cm と 176 cm の差を見る

def crisp_tall(h):
    return 1.0 if h >= 175 else 0.0          # ふつうの集合：175 cm で急に入る

def tall(h):                                  # ファジィ集合「背が高い」：160 cm で 0、185 cm で 1
    return min(1.0, max(0.0, (h - 160) / 25))

def medium(h):                                # ファジィ集合「ふつうの背」：170 cm で 1、158・182 cm で 0
    return max(0.0, 1 - abs(h - 170) / 12)

def bar(v, n=20):
    return "■" * round(v * n) + "□" * (n - round(v * n))

print("身長   ふつうの集合    ファジィ集合「背が高い」")
for h in range(150, 201, 5):
    print(f"{h} cm  {crisp_tall(h):.0f}  {bar(crisp_tall(h), 5)}   {tall(h):.2f} {bar(tall(h))}")

print("\n174 cm と 176 cm：")
for h in (174, 176):
    print(f"  {h} cm：ふつうの集合 {crisp_tall(h):.0f}　ファジィ {tall(h):.2f}")
print("  → ふつうの集合では 2 cm で 0 から 1 に跳ぶ。ファジィ集合では、ほとんど変わらない。")

print("\n2 つのファジィ集合を組み合わせる（論文の決め方）")
print("身長   高い  ふつう  高い または ふつう(Max)  高い かつ ふつう(Min)  高くない(1−高い)")
for h in range(155, 196, 5):
    a, b = tall(h), medium(h)
    print(f"{h} cm  {a:.2f}  {b:.2f}   {max(a, b):.2f} {bar(max(a, b), 10)}      {min(a, b):.2f} {bar(min(a, b), 10)}     {1 - a:.2f}")

091960〜1966 · 預言

機器會變得能做人類的任何工作嗎

「20年之內」的預言，是說人的工作會消失嗎？

1965年，賽門在書中寫道：（譯）。原本1960年的論文則展望（譯），緊接著又寫道：（譯）。

賽門使用的是經濟學中的概念。即使機器做所有工作都比人快，機器的時間仍然有限。各自負責相對擅長的事，整體就能產出更多。在右邊的圖裡，即使提高機器的速度，選「按專長分工」後，人的工作仍會保留。

人負責的工作＝（機器的速度 ÷ 人的速度）之比最小的工作

比較利益: 與其他對象相比，相對擅長的事（不是速度本身）

以為知道的事常見說法：賽門預言，20年內機器會搶走人的所有工作
原始資料中：原始論文把技術能力的展望，和如何使用技術分開討論。他認為長遠來看，想工作的人幾乎都能工作。1966年，他也反駁說，決定就業水準的是經濟運作機制，而不是技術。

101965 · 預言

每年增加為2倍，持續10年會怎樣

每年增加為2倍的東西，10年會變成幾倍？

1965年，快捷半導體公司的摩爾，在文章裡寫道，1個電路上的元件數量大約每年增加為2倍（指每1個元件的成本最低時的數量）。他認為這個成長比例會持續，並預測1975年將達到65,000個。

在右邊的圖表裡選「每格增加為2倍」，線就會變成一直線，表示每年都以相同的比例成長。改變增加為2倍所需的年數T，1975年的預測就會大幅改變。「詳細資訊：文章中的點、成本與出處」下方的圖表，顯示每1個元件成本最低時的元件數，隨年份往右移動的情形。

元件數＝64 × 2^{(年 − 1965) ÷ T}

T: 增加為2倍所需的年數（文章中約為1年）
64: 2⁶（1965年的點）

1975年，摩爾本人回顧說，此前幾乎每年都增加為2倍，並把展望修正為，今後可能大約是。這個名稱，是別人取的。

每1個元件的成本與元件數（該年成本最低的點）

111965〜1967 · 批評

縮小要推演的走法

下西洋棋的電腦，會推演所有能走的棋步嗎？

1965年，哲學家德雷福斯在RAND研究所的報告中指出，AI在最初的成功之後，碰上了比預期更大的障礙。他寫道，人思考時會用到視野邊緣的線索，以及判斷什麼重要的能力，但改寫成電腦的語言時，這些就遺漏了。

1967年，MIT的Greenblatt製作的西洋棋程式Mac Hack VI，在對局中戰勝德雷福斯。這個程式不會推演所有走法。它用約50種線索，為每個走法的合理程度評分，只推演分數高的走法。比賽時，它把推演的走法數縮小為：第1、2步各15種，第3、4步各9種，之後各7種。在右邊的圖裡，試著改變篩選方式和深度吧。

推演的局面數＝w₁ × w₂ × … × w_d（全部推演則是b^d）

w_k: 第k步推演的走法數
b: 能走的走法數（圖中是假設的數值）
d: 深度

以為知道的事常見說法：德雷福斯預言電腦下西洋棋連業餘棋手都贏不了，結果自己輸了
原始資料中：1965年的原文（譯），是在描述當時的情況。他本人回答說（譯）（根據Papert的備忘錄）。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_selective_search.py

# u04 読む手を絞る：全部読むか、もっともらしい手だけ読むか
#
# どの出来事か：1967年、MITのグリーンブラットのチェスプログラム（Mac Hack VI）がドレイファスとの対局に勝った
#   （記録 dreyfus_machack_game_1967、dreyfus_alchemy_1965）。1967年の論文によると、このプログラムは
#   約50の手がかりで手ごとにもっともらしさの点をつけ、点の高い手だけを読んだ。大会では、読む手の数を
#   1・2手目は 15、3・4手目は 9、その先は 7 にした。αβ法で計算量がおよそ 100 分の 1 になるとも見積もっている。
# 仕組み：
#   ① 読む局面の数を数える：全部読む（1手ごとに b 通り）と、絞って読む（15, 15, 9, 9, 7）
#   ② 作ったゲームの木で、絞って読んだ時に、全部読んだ時と同じ手を選べるかを調べる
#      （もっともらしさは、本当の値＋見積もりの誤差。木と数値は、このサイトが作った例）
# 試してみよう：
#   - B（1手ごとの手の数。仮の数値）を 20・40 に変える
#   - GUESS_NOISE（見積もりの誤差の大きさ）を 0 にすると、絞っても同じ手を選べるか

import random

B = 30                     # 1手ごとの手の数（仮の数値）
WIDTHS = [15, 15, 9, 9, 7]  # 論文の大会の時の、読む手の数

print("① 読む局面の数")
full, sel = 1, 1
for d, w in enumerate(WIDTHS, 1):
    full *= B
    sel *= w
    print(f"  {d} 手先まで：全部読む {full:>12,}　しぼって読む {sel:>9,}　（{full / sel:,.0f} 分の 1）")
print(f"  αβ 法でさらにおよそ 100 分の 1 なら、しぼって読む局面は約 {sel // 100:,}\n")

# ② 作ったゲームの木で比べる
random.seed(1967)
DEPTH, BR = 4, 8
GUESS_NOISE = 0.2

def make_tree(depth):
    if depth == 0:
        return random.gauss(0, 1)
    return [make_tree(depth - 1) for _ in range(BR)]

def minimax(node, me):
    if not isinstance(node, list):
        return node
    vals = [minimax(c, not me) for c in node]
    return max(vals) if me else min(vals)

def narrow(node, me, width, depth=0):
    """もっともらしさ（本当の値＋見積もりの誤差）の高い手を width 本だけ読む。"""
    if not isinstance(node, list):
        return node
    guess = [(minimax(c, not me) * (1 if me else -1) + random.gauss(0, GUESS_NOISE), i) for i, c in enumerate(node)]
    keep = [node[i] for _, i in sorted(guess, reverse=True)[:width]]
    vals = [narrow(c, not me, width, depth + 1) for c in keep]
    return max(vals) if me else min(vals)

def best_move(tree, width=None):
    if width is None:
        vals = [minimax(c, False) for c in tree]
    else:
        guess = sorted(((minimax(c, False) + random.gauss(0, GUESS_NOISE), i) for i, c in enumerate(tree)), reverse=True)[:width]
        vals = [-9e9] * len(tree)
        for _, i in guess:
            vals[i] = narrow(tree[i], False, width)
    return max(range(len(tree)), key=lambda i: vals[i])

trees = [make_tree(DEPTH) for _ in range(60)]
print(f"② 作ったゲームの木（1手ごとに {BR} 通り・{DEPTH} 手先まで）60本で、全部読んだ時と同じ手を選べた割合")
for width in (1, 2, 3, 5, 8):
    same = sum(best_move(t, width) == best_move(t) for t in trees)
    print(f"  読む手 {width} 本：{'■' * (same // 3)}{'□' * (20 - same // 3)} {same}/60（読む局面 {width ** DEPTH:,}）")
print("  → 絞るほど速いが、見積もりに誤差があると、最善手を読み落とすことがある。")

121966〜1972 · 機器人

撞到東西，就修改地圖重新搜尋

機器人撞到沒看見的東西，該怎麼辦？

1966年到1972年，史丹佛研究所（SRI）研究了一台用輪子移動的機器人。它裝有電視攝影機、測距儀和碰撞感測器；透過無線連接的大型電腦，根據看見的物體建立房間地圖，規劃路線並讓它移動。它突然停下時，車身會搖晃，因此被稱為Shakey（搖晃的東西）。

1970年報告中的作業範例裡，Shakey先規劃路線，再往前走。撞到沒看見的東西時，它就會停下來重新拍照，再次規劃。右邊的圖會自動前進。按「停止」讓它停下，再按「繼續前進」讓它重新前進吧。虛線表示的物體，還沒有出現在地圖上。搜尋方式可以切換：廣度優先從附近向外擴展；深度優先則走到不能再走的地方，才往回退。

廣度優先 ← 佇列　深度優先 ← 堆疊

佇列: 從最早發現的地方開始查（先進先出）
堆疊: 從最後發現的地方開始查（後進先出）

以為知道的事常見說法：Life雜誌把Shakey稱為『第一個電子人』
原始資料中：文章裡，這句話引用自帶記者參觀的年輕研究者。記者在同一篇報導中寫道，他看見的工作（譯）。SRI在1984年的總結，將Shakey描述為具有（譯）的機器人。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_shakey_replan.py

# u04 シェーキーのように：地図で道を探し、ぶつかったら地図を直して探し直す
#
# どの出来事か：1966〜1972 年、SRI のロボット「シェーキー」（記録 shakey_sri_robot_1966）。
#   1970 年の報告の作業例：目的地までの経路を計画し、見えなかった物にぶつかると止まって写真を撮り直し、計画し直す。
# 仕組み：
#   ・地図（ロボットが知っている壁）の上で経路を探す。探し方は 2 つ：
#       幅優先＝近い場所から順に広げる（先に見つけた場所から調べる。待ち行列）
#       深さ優先＝行ける所まで進んでから戻る（最後に見つけた場所から調べる。積み重ね）
#   ・実際の部屋には、地図にない物（?）がある。進む先にそれがあったら、地図に書き足して探し直す。
#   部屋と物の置き方は、このサイトが作った例（シェーキーの実際の部屋ではない）。
# 試してみよう：
#   - ROOM の ? を増やす・動かすと、探し直す回数はどうなるか
#   - 深さ優先の経路が、なぜ遠回りになるのかを、調べた順番から考える

from collections import deque

ROOM = [
    "S...?...#.........",
    "........#.........",
    "........#....?....",
    "........#.........",
    "....#.......###...",
    "....#.....?.......",
    "....#.........#...",
    "....#.........#..G",
]
H, W = len(ROOM), len(ROOM[0])
START = next((r, c) for r in range(H) for c in range(W) if ROOM[r][c] == "S")
GOAL = next((r, c) for r in range(H) for c in range(W) if ROOM[r][c] == "G")

def search(known, start, how):
    """known＝地図上の壁。how＝'幅優先' か '深さ優先'。経路と、調べたマス目の数を返す。"""
    todo = deque([start])
    came = {start: None}
    looked = 0
    while todo:
        p = todo.popleft() if how == "幅優先" else todo.pop()
        looked += 1
        if p == GOAL:
            break
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            q = (p[0] + dr, p[1] + dc)
            if 0 <= q[0] < H and 0 <= q[1] < W and q not in known and q not in came:
                came[q] = p
                todo.append(q)
    if GOAL not in came:
        return None, looked
    path, p = [], GOAL
    while p:
        path.append(p)
        p = came[p]
    return path[::-1], looked

def run(how):
    known = {(r, c) for r in range(H) for c in range(W) if ROOM[r][c] == "#"}   # 初めの地図（? は知らない）
    pos, walked, plans, looked_all = START, [START], 0, 0
    while pos != GOAL:
        path, looked = search(known, pos, how)
        plans += 1
        looked_all += looked
        if path is None:
            print("  経路が見つからない")
            return
        for q in path[1:]:
            if ROOM[q[0]][q[1]] == "?":          # ぶつかった。地図に書き足して、ここから探し直す
                known.add(q)
                print(f"  {len(walked) - 1:2d} 歩目で、地図にない物にぶつかった → 地図に書き足して、探し直す")
                break
            pos = q
            walked.append(q)
    print(f"  {how}：計画 {plans} 回、調べたマス目 合計 {looked_all}、移動距離 {len(walked) - 1} 歩")
    route = set(walked)
    for r in range(H):
        row = ""
        for c in range(W):
            ch = ROOM[r][c]
            row += ch if ch in "#SG?" else ("o" if (r, c) in route else ".")
        print("     " + row)

for how in ("幅優先", "深さ優先"):
    print(f"【{how}で探す】")
    run(how)
    print()
print("# = 地図にある壁　? = 地図にない物　o = 歩いた道")
print("幅優先は、地図の上で最短経路を見つける。深さ優先は、見つけた経路を進むだけなので、遠回りになりやすい。")

131966 · 電腦的眼睛

分開物體與背景

電腦怎麼找出照片中的？

1966年7月，MIT的Papert寫了一份備忘錄，計畫由暑期工作的人們完成視覺系統的（譯）。內容是從讀取裝置的影像中分開物體與背景，研究表面的性質，辨認已知物體的名稱。7月只處理彼此不重疊的球、磚塊和圓柱（表面顏色和背景都均勻）。8月再擴展到香菸盒和電池，接著是工具和杯子。

右邊的圖呈現第一步「分開物體與背景」的方式。把比門檻值暗的點當成物體，將相連的點歸為一群，再計算有幾群。背景均勻時，就能數對。但背景深淺不均時，連花紋都會被當成物體；物體彼此碰到時，也會被合併成1個。

物體的點 ⇔ 亮度＜門檻值　一群＝上下左右相連的物體點所組成的集合

撰寫AI歷史書的Nilsson（2010）指出，這項計畫比預期困難得多，但成了MIT持續研究視覺的契機。

以為知道的事常見說法：MIT想讓一名大學生在一個暑假裡解決『電腦視覺』
原始資料中：備忘錄列出約11位負責人的名字，計畫7月只處理均勻背景下的球、磚塊和圓柱，8月再逐步擴展。不過，後來的歷史書也寫道，這件事比預期困難得多。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_figure_ground.py

# u04 物と背景を分ける：しきい値で分け、つながった点をひとまとまりにして数える
#
# どの出来事か：1966年7月、MITの「夏の視覚プロジェクト」の覚え書き（記録 summer_vision_project_1966）。
#   画像の中で「物」と「背景」を分け、面の性質を調べ、知っている物の名前を当てる計画。
#   7月は、重ならずに置いた球・れんが・円柱だけ（面の色も背景も一様）で、8月に少しずつ広げる段階の計画だった。
# 仕組み（計画の最初の一歩を、最も単純にした例）：
#   ① 明るさがしきい値より暗い点を「物の点」とする
#   ② 上下左右でつながった物の点を、ひとまとまりにする（塗りつぶし）
#   ③ まとまりの数を数える
#   画像は、このサイトが作った例（覚え書きの図ではない）。
# 試してみよう：
#   - 最後の for の数値（背景のむら）を変えて、どこから個数が狂うか見る
#   - THRESHOLD を変えて、むらのある背景でも正しく 3 個と数えられるか試す

import random

W, H = 48, 20
THRESHOLD = 0.5

def scene(clutter, seed=1966):
    rnd = random.Random(seed)
    img = [[0.9 for _ in range(W)] for _ in range(H)]          # 白く一様な背景（明るさ 0.9）
    for y in range(H):
        for x in range(W):
            img[y][x] -= clutter * rnd.random()                 # 背景の模様（明るさのむら）
    for y in range(H):                                          # 球（円）
        for x in range(W):
            if (x - 8) ** 2 + ((y - 9) * 1.8) ** 2 < 36:
                img[y][x] = 0.2
    for y in range(6, 15):                                      # れんが（長方形）
        for x in range(18, 30):
            img[y][x] = 0.3
    for y in range(4, 17):                                      # 円柱（横から見た形）
        for x in range(37, 43):
            img[y][x] = 0.25
    return img

def label(img, th):
    lab = [[0] * W for _ in range(H)]
    n = 0
    for y in range(H):
        for x in range(W):
            if img[y][x] < th and not lab[y][x]:
                n += 1
                stack = [(y, x)]
                lab[y][x] = n
                while stack:
                    cy, cx = stack.pop()
                    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        ny, nx = cy + dy, cx + dx
                        if 0 <= ny < H and 0 <= nx < W and img[ny][nx] < th and not lab[ny][nx]:
                            lab[ny][nx] = n
                            stack.append((ny, nx))
    return lab, n

MARK = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for clutter in (0.0, 0.3, 0.45, 0.6):
    img = scene(clutter)
    lab, n = label(img, THRESHOLD)
    sizes = sorted((sum(row.count(k) for row in lab) for k in range(1, n + 1)), reverse=True)
    print(f"背景のむら {clutter}：見つけたまとまり {n} 個（正解は 3 個）　大きさ {sizes[:6]}{' …' if n > 6 else ''}")
    if clutter in (0.0, 0.6):          # 図は、いちばん一様なときと、むらがいちばん大きいときだけ出す
        for row in lab:
            print("   " + "".join(MARK[(k - 1) % 26] if k else "." for k in row))
        print()
print("一様な背景なら、しきい値1つで3つの物に分けられた。背景に模様があると、模様まで「物」になってしまう。")

141967 · 日本 · 學習方式

從誤差中逐步學習

機器怎麼從無法清楚分開的資料中學習？

1967年，甘利俊一在論文中，用數學研究學習方法。每看1個例子，就根據誤差逐步修正權重（每個特徵要看得多重要）。摘要指出，即使2組資料無法清楚分開，也能接近最佳權重，並說明速度與準確度之間的取捨。1968年的日語解說，把它稱為「隨機下降法」。

右邊的圖裡，2組的點有重疊。提高學習率η，會較快接近，但始終搖擺；調低則會穩定下來，但需要時間。讓η逐漸變小，就能兼顧兩者的優點。

w ← w − η ∇L（x, t ; w）

w: 權重
η: 學習率（修正的幅度）
L: 該1個例子的誤差
∇L: 指出往哪個方向修正，L才會減少的方向

Schmidhuber（2022）將它列為，用這種方法訓練多層類神經網路、可能是最早的一篇論文。不過，1967年的摘要討論的是線性分類器及其擴展的理論。

看過的例子數與錯誤率（虛線：最佳的線）

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_amari_online.py

# u04 誤差から少しずつ修正する学習法（甘利の 1967 年の理論の考え方）
#
# どの出来事か：1967 年、甘利俊一の論文「適応するパターン分類器の理論」（記録 amari_adaptive_classifier_1967）。
#   例を 1 つ見るたびに、誤差に応じて重みを少しずつ修正する学習法を数学的に分析した。
#   2 つの組がきれいに分けられないデータでも、最適な重みに近づくことや、
#   修正の速さと正確さの引きかえを示した。
#   1968 年の日本語の解説では、この学習法を「確率的降下法」と呼んでいる。
# このサンプルの仕組み：
#   2 つの組の点が重なり合っている（直線 1 本では、どう引いても誤りが残る）。
#   点を 1 つ見るたびに、誤差（ここでは (正解 − 線の値)² ÷ 2）が減る向きへ、重みを η だけ動かす。
#   データと数値は、このサイトが作った例。誤差の決め方は、ここでは一例（論文はもっと広く扱う）。
# 試してみよう：
#   - ETAS の η を変えて、「速いがゆれる」「落ち着くが遅い」を見る
#   - 「だんだん小さく」の 100 を 10 や 1000 にする

import random

random.seed(1967)

def sample():
    t = random.choice((1, -1))
    cx, cy = (0.8, 0.6) if t == 1 else (-0.5, -0.4)
    return (cx + random.gauss(0, 0.9), cy + random.gauss(0, 0.9)), t

TEST = [sample() for _ in range(2000)]
STREAM = [sample() for _ in range(3000)]

def err_rate(w):
    return sum(1 for (x, y), t in TEST if (w[0] * x + w[1] * y + w[2] > 0) != (t > 0)) / len(TEST)

def learn(eta_of):
    w = [-1.5, 1.0, 1.0]                         # 重みの初期値（わざと誤った向きにしておく）
    hist = []
    for n, ((x, y), t) in enumerate(STREAM, 1):
        u = w[0] * x + w[1] * y + w[2]
        g = t - u                                # 誤差を減らす向き
        eta = eta_of(n)
        w = [w[0] + eta * g * x, w[1] + eta * g * y, w[2] + eta * g]
        if n in (10, 50, 200, 1000, 3000) or (n > 2500 and n % 25 == 0):
            hist.append((n, err_rate(w)))
    return hist

ETAS = {
    "η = 0.1（大きく直す）": lambda n: 0.1,
    "η = 0.002（少しずつ直す）": lambda n: 0.002,
    "η をだんだん小さく": lambda n: 0.1 / (1 + n / 100),
}
print("見た例の数ごとの誤り率（別の 2000 個の点＝テストデータで調べた）")
for name, f in ETAS.items():
    hist = learn(f)
    main = [(n, e) for n, e in hist if n in (10, 50, 200, 1000, 3000)]
    tail = [e for n, e in hist if n > 2500]
    swing = max(tail) - min(tail)
    print(f"\n【{name}】")
    for n, e in main:
        print(f"  {n:5d} 個見た後：{e:5.1%} {'■' * round(e * 60)}")
    print(f"  最後の 500 個での誤り率のゆれ：{swing:.1%}")
print("\n大きく直すと早く良くなるが、最後までゆれる。少しずつ直すと落ち着くが、時間がかかる。")
print("だんだん小さくすると、初めは速く、最後は落ち着く（速さと正確さの引きかえ）。")

151968 · 搜尋

移動距離加估計值，找出最短路徑

搜尋迷宮時，應該先查看哪個格子？

1968年7月，SRI的Hart、Nilsson、Raphael發表了一篇論文，討論利用線索（啟發式）尋找最小成本路徑的理論。根據Nilsson的回憶，為了幫Shakey找路，他們想到在通往終點的估計值上，加上。只要估計值不大於真正的剩餘距離，就一定能找到最短路徑。這種搜尋方法被命名為A*（讀作A star）。

在右邊的迷宮裡比較3種情況吧。不使用估計值時，會從離起點最近的格子開始，查看四周所有格子。A* 則朝終點延伸。把估計值放大到3倍，查看的格子會減少，但找到的就不是最短路徑。

f(n)＝g(n)＋h(n)　先查看f較小的格子

g(n): 從起點到n的路程
h(n): 從n到終點的估計值（水平與垂直方向的直線距離）

這個迷宮查看的格子數是133、97、52，路徑長度是29、29、39。A* 現在也用於汽車導航和遊戲中（Nilsson 2010）。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_astar_maze.py

# u04 A*（エースター）：「ここまでの道のり＋ゴールまでの見積もり」で探す
#
# どの出来事か：1968 年 7 月、ハート、ニルソン、ラファエルの論文（記録 astar_search_1968）。
#   ロボット「シェーキー」の道探しのために、ここまで進んだ道のりに、ゴールまでのまっすぐの見積もりを
#   足して探す方法を作った。見積もりが本当の残りより大きくなければ、必ず最短の道が見つかることを示した。
# 仕組み：①見積もりなし（近い順に探索）②A*（ここまで＋見積もり）③見積もりを大きくしすぎた A* を比べる。
# 試してみよう：
#   - 3 つの結果の「調べたます目」と「道の長さ」を比べる（3 倍にすると速いが、最短ではなくなった）
#   - MAZE の壁（#）を動かす

import heapq

MAZE = [
    "S.##...#.#..........",
    ".#........#..#......",
    "....#...#......##...",
    ".........##.........",
    "#.......#...#..#..#.",
    ".....#..#..##.......",
    ".#..#..#....#...##.#",
    "...#.#.#..###..###.#",
    "#.#.#....#......##.G",
]
H, W = len(MAZE), len(MAZE[0])
start = next((r, c) for r in range(H) for c in range(W) if MAZE[r][c] == "S")
goal = next((r, c) for r in range(H) for c in range(W) if MAZE[r][c] == "G")

def search(weight):
    """weight=0 は見積もりなし、1 は A*、2 以上は見積もりを大きくしたもの。"""
    def guess(p):
        return weight * (abs(p[0] - goal[0]) + abs(p[1] - goal[1]))   # ゴールまでの見積もり（縦横の距離）
    frontier = [(guess(start), 0, start)]
    came = {start: None}
    cost = {start: 0}
    visited = []
    while frontier:
        _, g, p = heapq.heappop(frontier)
        if g > cost[p]:
            continue
        visited.append(p)
        if p == goal:
            break
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            q = (p[0] + dr, p[1] + dc)
            if 0 <= q[0] < H and 0 <= q[1] < W and MAZE[q[0]][q[1]] != "#":
                ng = g + 1
                if ng < cost.get(q, 10 ** 9):
                    cost[q] = ng
                    came[q] = p
                    heapq.heappush(frontier, (ng + guess(q), ng, q))
    path, p = [], goal
    while p:
        path.append(p)
        p = came[p]
    return visited, path[::-1]

for name, weight in (("見積もりなし（近い順）", 0), ("A*（ここまで＋見積もり）", 1), ("見積もりを 3 倍にしたもの", 3)):
    visited, path = search(weight)
    print(f"{name}：調べたます目 {len(visited)}、見つけた道の長さ {len(path) - 1}")
    seen, route = set(visited), set(path)
    for r in range(H):
        row = ""
        for c in range(W):
            ch = MAZE[r][c]
            if ch == "#":
                row += "■"
            elif ch in "SG":
                row += "Ｓ" if ch == "S" else "Ｇ"
            elif (r, c) in route:
                row += "◎"
            elif (r, c) in seen:
                row += "・"
            else:
                row += "　"
        print("   " + row)
print("■＝壁　◎＝見つけた道　・＝調べたけれど道にならなかったます目")

161968 · 日本

負值變成0，正值原樣輸出

只做加法的神經元，不管疊幾層，能做的事會增加嗎？

1968年，NHK放送科學基礎研究所的福島邦彦，參考貓和猴子的眼睛與大腦實驗，用電腦模擬多層電路網路。這是朝向讀取手寫文字機器的第一步。圖形每經過一層，就被分成獨立的點和不同方向的線段，接著找出線段的端點。

他使用的神經元，輸入總和是正值就原樣輸出，是負值就輸出0。這與現在深度學習中廣泛使用的ReLU形式相同。他也寫道，若全部用只做加法的神經元來組成，不管疊幾層都和2層一樣。在右邊的圖裡取消勾選「負值變成0（ReLU）」後，沒有線的地方的負值就會流入下一層，無法正確找出端點。

輸出＝max(0, Σ權重 × 輸入)

max(0, u): u是負值就輸出0，是正值就原樣輸出（現在稱為ReLU）

圖中的權重經過本站簡化（並非1968年電路網路的原始權重）。找出端點的神經元，會將線上相鄰位置的值相減。

以為知道的事常見說法：ReLU是2010年代深度學習的發明
原始資料中：相同形式的活化函數（負值變成0，正值原樣輸出），在福島1968年的日語解說和1969年的英語論文中，就已經用來模仿眼睛的運作方式。

輸入總和與神經元的輸出

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_relu_layers.py

# u04 「負なら 0、正ならそのまま」のニューロンを重ねて、線と線の端を見つける
#
# どの出来事か：1968 年、NHK の福島邦彦の「アナログ多層回路網による特徴抽出」（記録 fukushima_feature_network_1968）。
#   目と脳の仕組みを手本に層を重ね、図形を、孤立した点・向きごとの線分・線分の端点に分けていった。
#   ニューロンは、入力の合計が正ならそのまま、負なら 0 を出すもの（今の ReLU と同じ形）。
#   全部を足し算だけにすると、何層重ねても 2 層と同じになる、とも書いている。
# このサンプルの仕組み（このサイトが単純化した例。1968 年の回路網の重みそのものではない）：
#   ① 線の層：向き（横・縦）ごとに、隣の 3 つの点を足して 2 を引く → 3 つ並んでいる所だけ正になる
#   ② 端の層：線の層のある点から、その向きの隣の点を引く（隣に線が続いていなければ正）
#   ③ それぞれの層で「負なら 0」を使うか使わないかを切り替えて、結果を比べる
# 試してみよう：
#   - PATTERN の形を変える（「十」「L」など）
#   - 結果の「負なら 0」を使わない（足し算だけ）の方で、端ではない所にまで反応が出る理由を考える

PATTERN = [
    "..........",
    ".#######..",
    "....#.....",
    "....#.....",
    "....#.....",
    "....#.....",
    "..........",
]
H, W = len(PATTERN), len(PATTERN[0])
IMG = [[1 if ch == "#" else 0 for ch in row] for row in PATTERN]
DIRS = {"横": (0, 1), "縦": (1, 0)}

def px(img, y, x):
    return img[y][x] if 0 <= y < H and 0 <= x < W else 0

def relu(u, on=True):
    return max(0, u) if on else u

def line_layer(img, d, on):
    dy, dx = d
    return [[relu(px(img, y - dy, x - dx) + px(img, y, x) + px(img, y + dy, x + dx) - 2, on) for x in range(W)] for y in range(H)]

def end_layer(line, d, sign, on):
    """sign=+1：その向きの先の端、-1：手前の端。隣を引き、線が続いていない所だけ正にする。"""
    dy, dx = d[0] * sign, d[1] * sign
    return [[relu(px(line, y, x) - px(line, y + dy, x + dx), on) for x in range(W)] for y in range(H)]

def show(grid):
    return ["".join("." if v == 0 else ("+" if v > 0 else "-") for v in row) for row in grid]

for on in (True, False):
    print(f"━━ 「負なら 0」を {'使う（ReLU）' if on else '使わない（足し算だけ）'}")
    ends = set()
    for name, d in DIRS.items():
        ln = line_layer(IMG, d, on)
        e1, e2 = end_layer(ln, d, +1, on), end_layer(ln, d, -1, on)
        for grid in (e1, e2):
            ends |= {(y, x) for y in range(H) for x in range(W) if grid[y][x] > 0}
        print(f"  {name}の線の層" + " " * 6 + f"{name}の端の層（先・手前）")
        for a, b, c in zip(show(ln), show(e1), show(e2)):
            print(f"   {a}   {b}  {c}")
    print(f"  端と答えた場所：{len(ends)} か所（+ は正、- は負）\n")
print("足し算だけだと、線のない所の負の値（-2 など）が次の層に流れ込み、引き算で消えたり、端でない所に正が出たりする。")

# 足し算だけの層を重ねても、入力と出力の 2 層だけの回路（掛けて足す 1 回）にまとまることを確かめる
a = [[2, -1], [0, 3]]
b = [[1, 4], [-2, 1]]
ab = [[sum(b[i][k] * a[k][j] for k in range(2)) for j in range(2)] for i in range(2)]
x = [1, -2]
two = [sum(b[i][k] * sum(a[k][j] * x[j] for j in range(2)) for k in range(2)) for i in range(2)]
one = [sum(ab[i][j] * x[j] for j in range(2)) for i in range(2)]
print(f"\n足し算だけの層を 2 段通す：{two}　掛け算をまとめて 1 段で：{one} → 同じ（何段重ねても、入力と出力の 2 層だけの回路と同じ）")
print(f"段の間に「負なら 0」を挟むと：{[relu(sum(b[i][k] * relu(sum(a[k][j] * x[j] for j in range(2))) for k in range(2))) for i in range(2)]}（まとめられない）")

171968〜1969 · 日本

讀出手寫的郵遞區號

機器怎麼處理讀不出來的文字？

日本郵遞區號制度開始的1968年7月1日，東芝在郵政省指導下開發的郵遞區號自動讀取分揀機，在東京中央郵局公開展示。讀取人自由手寫的數字並分揀郵件，被認為是。它分析了從全國蒐集的約30萬個手寫數字，用光學濾鏡去掉紅框，以每1秒約6封的速度讀取前3碼。

根據開發者1969年的論文，它將文字分成橫向條帶逐條檢查，把特徵分成19種，再將這些特徵由上到下的排列，與字典裡儲存的各個數字變形的排列比較。不符合的地方有2處以上，就排除該數字。剩下1個，那就是答案；剩下0個或2個以上，就記為「拒絕讀取」，交給人處理。

剩下的數字＝ { d｜不符合的地方數（文字的排列, d的字典排列）＜2 }

剩下1個: 那就是答案
0個或2個以上: 拒絕讀取（由人來讀）

圖中的文字和特徵（5種）是本站製作的範例。1969年第一屆國際人工智慧聯合會議上，日本的5篇論文中，有3篇是文字辨識研究。

雜訊量與讀取結果

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_postal_digits.py

# u04 手書きの郵便番号を読む：型と比べ、自信がない字は人に回す
#
# どの出来事か：1968年7月1日、郵便番号制度が始まった日に、東芝が郵政省の指導で開発した
#   郵便番号自動読取区分機が公開された（記録 postal_code_reader_1968）。読めない字は「読取拒否」として人に回した。
# このサンプルの仕組み：数字の「型」（5×7のマス目）と、ゆがんだ手書き風の数字を1マスずつ比べ、
#   いちばん似ている型を答えにする。1位と2位の差が小さい（自信がない）ときは、答えずに人に回す。
#   ※ 1968年の機械は、線の向きの並びを使うなど、もっと工夫した読み方をしていた。いちばん下に、
#     それに近い読み方（横の帯の特徴の上下の並びを辞書と比べ、2か所以上合わない数字は外す）も入れた。
#   ※ 手書き風の数字は、このプログラムが型をずらしたり、点の白黒を変えたりして作った例（本物の手書きではない）。
# 試してみよう：
#   - NOISE（点の白黒が変わる割合）を上げると、何が起きるか
#   - 最後の「ずらして比べる」は、なぜ効くのか（→ u05 の福島さんのネオコグニトロン）
#   - いちばん下の「1968 年の機械に近い読み方」で、合わない所をいくつまで許すか（< 2）を < 1 にすると、どう変わるか

import random

random.seed(1968)
NOISE = 0.10    # 1 マスの白黒が反転する割合
SHIFT = 0.5     # 字が上下左右に 1 マスずれる割合
FONT = {
    "0": [".###.", "#...#", "#..##", "#.#.#", "##..#", "#...#", ".###."],
    "1": ["..#..", ".##..", "..#..", "..#..", "..#..", "..#..", ".###."],
    "2": [".###.", "#...#", "....#", "...#.", "..#..", ".#...", "#####"],
    "3": ["#####", "...#.", "..#..", "...#.", "....#", "#...#", ".###."],
    "4": ["...#.", "..##.", ".#.#.", "#..#.", "#####", "...#.", "...#."],
    "5": ["#####", "#....", "####.", "....#", "....#", "#...#", ".###."],
    "6": ["..##.", ".#...", "#....", "####.", "#...#", "#...#", ".###."],
    "7": ["#####", "....#", "...#.", "..#..", ".#...", ".#...", ".#..."],
    "8": [".###.", "#...#", "#...#", ".###.", "#...#", "#...#", ".###."],
    "9": [".###.", "#...#", "#...#", ".####", "....#", "...#.", ".##.."],
}
H, W = 7, 5

def to_grid(rows):
    return [[1 if ch == "#" else 0 for ch in row] for row in rows]

def shifted(g, dy, dx):
    return [[g[y - dy][x - dx] if 0 <= y - dy < H and 0 <= x - dx < W else 0 for x in range(W)] for y in range(H)]

def handwrite(d):
    g = to_grid(FONT[d])
    if random.random() < SHIFT:
        g = shifted(g, random.choice([-1, 0, 1]), random.choice([-1, 0, 1]))
    return [[1 - v if random.random() < NOISE else v for v in row] for row in g]

def similarity(a, b):
    return sum(a[y][x] == b[y][x] for y in range(H) for x in range(W))   # 一致するマスの数（35 点満点）

TEMPLATES = {d: to_grid(rows) for d, rows in FONT.items()}

def read(g, try_shifts=False):
    scores = []
    for d, t in TEMPLATES.items():
        cands = [t] if not try_shifts else [shifted(t, dy, dx) for dy in (-1, 0, 1) for dx in (-1, 0, 1)]
        scores.append((max(similarity(g, c) for c in cands), d))
    scores.sort(reverse=True)
    (s1, d1), (s2, _) = scores[0], scores[1]
    return d1, s1 - s2   # 答えと、1 位と 2 位の差（自信）

tests = [(d, handwrite(d)) for d in FONT for _ in range(100)]   # 各数字 100 字、計 1000 字
print("手書き風の 3 の例:")
for row in [d for d in tests if d[0] == "3"][0][1]:
    print("   " + "".join("■" if v else "・" for v in row))

for try_shifts in (False, True):
    results = [(d, *read(g, try_shifts)) for d, g in tests]
    title = "型をずらして比べる" if try_shifts else "型をそのまま比べる"
    print(f"\n【{title}】")
    print("  人に回す基準（差がこれ未満なら人へ）  人に回した字  機械が読んだ字の正しさ")
    for margin in (0, 1, 2, 3, 4):
        taken = [(d, a) for d, a, gap in results if gap >= margin]
        ok = sum(d == a for d, a in taken)
        print(f"  差 {margin} 未満 {'':18} {1000 - len(taken):4d} 字 {'':10} {ok / max(1, len(taken)):.1%}")

# ---------------------------------------------------------------------------
# 1968 年の機械に近い読み方：横の帯の特徴の「上下の並び」を、辞書の並びと比べる
#   1969 年の開発者の論文（記録 postal_code_reader_1968）によると、字を横の細い帯ごとに調べて
#   横の特徴を 19 種類に分け、その上下の並びを、辞書に入れた各数字の変形の並びと比べた。
#   合わない所が 2 か所以上ある数字は外し、残りが 1 つなら答え、0 か 2 つ以上なら「読取拒否」とした。
#   ここでは、特徴を 5 種類だけにした（このサイトが単純にした例）：
#     _＝何もない  -＝横棒  L＝左に線  C＝中央に線  R＝右に線  D＝線が 2 本
# ---------------------------------------------------------------------------

def row_feature(row):
    runs, x = [], 0
    while x < W:
        if row[x]:
            s = x
            while x < W and row[x]:
                x += 1
            runs.append((s, x - 1))
        x += 1
    if not runs:
        return "_"
    if len(runs) >= 2:
        return "D"
    s, e = runs[0]
    if e - s >= 2:
        return "-"
    c = (s + e) / 2
    return "L" if c < 1.5 else ("R" if c > 2.5 else "C")

def feature_seq(g):
    seq = [row_feature(r) for r in g]
    out = [f for i, f in enumerate(seq) if i == 0 or f != seq[i - 1]]   # 同じ特徴の連続を 1 つにまとめる
    return "".join(out).strip("_")

def mismatch(a, b):
    """合わない所の数（1 文字の置換・挿入・削除を 1 回と数える）"""
    d = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        prev, d[0] = d[0], i
        for j, cb in enumerate(b, 1):
            prev, d[j] = d[j], min(d[j] + 1, d[j - 1] + 1, prev + (ca != cb))
    return d[-1]

# 辞書：型そのものと、上下左右に 1 マスずらした変形の並び（1968 年の辞書は、約 30 万字の手書き数字の分析から作った）
DICT = {d: sorted({feature_seq(shifted(t, dy, dx)) for dy in (-1, 0, 1) for dx in (-1, 0, 1)}) for d, t in TEMPLATES.items()}
print("\n【1968 年の機械に近い読み方：横の特徴の並びを辞書と比べる】")
print("  辞書（数字ごとの並びの変形。一部）：")
for d, seqs in DICT.items():
    print(f"    {d}：{' / '.join(seqs[:5])}{' …' if len(seqs) > 5 else ''}")

def read_1968(g):
    seq = feature_seq(g)
    left = [d for d, seqs in DICT.items() if min(mismatch(seq, s) for s in seqs) < 2]   # 合わない所が 2 か所以上なら外す
    return (left[0] if len(left) == 1 else None), seq, left

def score(samples):
    right = wrong = reject = 0
    for d, g in samples:
        ans, _, _ = read_1968(g)
        if ans is None:
            reject += 1
        elif ans == d:
            right += 1
        else:
            wrong += 1
    return right, wrong, reject

ex = [t for t in tests if t[0] == "3"][0][1]
ans, seq, left = read_1968(ex)
print(f"  上の手書き風の 3 の並び：{seq}　残った数字：{left} → {ans if ans else '読取拒否'}")
for noise in (0.0, 0.02, NOISE):
    rnd = random.Random(7)
    samples = []
    for d in FONT:
        for _ in range(100):
            g = to_grid(FONT[d])
            if rnd.random() < SHIFT:
                g = shifted(g, rnd.choice([-1, 0, 1]), rnd.choice([-1, 0, 1]))
            samples.append((d, [[1 - v if rnd.random() < noise else v for v in row] for row in g]))
    right, wrong, reject = score(samples)
    print(f"  雑音 {noise:.2f} の 1000 字：正しく読んだ {right}、まちがえた {wrong}、読取拒否（人へ） {reject}"
          f"　機械が答えた字の正しさ {right / max(1, right + wrong):.1%}")
print("  特徴を 5 種類にしぼったので、別の数字と並びが似てしまい、読取拒否が多くなる（1968 年の機械は 19 種類）。")
print("  雑音が増えると、読取拒否もまちがいも増える。1968 年の機械は、線の太さをそろえる回路や、")
print("  字の大きさをそろえる回路で、比べる前に字を整えていた。")

181967〜1970 · 預言

一代人之內、3〜8年、近期可能性不大

同一時期的展望，是寫在哪裡的話？

1967年，明斯基在著作中寫道：（譯）。1970年，Life雜誌記者的文章寫道，明斯基說（譯），也轉述其他研究者說（譯）。1968年的電影中，出現了用人聲說話的電腦HAL 9000。

同樣是1968年，日本的甘利俊一寫道：（譯）。右邊的圖用線連起說出預言的年份和期限。顏色與標籤的形狀，表示話語的出處。調整「目前年份」，就會顯示已到期限的預言，後來發生了什麼事。

是幾年，書裡沒有寫。歷史學家的書說，明斯基後來寫過反駁文章，否認那段引文，但未能確認他否認的是不是這句話。

以為知道的事常見說法：明斯基在1970年斷言「3〜8年內會出現具有人類程度智慧的機器」
原始資料中：原文是雜誌記者文章中的話（Life雜誌，1970年11月20日號，第58D頁）。他本人著作（1967年）的說法是「一代人之內」（未能看到原書的頁面，是透過引用這本書的2本書查證的）。

191971 · 語言

在積木世界裡，話就說得通

只要縮小範圍，電腦就能語言嗎？

1971年1月，MIT的Winograd在博士論文裡發表了一個程式（後來稱為SHRDLU），能在英語對話中回答問題、執行指令。場景是有手和眼睛的簡單機器人，在桌上移動積木和金字塔的世界。對（譯），它先移開上方的積木，再拿起並回答；對（譯），因為場景裡有3個，它會反問：（譯）

在右邊的圖裡按「下指令」吧。用形狀、顏色、大小的詞語篩選物體，確定只有1個就行動，2個以上就反問，沒有就回答沒有。論文的詞彙量是200個詞，處理1句話需要5〜20秒。

符合的有1個 → 行動　2個以上 → 反問　0個 → 回答沒有

符合的物體: 形狀、顏色、大小符合指令中詞語的物體

以為知道的事常見說法：SHRDLU用機器人手臂移動真正的積木，也理解了英語
原始資料中：論文裡，機器人和積木是螢幕上的模擬。場景資料假設有，一開始就提供給程式，對話則透過打字進行。他本人在2004年寫道，SHRDLU的運作方式與大腦的運作方式之間，有根本的鴻溝（根據Nilsson）。

這是用Python寫的程式碼，原理和「動手試試」裡的一樣。按下▶ 執行，結果會顯示在下方。改改數字，再執行一次試試。

u04_blocks_world.py

# u04 積み木の世界で命令を聞く（SHRDLU のまね）
#
# どの出来事か：1971年1月、MITのウィノグラードの博士論文のプログラム（のちにSHRDLUと呼ばれる。記録 winograd_shrdlu_1971）。
#   机の上の積み木やピラミッドを動かす世界。「大きな赤い積み木を持ち上げて」（訳）には上の積み木をどけて持ち上げた。
#   「そのピラミッドをつかんで」（訳）には、場面に3つあるので聞き返した。「それ」が何を指すかも判断した。
#   ロボットと積み木は画面上のシミュレーションで、語彙は200語だった。
# このサンプルの仕組み（このサイトが小さくした例。論文のプログラムの中身ではない）：
#   ① 命令を言葉に分け、知っている言葉（大きさ・色・形・動き）だけで読む。知らない言葉があれば、そう答える
#   ② 大きさ・色・形が合う物を探す。1つなら動く。2つ以上なら聞き返す。0なら「見つからない」
#   ③ 持ち上げる物の上に何か載っていれば、先にどける。手に何か持っていれば、先に置く
#   ④ 「それ」は、前の命令で決まった物を指す
# 試してみよう：
#   - COMMANDS に「小さな 緑の 積み木 を 持ち上げて」を足す
#   - 知らない言葉（例：「そっと」）を入れると、どう答えるか

SIZE = {"大きな": "大", "小さな": "小"}
COLOR = {"赤い": "赤", "緑の": "緑", "青い": "青", "黄色い": "黄"}
SHAPE = {"積み木": "積み木", "ピラミッド": "ピラミッド", "箱": "箱"}
VERB = {"持ち上げて": "take", "つかんで": "take", "置いて": "put", "入れて": "into"}
OTHER = {"を", "に", "それ", "机"}

# 物：名前 → (大きさ, 色, 形)。位置：何の上（または中）にあるか
THINGS = {
    "A": ("大", "赤", "積み木"), "B": ("小", "緑", "積み木"), "C": ("大", "緑", "積み木"),
    "D": ("小", "赤", "ピラミッド"), "E": ("小", "緑", "ピラミッド"), "F": ("大", "青", "ピラミッド"), "箱": ("大", "白", "箱"),
}
ON = {"A": "机", "B": "A", "C": "机", "D": "C", "E": "机", "F": "箱", "箱": "机"}
hand = None
last = None

def desc(k):
    s, c, sh = THINGS[k]
    adj = {"赤": "赤い", "緑": "緑の", "青": "青い", "白": "白い", "黄": "黄色い"}[c]
    return f"{'大きな' if s == '大' else '小さな'}{adj}{sh}（{k}）"

def top_of(k):
    return [x for x, below in ON.items() if below == k and THINGS[k][2] != "箱"]

def put_on_table(k, log):
    ON[k] = "机"
    log.append(f"{desc(k)}を机に置く")

def take(k, log):
    global hand
    if hand and hand != k:
        put_on_table(hand, log)
        hand = None
    for x in top_of(k):                      # 上に載っている物を先にどける
        take(x, log)
        put_on_table(x, log)
        globals()["hand"] = None
    ON[k] = "手"
    hand = k
    log.append(f"{desc(k)}を持ち上げる")

def command(text):
    global last, hand
    words = text.split()
    unknown = [w for w in words if w not in SIZE and w not in COLOR and w not in SHAPE and w not in VERB and w not in OTHER]
    if unknown:
        return f"知らない言葉があります：{'・'.join(unknown)}", []
    verb = next((VERB[w] for w in words if w in VERB), None)
    obj_words = words[:words.index("を")] if "を" in words else []
    if obj_words == ["それ"]:
        found = [last] if last else []
    else:
        size = [SIZE[w] for w in obj_words if w in SIZE]
        color = [COLOR[w] for w in obj_words if w in COLOR]
        shape = [SHAPE[w] for w in obj_words if w in SHAPE]
        found = [k for k, (s, c, sh) in THINGS.items()
                 if (not size or s == size[0]) and (not color or c == color[0]) and (not shape or sh == shape[0])]
    if not found:
        return "そんな物は見つかりません。", []
    if len(found) > 1:
        name = obj_words[-1] if obj_words else "物"
        return f"どの{name}のことか分かりません。（候補：{'、'.join(desc(k) for k in found)}）", []
    k = found[0]
    last = k
    log = []
    if verb == "take":
        if THINGS[k][2] == "箱":
            return "箱は持ち上げられません。", []
        take(k, log)
    elif verb == "put":
        if hand != k:
            take(k, log)
        put_on_table(k, log)
        hand = None
    elif verb == "into":
        if hand != k:
            take(k, log)
        ON[k] = "箱"
        hand = None
        log.append(f"{desc(k)}を箱に入れる")
    return "OK.", log

def scene():
    rows = []
    for base in [k for k, b in ON.items() if b == "机"]:
        stack, cur = [base], base
        while True:
            up = [x for x, b in ON.items() if b == cur]
            if not up or THINGS[cur][2] == "箱":
                break
            cur = up[0]
            stack.append(cur)
        inside = [x for x, b in ON.items() if b == "箱"] if base == "箱" else []
        rows.append(" の上に ".join(desc(x) for x in stack) + (f"［中：{'、'.join(desc(x) for x in inside)}］" if inside else ""))
    return rows + ([f"手：{desc(hand)}"] if hand else ["手：なし"])

COMMANDS = [
    "大きな 赤い 積み木 を 持ち上げて",
    "ピラミッド を つかんで",
    "青い ピラミッド を つかんで",
    "それ を 箱 に 入れて",
    "緑の 積み木 を 持ち上げて",
    "黄色い 積み木 を 持ち上げて",
    "赤い ピラミッド を そっと 置いて",
]
print("初めの場面：")
for r in scene():
    print("   ", r)
for c in COMMANDS:
    answer, log = command(c)
    print(f"\n人：{c.replace(' ', '')}")
    for step in log:
        print(f"   （動き）{step}")
    print(f"機械：{answer}")
print("\n終わりの場面：")
for r in scene():
    print("   ", r)

每次分辨1個音

記住動作並反覆執行的手臂

西洋跳棋真的「已解決」了嗎

把應用題改寫成式子來解

揭開ELIZA的運作方式

ELIZA是哪一年的成果

列出所有候選，再用規則篩選

「高個子」從幾cm開始？

機器會變得能做人類的任何工作嗎

每年增加為2倍，持續10年會怎樣

縮小要推演的走法

撞到東西，就修改地圖重新搜尋

分開物體與背景

從誤差中逐步學習

移動距離加估計值，找出最短路徑

負值變成0，正值原樣輸出

讀出手寫的郵遞區號

一代人之內、3〜8年、近期可能性不大

在積木世界裡，話就說得通

本章仍不清楚的事

西洋跳棋真的了嗎