第1次ブームのはじまり

011955・名前と計画書

を掲げた夏の計画書

という名前は、どこで、どんな見通しとともに生まれたのか。

1955年8月31日付で、マッカーシー、ミンスキー、ロチェスター、シャノンの4人が、翌年の夏にダートマス大学で開く研究会の計画書を書き、ロックフェラー財団に資金を申請した。その題に入っていたのがという言葉だ。計画書は、学習や知能のどんな特徴も、原理的には（訳）という予想から出発する。

右の7つの箱が、計画書に並ぶ研究課題だ。押すと中身が表示される。言語、ニューラルネットワーク、計算の規模、自己改良する機械。この章の見開きの多くは、どれかの続きにあたる。

期間は2か月、参加者は10人を見込んだ。選ばれた科学者がひと夏集まって取り組めば、挙げた課題の（訳）と書いた。申請した予算は13,500ドルだったが、財団から助成されたのは7,500ドルだった。

予算表の各項目を足すと13,000ドルになり、表に書かれた合計13,500ドルと500ドル合わない（マッカーシーのサイトにある再録版で確認。差の理由は書かれていない）。

知ってるつもりよく言われる話：は全員一致で決めた名前
元の資料では：マッカーシーが選んだ名前で、当時から異論もあった。ニューウェルとサイモンは何年もという別の呼び名を使っていた。

知ってるつもりよく言われる話：ダートマスの参加者はひと夏でAIを完成させるつもりだった
元の資料では：計画書の表現は（訳）。完成させるとは書いていない。

021956・ダートマス

ひと夏の研究会はどんな集まりだったか

「AIが生まれた大きな会議」は、本当はどんな集まりだったのか。

1956年の夏、ダートマス大学の数学科の最上階に、考える機械に関心を持つ研究者が集まった。参加者ソロモノフのメモによると、期間は6月18日ごろから8月17日までのおよそ8週間だった。決まった日程の会議というより、人が入れかわりで訪れては話し合う集まりだった。

右の図で「くわしく：予定と記録」を押すと、5月26日にマッカーシーが財団に伝えた予定（紫の枠）に、ソロモノフとモアのメモに残る「その日にいた人」（紺の点）を重ねて見られる。全期間いたのは3人だけで、予定された11人のうち2人は来なかった。毎日の話し合いに参加したのは3〜8人ほどだった。

全員で1つの課題に取り組む相談もあった。8月7日、マッカーシーがチェスを持ちかけたが、共同研究にはならなかった。マッカーシーは後に、資金が足りず、それぞれに別の用事があって、全員がひと夏そろう計画は実現しなかったと語っている。

正確な名簿は残っていない（マッカーシーは自分の名簿をなくした）。点はメモに残る日だけであり、点のない日に来ていなかったとは限らない。

知ってるつもりよく言われる話：ダートマスの研究会は、AIが生まれた大規模な会議だった
元の資料では：実際は人が入れかわりで訪れる夏の集まりで、毎日の話し合いは3〜8人ほど。財団からの資金は希望額の約半分で、研究会としての報告書も出版されなかった。

6週目（7月23〜27日）の毎日の話し合いに参加した人数（モアのメモ）

031956・探索

証明を片っ端から作ると

作れる証明を全部、順番に作っていけば、いつか目当ての定理にたどり着くのでは？

ニューウェル、ショー、サイモンが挑んだのは、本の論理の定理だ。5つの公理から、文字に式を入れる代入、同じ意味の形に直す置き換え、Aと「AならばB」からBを得る切り離し、の3つの規則で新しい定理を作る。

一番単純なのは、作れる証明を短い順にすべて作り、目当ての式が出るのを待つ方法だ。3人はこれを大英博物館のやり方（British Museum algorithm）と呼び、比較の相手にした。報告の数値では4段目までに42個、8段目までに246個。第2章をすべてそろえるには1億個ほど必要になるかもしれず、何十万年もかかると見積もった。

答えの候補を順に調べることを探索という。しらみつぶしでは候補が多すぎるため、近道の知恵（ヒューリスティクス）で調べる範囲を絞る必要がある。右の図は、このサイトの数え方で式を作っていく。

n段目の式の数 ≈（n−1段目の式の数）×（1か所の変え方の数）

変え方: pを ¬pにする、→ と ¬…∨ を入れ替えるなど

段ごとの式の数（縦軸は10倍ずつ）

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_british_museum.py

# u03 「大英博物館のやり方」：証明を片っぱしから作ると、どれだけ増えるか
#
# どの出来事か：1957年1月のロジック・セオリストの報告（記録 logic_theorist_1956）。
#   ニューウェルたちは比較対象として、公理から作れる証明をすべて順に作っていく手法を考え、
#   冗談まじりに British Museum algorithm（大英博物館のやり方）と呼んだ。報告にある数値：
#   4段目までに42個、6段目までに115個、8段目までに246個、11段目までで約1,000個。
#   第2章の定理をすべてそろえるには1億個ほど要るかもしれず、何十万年もかかると見積もった。
# 仕組み：公理（5個）から出発し、1段ごとに、前の段の式の1か所だけを変えた式をすべて作る。
#   変え方は報告の図2と同じ2種類。文字を「でない＋その文字」にする（p → -p）、
#   「ならば」と「でない…または」を入れかえる（p > q ⇔ -p v q）。
#   ※ 数え方はこのサイト独自のもので、報告の数とは一致しない。増え方の傾向を見るためのもの。
# 試してみよう：
#   - SPECIALIZE を True にして、文字どうしの代入（q を p にするなど）も入れると、2.07 は出てくるか
#   - STEPS を 12 にすると、作る式の数はどれだけ増えるか

STEPS = 10
SPECIALIZE = False

AXIOMS = ["(p v p) > p", "p > (q v p)", "(p v q) > (q v p)", "(p v (q v r)) > (q v (p v r))", "(p > q) > ((r v p) > (r v q))"]
TARGETS = {"2.01": "(p > -p) > -p", "2.02": "p > (q > p)", "2.07": "p > (p v p)"}

def parse(s):
    toks = s.replace("(", " ( ").replace(")", " ) ").replace("-", " - ").split()
    pos = 0

def expr():
        nonlocal pos
        left = unary()
        if pos < len(toks) and toks[pos] in (">", "v"):
            op = toks[pos]
            pos += 1
            return ("i" if op == ">" else "o", left, expr())
        return left

def unary():
        nonlocal pos
        t = toks[pos]
        pos += 1
        if t == "-":
            return ("n", unary())
        if t == "(":
            e = expr()
            pos += 1
            return e
        return ("v", t)
    return expr()

def show(e):
    if e[0] == "v":
        return e[1]
    if e[0] == "n":
        return "-" + (show(e[1]) if e[1][0] in ("v", "n") else f"({show(e[1])})")
    a, b = show(e[1]), show(e[2])
    a = a if e[1][0] in ("v", "n") else f"({a})"
    b = b if e[2][0] in ("v", "n") else f"({b})"
    return f"{a} {'>' if e[0] == 'i' else 'v'} {b}"

def letters(e, out=None):
    out = set() if out is None else out
    if e[0] == "v":
        out.add(e[1])
    else:
        for x in e[1:]:
            letters(x, out)
    return out

def put(e, v, new):
    if e[0] == "v":
        return new if e[1] == v else e
    if e[0] == "n":
        return ("n", put(e[1], v, new))
    return (e[0], put(e[1], v, new), put(e[2], v, new))

def replacements(e):
    """1 か所だけ「ならば」⇔「でない…または」を入れかえた式をすべて作る。"""
    out = []
    if e[0] == "i":
        out.append(("o", ("n", e[1]), e[2]))
    if e[0] == "o" and e[1][0] == "n":
        out.append(("i", e[1][1], e[2]))
    if e[0] == "n":
        out += [("n", x) for x in replacements(e[1])]
    if e[0] in ("i", "o"):
        out += [(e[0], x, e[2]) for x in replacements(e[1])]
        out += [(e[0], e[1], x) for x in replacements(e[2])]
    return out

def one_change(e):
    ls = sorted(letters(e))
    out = [put(e, v, ("n", ("v", v))) for v in ls]           # p → -p
    if SPECIALIZE:
        out += [put(e, v, ("v", w)) for v in ls for w in ls if v != w]   # q → p
    return out + replacements(e)

targets = {k: parse(s) for k, s in TARGETS.items()}
seen = {parse(a) for a in AXIOMS}
level = list(seen)
total = len(seen)
found = {}
print(f"段  作った式の合計   （公理 5 個から）")
print(f" 1  {total:>8}")
for step in range(2, STEPS + 1):
    new = []
    for e in level:
        for x in one_change(e):
            if x not in seen:
                seen.add(x)
                new.append(x)
                for k, t in targets.items():
                    if x == t and k not in found:
                        found[k] = (step, total + len(new))
    total += len(new)
    level = new
    hits = "、".join(f"{k} が見つかった（{n} 個目）" for k, (s, n) in found.items() if s == step)
    print(f"{step:>2}  {total:>8}  " + "■" * min(60, total // 100) + ("  " + hits if hits else ""))

for k in TARGETS:
    if k not in found:
        print(f"{k} {TARGETS[k]} は、{STEPS} 段までに見つからなかった")
print("\n例：最後の段で作った式の最初の 5 個")
for e in level[:5]:
    print("   ", show(e))

041956・ロジック・セオリスト

答えの側から、逆向きに探す

定理の証明を、人のように当たりをつけて探すには？

ロジック・セオリスト（LT）は、全部を作る代わりに、証明したい式の側から逆向きに探した。4つの方法を順に試す。代入法は、公理やすでに証明した定理の文字に式を入れて、問題とぴったり同じ形にできるか調べる。切り離し法は「AならばB」の定理でBが問題と合うものを探し、Aを新しい小さな問題にする。前向き・後ろ向きのつなぎも、小さな問題を作る。

1957年の報告では、第2章の最初の 52の定理のうち38の証明を見つけた。17は代入法だけで、19は2手で解けた。2.01は約10秒、2.45は約12分。2.31は約23分で探索の手が尽きた。右の図は、このサイトが作った小さなLT。「最後まで」を押すと木が下へ伸び、緑の道が証明になる。

報告はこうたとえた。公理から前へ進むのが干し草の山から1本の針を探すことなら、目当てから後ろへ戻るのは、針が山から出る道を探すのに似ている。

図のLTは、1956年のプログラムと細かい所が違う。報告は4つの方法では2.13は証明できないと書くが、このサイトの例は形のそろえ方と用意した定理の条件が違うため、「用意した定理も使う」にチェックを入れると、2.13の証明も見つける。

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_logic_theorist.py

# u03 ロジック・セオリスト：証明を「答えの側から、逆向きに」探す（1956 年の仕組みを小さくした例）
#
# どの出来事か：1956 年、ニューウェル、ショー、サイモンのロジック・セオリスト（記録 logic_theorist_1956）。
#   ホワイトヘッドとラッセルの著書『プリンキピア・マテマティカ』第 2 章の定理の証明を探索した。
#   1957 年の報告では、最初の 52 の定理のうち 38 の証明を見つけた。2.01 は約 10 秒、2.45 は約 12 分。
# 仕組み：原著と同じ 5 つの公理から出発する。証明したい式（問題）に対して、次の 4 つの「方法」を順に試す。
#   1. 代入法：公理や、すでに証明した定理の文字（p, q, r）に式を代入し、問題と一致させられるか調べる
#   2. 切り離し法：「A ならば B」の形の定理で、B が問題と一致するものを探し、A を新しい小さな問題にする
#   3. 前向きのつなぎ：問題が「a ならば c」のとき、「a ならば b」の定理を探し、「b ならば c」を新しい問題にする
#   4. 後ろ向きのつなぎ：「b ならば c」の定理を探し、「a ならば b」を新しい問題にする
#   新しい問題は、すぐ代入法で解けないか試し、解けなければ「あとで考える問題の列」に並べる。
#   ※「A ならば B」は「A でない、または B」と同じとして、形をそろえてから比べる（原著の「置きかえ」の決まり）。
#   ※ これはこのサイトが作成した小さな例。1956 年のプログラムの細かい点（似ているかの判定方法など）は同じではない。
#   報告と同じく、ある定理を証明するときは、公理と、それより前の定理を全部「使ってよい物」として渡す。
# 試してみよう：
#   - ONLY_AXIOMS を True にして、公理だけで始めると、証明できる定理と調べる回数はどう変わるか
#   - GOALS に "2.13" を足すと？（報告では、1956 年のプログラムの 4 つの方法では 2.13 は証明できない。
#     このプログラムは形のそろえ方が違うため、結果が違うことがある。どこが違うか考えてみよう）

AXIOMS = {
    "1.2": "(p v p) > p",
    "1.3": "p > (q v p)",
    "1.4": "(p v q) > (q v p)",
    "1.5": "(p v (q v r)) > (q v (p v r))",
    "1.6": "(p > q) > ((r v p) > (r v q))",
}
# 報告に形が出てくる第 2 章の定理（> は「ならば」、v は「または」、- は「でない」）
THEOREMS = {
    "2.01": "(p > -p) > -p",
    "2.02": "p > (q > p)",
    "2.06": "(p > q) > ((q > r) > (p > r))",
    "2.07": "p > (p v p)",
    "2.12": "p > --p",
    "2.15": "(-p > q) > (-q > p)",
    "2.16": "(p > q) > (-q > -p)",
    "2.17": "(-q > -p) > (p > q)",
    "2.2": "p > (p v q)",
    "2.45": "-(p v q) > -p",
    "2.13": "p v ---p",
    "2.31": "(p v (q v r)) > ((p v q) v r)",
}
GOALS = ["2.01", "2.02", "2.06", "2.07", "2.12", "2.15", "2.16", "2.17", "2.2", "2.45"]
ONLY_AXIOMS = False
MAX_TRIES = 20000          # 調べる定理の数の上限（制限時間の代わり）

# ---------- 式を読む・書く ----------
def parse(s):
    toks = s.replace("(", " ( ").replace(")", " ) ").replace("-", " - ").split()
    pos = 0

def expr():
        nonlocal pos
        left = unary()
        if pos < len(toks) and toks[pos] in (">", "v"):
            op = toks[pos]
            pos += 1
            right = expr()
            return ("i" if op == ">" else "o", left, right)
        return left

def unary():
        nonlocal pos
        t = toks[pos]
        pos += 1
        if t == "-":
            return ("n", unary())
        if t == "(":
            e = expr()
            pos += 1  # ")"
            return e
        return ("v", t)
    return expr()

def show(e):
    if e[0] == "v":
        return e[1]
    if e[0] == "n":
        return "-" + (show(e[1]) if e[1][0] in ("v", "n") else f"({show(e[1])})")
    a, b = show(e[1]), show(e[2])
    a = a if e[1][0] in ("v", "n") else f"({a})"
    b = b if e[2][0] in ("v", "n") else f"({b})"
    return f"{a} {'>' if e[0] == 'i' else 'v'} {b}"

def canon(e):
    """「A ならば B」を「A でない、または B」に直して、形をそろえる。"""
    if e[0] == "v":
        return e
    if e[0] == "n":
        return ("n", canon(e[1]))
    if e[0] == "i":
        return ("o", ("n", canon(e[1])), canon(e[2]))
    return ("o", canon(e[1]), canon(e[2]))

def match(pat, e, sub):
    """定理 pat の文字に式を代入して e と一致させられるか調べる。できれば代入の辞書を返す。"""
    if pat[0] == "v":
        name = pat[1]
        if name in sub:
            return sub if sub[name] == e else None
        s2 = dict(sub)
        s2[name] = e
        return s2
    if pat[0] != e[0]:
        return None
    if pat[0] == "n":
        return match(pat[1], e[1], sub)
    s1 = match(pat[1], e[1], sub)
    return None if s1 is None else match(pat[2], e[2], s1)

def subst(e, sub):
    if e[0] == "v":
        return sub.get(e[1], e)
    if e[0] == "n":
        return ("n", subst(e[1], sub))
    return (e[0], subst(e[1], sub), subst(e[2], sub))

def letters(e, out=None):
    out = set() if out is None else out
    if e[0] == "v":
        out.add(e[1])
    else:
        for x in e[1:]:
            letters(x, out)
    return out

def as_implication(e):
    """形をそろえた式が「A ならば B」（= A でない、または B）なら (A, B) を返す。"""
    if e[0] == "o" and e[1][0] == "n":
        return e[1][1], e[2]
    return None

# ---------- ロジック・セオリスト（小さくした例） ----------
def prove(goal, known):
    tries = 0
    theorems = [(name, canon(parse(s))) for name, s in known]
    root = canon(goal)

def by_substitution(problem):
        nonlocal tries
        for name, t in theorems:
            tries += 1
            if match(t, problem, {}) is not None:
                return name
        return None

first = by_substitution(root)
    if first:
        return [f"代入法：{first} から"], tries
    queue = [(root, [])]
    seen = {root}
    while queue and tries < MAX_TRIES:
        problem, path = queue.pop(0)
        new = []
        for name, t in theorems:
            imp = as_implication(t)
            if not imp:
                continue
            a, b = imp
            tries += 1
            s = match(b, problem, {})                      # 切り離し法
            if s is not None and letters(a) <= set(s):
                new.append((subst(a, s), f"切り離し法：{name}"))
            pi = as_implication(problem)
            if pi:
                pa, pc = pi
                tries += 1
                s = match(a, pa, {})                       # 前向きのつなぎ
                if s is not None and letters(b) <= set(s):
                    new.append((("o", ("n", subst(b, s)), pc), f"前向きのつなぎ：{name}"))
                tries += 1
                s = match(b, pc, {})                       # 後ろ向きのつなぎ
                if s is not None and letters(a) <= set(s):
                    new.append((("o", ("n", pa), subst(a, s)), f"後ろ向きのつなぎ：{name}"))
        for sub_problem, how in new:
            if sub_problem in seen:
                continue
            seen.add(sub_problem)
            done = by_substitution(sub_problem)
            if done:
                return path + [how, f"代入法：{done} から"], tries
            queue.append((sub_problem, path + [how]))
    return None, tries

print("公理：", "  ".join(f"{k} {v}" for k, v in AXIOMS.items()))
print("（> は「ならば」、v は「または」、- は「でない」）\n")
proved = []
for i, g in enumerate(GOALS):
    known = list(AXIOMS.items())
    if ONLY_AXIOMS:
        known += [(k, THEOREMS[k]) for k in proved]            # 自分で証明できたものだけ
    else:
        known += [(k, THEOREMS[k]) for k in GOALS[:i]]         # 報告と同じ：前の定理は全部使ってよい
    steps, tries = prove(parse(THEOREMS[g]), known)
    if steps:
        proved.append(g)
        print(f"{g:<5} {THEOREMS[g]:<30} 見つけた（定理を {tries:,} 回 調べた）")
        print("      問題 → " + " → ".join(steps))
    else:
        print(f"{g:<5} {THEOREMS[g]:<30} 見つからない（{tries:,} 回 調べて打ち切り）")
print(f"\n{len(GOALS)} 個のうち {len(proved)} 個の証明を見つけた（1957 年の報告では、52 個のうち 38 個）")

051957・学ぶ機械

間違えた時だけ、重みを直す

例を見せるだけで、機械に識別方法を学習させられるか。

1957年、コーネル航空研究所の心理学者ローゼンブラットは、海軍研究局の支援での研究を始めた。神経細胞のつながりをまねた人工ニューロンで、入力（0か1）に重み（入力を重く見る度合い）をかけて足し、合計がしきい値以上なら1を出力する。

学習方法は単純だ。間違えた時だけ、正解の方向に重みを少し修正する。右の図で●と○を置いて「続けて学ぶ」を押すと、紫の線が回ったり平行に動いたりして、誤り（紫の輪）の数が変わっていく。同じコーネルの数学者ブロックは、分類する直線が存在するなら、この修正法で必ず見つかることを証明した。

ニューラルネットワークの歴史は、ここから始まる。直線1本で分類できない問題は5章、層を重ねる話は8章で扱う。

y＝1（w₁x₁ ＋w₂x₂ ≧ t）、それ以外は0。まちがえたらw ← w＋η（正解 − y）x、t ← t − η（正解 − y）

t: しきい値
η: 修正の大きさ（図では0.5）
紫の線: w₁x₁ ＋w₂x₂ がtと等しくなる境界線

1周ごとの誤りの数

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_perceptron_line.py

# u03 パーセプトロン：間違えた時だけ、重みを正解の向きに修正する
#
# どの出来事か：1957 年からのローゼンブラットのパーセプトロン（記録 perceptron_1957）。
#   入力に重みを掛けて足し合わせ、しきい値以上なら 1、そうでなければ 0 を出力するニューロンを使う。
#   答えを間違えた時だけ重みを直す学習のしかた（誤り訂正学習）で、例から識別のしかたを学習した。
#   同じコーネル大学の数学者ブロックは、分ける境界（直線や平面）が存在するなら、この修正手順で必ず見つかることを証明した。
# 仕組み：点 (x1, x2) を「●」か「○」に分類する。w1·x1 + w2·x2 がしきい値 t 以上なら「●」。
#   間違えたら：●なのに○と判定した → w に x を足し、t を 1 下げる。逆なら引いて、t を上げる。
#   w1·x1 + w2·x2 = t が「分ける線」。重みを変えると線が回転し、t を変えると線が平行移動する。
#   データ点はこのサイトが作った例（固定した乱数）。
# 試してみよう：
#   - OVERLAP を 1.5 にして 2 つの集まりを重ねると、間違いはいつまでも 0 にならないか
#   - 点を 1 つ、わざと反対のグループに入れると、どうなるか

import random

random.seed(1957)
OVERLAP = 0.0   # 2 つの集まりの重なり具合（0 なら直線 1 本で分離できる）
ROUNDS = 20     # すべてのデータを学習させる回数

def make_points(n=12):
    pts = []
    for _ in range(n):
        pts.append((random.uniform(0, 3), random.uniform(3.3 - OVERLAP, 6), 1))    # ●（左上の集まり）
        pts.append((random.uniform(3.3 - OVERLAP, 6), random.uniform(0, 3), 0))    # ○（右下の集まり）
    random.shuffle(pts)
    return pts

def answer(w1, w2, t, x1, x2):
    return 1 if w1 * x1 + w2 * x2 >= t else 0

points = make_points()
w1, w2, t = 0.0, 0.0, 0.0
for r in range(1, ROUNDS + 1):
    mistakes = 0
    for x1, x2, want in points:
        got = answer(w1, w2, t, x1, x2)
        if got != want:
            mistakes += 1
            d = want - got               # +1 か -1
            w1 += d * x1
            w2 += d * x2
            t -= d
    print(f"{r:2d} 周目：間違い {mistakes:2d} 回 " + "■" * mistakes + f"   線：{w1:+.1f}·x1 {w2:+.1f}·x2 = {t:+.1f}")
    if mistakes == 0:
        print("   間違いが 0 になったので、線が止まった")
        break

print("\n点と線の図（● ○ はデータ点、· はモデルが●と判定する場所、空白は○と判定する場所）")
grid = {(round(x1), round(x2)): ("●" if k else "○") for x1, x2, k in points}
for y in range(6, -1, -1):
    row = ""
    for x in range(0, 7):
        row += grid.get((x, y), "·" if answer(w1, w2, t, x, y) else "　")
    print("  " + row)

061957・予言

「10年以内に」4つの予言

1957年の研究者は、10年後をどう見通したのか。

1957年11月14日、ピッツバーグの学会の夕食会で、サイモンが、ニューウェルと共同で書いた講演をした（翌年、雑誌に掲載）。いまの計算機は、決まった解き方のない問題を人に似た方法で解き、経験から学習できる、とまとめたうえで、10年以内に4つのことが起きると予言した。

チェスの世界チャンピオンになる（〈訳〉）。大事な新しい数学の定理を見つけて証明する。批評家に認められる曲を書く。心理学の理論のほとんどが、プログラムの形をとる。続けて（訳）とも語った。

手がかりになる成果もあった。論理の定理を証明するプログラム、チェスの初歩を指す計算機、作曲するイリノイ大学のILLIACだ。右の図で年を進めると、答え合わせの年（1968年）と、その後に起きたことが表示される。

計算機が現役のチェスの世界チャンピオンに勝ったのは1997年、予言から約40年後だった。計算機が世界チャンピオンの称号そのものを獲得したことはない。

071958・批判と返答

答え合わせの日を、自分で書いた

予言を確かめられる形にするには、何が要るか。

講演が雑誌に載ると、ベルマンが手紙で批判した。2人の返答によると、予言は（訳）だという批判だった。1958年の返答で2人は、（訳）と書いた。

期限をつけて具体的にしたのは、ノストラダムスのような検証できない予言にしないためだ、と2人は説明した。ただ、確かめるには、何が・いつまでに起きるかに加えて、どうなったら当たりとするかの判定基準も要る。右の図で、期限と判定基準を外してみよう。チェスなら結果がはっきり出るが、定理・曲・心理学の予言は、期限が来ても人によって評価が分かれてしまう。

心理学の予言について2人は、プログラムが心理学の理論の有力な候補であることは（訳）とも返答に書いた。

チェスの判定基準（現役の世界チャンピオンとの対局に勝つ）は、このサイトが仮に設定したもの。

知ってるつもりよく言われる話：昔のAI研究者は根拠なく大きなことを言っていた
元の資料では：当時すでに批判があり、言った本人たちは検証できるように期限をつけたと説明して、答え合わせの日（1968年1月1日ごろ）まで自分で指定していた。

081958・海軍の実演

カードの印は、右か左か

新聞が大きな期待を書いた日、機械は実際に何をしたのか。

1958年7月、アメリカ海軍がワシントンで記者に実演を見せた。気象局（天気の役所）の大型コンピュータIBM 704でパーセプトロンのシミュレーションを動かし、カードの印が右か左かを、約50回の試行で識別できるようになった。専用の機械は、まだ製作前だった。

翌日のニューヨーク・タイムズの見出しは。記事は、海軍はこの“胚”が、いずれ（訳）ようになると期待している、と報じた。

右の図は、その日の実演を小さく再現した例だ（カードの大きさや印はこのサイトが決めた）。「続けて50枚」を押すと、重みのマップで、右半分は右に、左半分は左に票を入れるパターンが育つ。機械が学習したのは、どのマスがどちらに票を入れるかだけ。右や左という言葉は知らない。

知ってるつもりよく言われる話：ローゼンブラットは『パーセプトロンは歩き、話し、意識を持つ』と言った
元の資料では：記事でそう期待したと書かれたのは。本人も（訳）になると話したが、1961年の報告では新聞の扱いを（訳）のようだったと批判した。

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_perceptron_cards.py

# u03 パーセプトロン：カードの印は右か左か（1958 年の実演を小さく再現）
#
# どの出来事か：1958 年 7 月、アメリカ海軍が記者に公開した実演（記録 perceptron_navy_demo_1958）。
#   ふつうのコンピュータ IBM 704 の上で、ローゼンブラットのパーセプトロンが、カードの印が右か左かを
#   50 回ほどの試行で識別できるようになった。
# 仕組み：マス目ごとに「重み」があり、印のあるマスの重みを足して、正なら「右」、負なら「左」と判定する。
#   間違えた時だけ、正解の方向に重みを更新する（パーセプトロンの学習規則）。
# 試してみよう：
#   - TRIALS を 20 にすると、まだ誤りが残るか？
#   - MARK を 1 にすると（印が小さいと）、学習に何枚かかるか？
#   - 最後の「重みの地図」は何を表しているか？（コンピュータは「右と左」という言葉を知らない）

import random

random.seed(1958)
SIZE = 10      # カードの大きさ（10×10 のマス目）
MARK = 3       # 印の大きさ（3×3 のマス目）
TRIALS = 60    # 学習のために見せるカードの枚数

def make_card():
    """印を左半分か右半分のどちらかに置いたカードを 1 枚作る。"""
    side = random.choice(["左", "右"])
    if side == "左":
        x0 = random.randint(0, SIZE // 2 - MARK)
    else:
        x0 = random.randint(SIZE // 2, SIZE - MARK)
    y0 = random.randint(0, SIZE - MARK)
    pixels = [0] * (SIZE * SIZE)
    for y in range(y0, y0 + MARK):
        for x in range(x0, x0 + MARK):
            pixels[y * SIZE + x] = 1
    answer = 1 if side == "右" else -1
    return pixels, answer

weights = [0] * (SIZE * SIZE)   # 重みの初期値はすべて 0
bias = 0

def guess(pixels):
    total = bias + sum(w * p for w, p in zip(weights, pixels))
    return 1 if total > 0 else -1

mistakes = []
for trial in range(1, TRIALS + 1):
    pixels, answer = make_card()
    if guess(pixels) != answer:
        # 間違えた時だけ更新する：印のあるマスの重みを、正解の方向に 1 動かす
        for i, p in enumerate(pixels):
            weights[i] += answer * p
        bias += answer
        mistakes.append(trial)

print("間違えたカードの番号:", mistakes)
for start in range(1, TRIALS + 1, 10):
    n = sum(1 for m in mistakes if start <= m < start + 10)
    print(f"  {start:3d}〜{start + 9:3d} 枚目：誤り {n} 回 " + "■" * n)

# 学習後に、新しいテストデータ 200 枚で試す
correct = 0
for _ in range(200):
    pixels, answer = make_card()
    correct += guess(pixels) == answer
print(f"新しいカード 200 枚でテストすると、正解したのは {correct} 枚")

# 重みの可視化（＋は「右」方向、－は「左」方向、・は 0）
print("重みの地図:")
for y in range(SIZE):
    row = ""
    for x in range(SIZE):
        w = weights[y * SIZE + x]
        row += "＋" if w > 0 else ("－" if w < 0 else "・")
    print("  " + row)

091958・LISP

かっこの入れ子で、式を式のまま扱う

数ではなく、記号の式そのものを計算するには？

1958年の秋、マッカーシーとミンスキーはMITでを始めた。計画書は書かず、何が必要かと聞かれて、部屋1つ、プログラマー2人、秘書1人、カードに穴をあける機械1台と答えたという。同じ秋、記号の並びを扱うプログラミング言語LISP（リスト処理）を作り始めた。

LISPでは、(TIMES X (PLUS X A) Y) のように、かっこの入れ子で式を書く。最初の語が何をするかを表し、残りが対象を表す。基本の働きは、先頭を取るcar、残りを取るcdr、先頭につなぐconsなど、ほんの少しだ。1960年の論文は、これと条件の分岐、自分を呼び出す関数だけで、式の微分を書いてみせた。

右の図で「X(X+A)Y・論文の例」を選び、「1・0を整理（サイトの追加）」を外して「Xで微分（DIFF）」を押すと、論文と同じ答えが木で出る。1を表すONEや、0を表すZEROがそのまま残る。LISPの仲間の言語は、その後長くAI研究の中心で使われた。

d(u·v·w)/dX＝u′·v·w＋u·v′·w＋u·v·w′

′: Xで微分したもの。DIFFはこの形を、かっこの入れ子のまま作る

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_mini_lisp.py

# u03 小さな LISP：かっこの入れ子の式を、式のまま微分する
#
# どの出来事か：1958 年秋から MIT の AI グループが開発したプログラミング言語 LISP（記録 lisp_1958・mit_ai_project_1958）。
#   マッカーシーの 1960 年の論文は、記号式（S 式）を扱う基本操作 car・cdr・cons・atom・eq と、
#   条件分岐、再帰関数だけで、数式の微分を計算する例を示した。
# 仕組み：(TIMES X (PLUS X A) Y) は X(X+A)Y のこと。最初の要素が「何をするか」、残りが「何に」を表す。
#   car はリストの先頭、cdr は先頭を除いた残り、cons は先頭に要素を追加する操作。
#   DIFF（微分）は論文の式をそのまま LISP で書いたもの。MAPLIST は、リストの残りを 1 つずつ関数に渡す。
#   論文と同じく、計算結果の整理は行わない（ONE は 1、ZERO は 0 のこと）。
#   ※ LISP を解釈して実行する部分（eval）は、このサイトが Python で書いた小さな例。
# 試してみよう：
#   - EXPR を (PLUS X (TIMES X X)) に変えてみる（X + X·X の微分）
#   - DIFF に「ZERO をかける項は消す」整理を足すには、どこを変えればよいか

EXPR = "(TIMES X (PLUS X A) Y)"

class Cons:
    def __init__(self, car, cdr):
        self.car, self.cdr = car, cdr

def read(text):
    toks = text.replace("(", " ( ").replace(")", " ) ").split()

def walk(i):
        if toks[i] != "(":
            return (None if toks[i] == "NIL" else toks[i]), i + 1
        items, i = [], i + 1
        while toks[i] != ")":
            x, i = walk(i)
            items.append(x)
        lst = None
        for x in reversed(items):
            lst = Cons(x, lst)
        return lst, i + 1
    return walk(0)[0]

def show(x):
    if x is None:
        return "NIL"
    if isinstance(x, str):
        return x
    parts = []
    while isinstance(x, Cons):
        parts.append(show(x.car))
        x = x.cdr
    return "(" + " ".join(parts) + ")"

BUILTIN = {
    "CAR": lambda x: x.car,
    "CDR": lambda x: x.cdr,
    "CONS": lambda a, b: Cons(a, b),
    "ATOM": lambda x: "T" if not isinstance(x, Cons) else None,
    "EQ": lambda a, b: "T" if (a == b if isinstance(a, str) or a is None else a is b) else None,
    "NULL": lambda x: "T" if x is None else None,
    "NOT": lambda x: "T" if x is None else None,
}
DEFS = {}

def evaluate(e, env):
    if e is None or e == "T":
        return e
    if isinstance(e, str):
        return env[e] if e in env else DEFS.get(e, BUILTIN.get(e))
    head = e.car
    if head == "QUOTE":
        return e.cdr.car
    if head == "COND":
        clause = e.cdr
        while clause is not None:
            if evaluate(clause.car.car, env) is not None:
                return evaluate(clause.car.cdr.car, env)
            clause = clause.cdr
        return None
    if head == "LAMBDA":
        return ("closure", e.cdr.car, e.cdr.cdr.car, env)
    fn = evaluate(head, env)
    args = []
    a = e.cdr
    while a is not None:
        args.append(evaluate(a.car, env))
        a = a.cdr
    if callable(fn):
        return fn(*args)
    _, params, body, fenv = fn
    new = dict(fenv)
    p = params
    for v in args:
        new[p.car] = v
        p = p.cdr
    return evaluate(body, new)

def define(name, text):
    DEFS[name] = evaluate(read(text), {})

define("MAPLIST", "(LAMBDA (X F) (COND ((NULL X) NIL) (T (CONS (F X) (MAPLIST (CDR X) F)))))")
define("DIFF", """(LAMBDA (Y X) (COND
  ((ATOM Y) (COND ((EQ Y X) (QUOTE ONE)) (T (QUOTE ZERO))))
  ((EQ (CAR Y) (QUOTE PLUS)) (CONS (QUOTE PLUS) (MAPLIST (CDR Y) (LAMBDA (Z) (DIFF (CAR Z) X)))))
  ((EQ (CAR Y) (QUOTE TIMES)) (CONS (QUOTE PLUS) (MAPLIST (CDR Y) (LAMBDA (Z)
      (CONS (QUOTE TIMES) (MAPLIST (CDR Y) (LAMBDA (W)
          (COND ((NOT (EQ Z W)) (CAR W)) (T (DIFF (CAR W) X)))))))))))))""")

e = read(EXPR)
print("式           ", show(e))
print("car（先頭）  ", show(evaluate(read("(CAR (QUOTE " + EXPR + "))"), {})))
print("cdr（残り）  ", show(evaluate(read("(CDR (QUOTE " + EXPR + "))"), {})))
print("cons で A を前に", show(evaluate(read("(CONS (QUOTE A) (QUOTE " + EXPR + "))"), {})))
print()
d = evaluate(read("(DIFF (QUOTE " + EXPR + ") (QUOTE X))"), {})
print("X で微分すると")
print("  ", show(d))
print("（1960 年の論文の答えと同じ形：積の微分は、1 つずつ微分した項を足し合わせる）")

101958・常識

空港へ行くため最初にする行動を導く

事実を文で書いておけば、機械はそこから行動を導けるか。

1958年11月、イギリスの国立物理学研究所での国際会議が開かれた。マッカーシーはそこでを発表した。事実や助言を論理式で書き、そこから推論して「〜せよ」という結論が出たら実行する構想だ（アドバイス・テイカー）。

論文の例は、家の机にいる私が空港へ行く問題だ。at(I, desk)（私は机にいる）、at(car, home)（車は家にある）、walkable(home)（家の中は歩ける）、drivable(county)（郡の中は車で行ける）など17の前提から8つの結論を順に導き、最後にdo(go(desk, car, walking))、つまり、まず車まで歩く、が出る。

右の図で「次を導く」を押してみよう。前提を1つ外すと、計画が見つからなくなる。

論文は、17の前提をどう集めるか、どう導くかについては完全には答えられない、と書いている。図の導く順番は、論文の結論の並びに合わせた。

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_advice_taker.py

# u03 アドバイス・テイカー：「空港へ行きたい」から、最初にすることを導く
#
# どの出来事か：1958 年 11 月、イギリスの会議でマッカーシーが出した「常識を持つプログラム」の提案
#   （記録 mtp_symposium_1958・lisp_1958）。事実や助言を文の形で書いておき、そこから結論を導いて、
#   「〜せよ」という結論が出たらそれを実行する。論文の例は「机の前にいる私が、空港へ行く」。
# 仕組み：前提（論文の 17 個のうち、この例に使うもの）を、そのまま Python のデータにした。
#   at(x, y)＝x は y にある。walkable(家)＝家の中は歩ける。drivable(郡)＝郡の中は車で行ける。
#   1. 歩く・車の規則から「この状況なら、この行き方ができる」を作る。
#   2. 「行ったら、そこにいる」と組み合わせて、canachult（その状況で、その行動をすれば、次の状況になる）を作る。
#   3. 2 つの canachult をつないで机から空港までの計画を作り、want（望み）と一致したら、最初の行動を do にする。
#   ※ 論文は、前提の集め方や導き方について、この論文では完全には答えられないと書いている。
#     ここの導き方（順番や候補の作り方）は、このサイトが決めたもの。
# 試してみよう：
#   - FACTS から ("at", "car", "home") を消すと（車が家にないと）、計画は見つかるか
#   - ("drivable", "county") を消すとどうなるか

FACTS = [
    ("at", "I", "desk"), ("at", "desk", "home"), ("at", "car", "home"),
    ("at", "home", "county"), ("at", "airport", "county"),
    ("walkable", "home"), ("drivable", "county"),
]
WANT = ("at", "I", "airport")

# (6) at の推移：at(x,y), at(y,z) → at(x,z)。私（I）は動くので、物の場所だけでつなぐ
at = {(f[1], f[2]) for f in FACTS if f[0] == "at" and f[1] != "I"}
changed = True
while changed:
    changed = False
    for (x, y) in list(at):
        for (y2, z) in list(at):
            if y == y2 and (x, z) not in at:
                at.add((x, z))
                changed = True
places = {p for pair in at for p in pair}
now = next(f[2] for f in FACTS if f[:2] == ("at", "I"))

can = []   # (状況, 行動)
for f in FACTS:
    if f[0] == "walkable":                      # (9)
        x = f[1]
        for y in sorted(places):
            for z in sorted(places):
                if y != z and (y, x) in at and (z, x) in at:
                    can.append((("at", "I", y), ("go", y, z, "walking")))
    if f[0] == "drivable":                      # (10)
        x = f[1]
        for y in sorted(places):
            for z in sorted(places):
                if y != z and (y, x) in at and (z, x) in at and ("car", y) in at:
                    can.append((("at", "I", "car"), ("go", y, z, "driving")))

def after(action):                              # (13) did(go(x,y,z)) → at(I, y)
    return ("at", "I", action[2])

chult = [(s, a, after(a)) for s, a in can]      # (15)

def fmt(t):
    return t[0] + "(" + ", ".join(fmt(x) if isinstance(x, tuple) else x for x in t[1:]) + ")"

plan = None
for s1, a1, r1 in chult:                        # (16) 2 つをつなぐ
    for s2, a2, r2 in chult:
        if r1 == s2 and s1 == ("at", "I", now) and r2 == WANT:
            plan = (s1, a1, r1, a2, r2)
            break
    if plan:
        break

print("前提：", "  ".join(fmt(f) for f in FACTS), "  want(" + fmt(WANT) + ")")
print(f"（at を推移でつなぐと {len(at)} 個。行き方の候補 {len(can)} 個を作った）\n")
if plan:
    s1, a1, r1, a2, r2 = plan
    steps = [
        f"{fmt(s1)} → can({fmt(a1)})",
        f"{fmt(r1)} → can({fmt(a2)})",
        f"did({fmt(a1)}) → {fmt(r1)}",
        f"did({fmt(a2)}) → {fmt(r2)}",
        f"canachult({fmt(s1)}, {fmt(a1)}, {fmt(r1)})",
        f"canachult({fmt(r1)}, {fmt(a2)}, {fmt(r2)})",
        f"canachult({fmt(s1)}, prog({fmt(a1)}, {fmt(a2)}), {fmt(r2)})",
        f"do({fmt(a1)})",
    ]
    for i, s in enumerate(steps, 1):
        print(f"{i}. {s}")
    print("\n→ 最初にすることは、机から車まで歩くこと（論文の 8 つの結論と同じ順）")
else:
    print("机から空港までの計画が見つからない。どの前提が足りないか考えてみよう")

111958・パターン認識

悪魔たちの叫び声で文字を認識する

文字を認識する仕組みを、たくさんの小さな部品に分けられるか。

同じ会議で、セルフリッジは（悪魔が全部集まる場所という意味）という仕組みを発表した。一番下のデータの悪魔は、それぞれ文字の一部（横棒、縦棒、丸みなど）を探し、見つかった確かさに応じて大声で叫ぶ。上の認識の悪魔は、自分の文字に合う叫び声を集めて叫び、一番上の決める悪魔が、最も大きな声の文字を答えにする。

学習の方法も提案した。悪魔のメガホンの音量を外から少しずつ変えて、成績が最も上がる調整を選び、それを繰り返す（山登り法）。右の図で「続けて直す」を押すと、音量0から正解率が上がっていく。

特徴を拾い出し、重みをかけて組み合わせる構造は、パーセプトロンや、のちのニューラルネットワークと同じ仕組みだ。

認識の悪魔kの声＝Σ_i 音量_k,i × データの悪魔iの声

音量_k,i: 悪魔kが悪魔iの声を聞く重み（学習する部分）
答え: 声が最も大きいk

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_pandemonium.py

# u03 パンデモニウム：小さな悪魔たちの叫び声で、文字を識別する
#
# どの出来事か：1958年11月、イギリスの会議でセルフリッジが発表した「パンデモニウム」（記録 mtp_symposium_1958）。
#   最下層の「データの悪魔」は、文字の特徴（横棒・縦棒など）を探し、見つかった確かさに応じた大きさの声で叫ぶ。
#   中間の「認識の悪魔」は、自分の文字に合う叫び声の組み合わせを聞いて叫び、最上部の「決める悪魔」が、
#   いちばん大きな声の文字を答えにする。メガホンの音量は外部から少しずつ調整し、
#   成績が最も上がる変更を選ぶ（山登り法）。※説明は Nilsson（2010）による。
#   ここでは成績の点に「全部の声のうち、正しい字の声がしめる割合」を使う（このサイトの決め方）。
# 仕組み：5×5の文字（このサイトが作った例の A・E・L・O・T）に、ノイズ（マスの白黒反転）を加えて見せる。
#   データの悪魔 8 匹（7 匹が文字の部分を探し、1 匹はいつも同じ大きさの声）→ 認識の悪魔 5 匹（文字ごと）→ 決める悪魔。
#   音量の初期値はすべて 0。
# 試してみよう：
#   - NOISE を 0.2 にすると、学習後の成績はどれだけ下がるか
#   - データの悪魔を 1 匹（たとえば「まん中の縦棒」）消すと、どの文字を間違えやすくなるか

import math
import random

random.seed(1958)
NOISE = 0.08      # 1マスの白黒が反転する割合
ROUNDS = 60       # 音量を調整する最大反復回数
STEP = 1.0        # 1回の調整で音量を変更する幅

LETTERS = {
    "A": [".###.", "#...#", "#####", "#...#", "#...#"],
    "E": ["#####", "#....", "####.", "#....", "#####"],
    "L": ["#....", "#....", "#....", "#....", "#####"],
    "O": [".###.", "#...#", "#...#", "#...#", ".###."],
    "T": ["#####", "..#..", "..#..", "..#..", "..#.."],
}
DEMONS = ["上の横棒", "まん中の横棒", "下の横棒", "左の縦棒", "右の縦棒", "まん中の縦棒", "白い角", "いつも"]

def shouts(img):
    """データの悪魔たちの声の大きさ（0〜1）。img は 5×5 の 0/1 配列。"""
    row = lambda r: sum(img[r]) / 5
    col = lambda c: sum(img[r][c] for r in range(5)) / 5
    return [row(0), row(2), row(4), col(0), col(4),
            sum(img[r][2] for r in range(1, 5)) / 4,
            sum(1 - img[r][c] for r, c in ((0, 0), (0, 4), (4, 0), (4, 4))) / 4,
            1.0]   # 「いつも」＝常に一定の声で叫ぶ悪魔（文字ごとの基準値）

def noisy(letter):
    return [[(1 if ch == "#" else 0) ^ (random.random() < NOISE) for ch in rowtxt] for rowtxt in LETTERS[letter]]

def decide(vol, s):
    loud = {k: sum(v * x for v, x in zip(vol[k], s)) for k in LETTERS}
    return max(loud, key=loud.get), loud

def score(vol, data):
    return sum(decide(vol, s)[0] == k for k, s in data) / len(data)

def grade(vol, data):
    """成績の点：すべての声のうち、正しい文字の悪魔の声が占める割合（対数）の平均。0 に近いほどよい。"""
    total = 0
    for k, s in data:
        _, loud = decide(vol, s)
        top = max(loud.values())
        total += (loud[k] - top) - math.log(sum(math.exp(v - top) for v in loud.values()))
    return total / len(data)

train = [(k, shouts(noisy(k))) for k in LETTERS for _ in range(8)]
test = [(k, shouts(noisy(k))) for k in LETTERS for _ in range(40)]
vol = {k: [0.0 for _ in DEMONS] for k in LETTERS}   # 音量の初期値はすべて 0（どの悪魔の声も聞かない）

print(f"初め：訓練データで {score(vol, train):.0%}、テストデータで {score(vol, test):.0%}")
for r in range(1, ROUNDS + 1):
    best, best_s = None, grade(vol, train)
    for k in LETTERS:                       # 各音量を少し増減させてすべて試す
        for i in range(len(DEMONS)):
            for d in (STEP, -STEP):
                vol[k][i] += d
                s = grade(vol, train)
                vol[k][i] -= d
                if s > best_s:
                    best, best_s = (k, i, d), s
    if best is None:
        print(f"{r:2d} 回目：どの変更でもスコアが上がらないため終了（山の頂上に到達）")
        break
    k, i, d = best
    vol[k][i] += d
    if r <= 3 or r % 15 == 0:
        print(f"{r:2d} 回目：「{k}」の悪魔が「{DEMONS[i]}」を聞く音量を{'上げ' if d > 0 else '下げ'}る → 点 {best_s:.2f}、訓練データで {score(vol, train):.0%} 正解")

print(f"\n学習後：テストデータ（{len(test)} 個）を {score(vol, test):.0%} 正しく識別")
k, s = test[3]
ans, loud = decide(vol, s)
print(f"\n例：本当は「{k}」の文字 → データの悪魔の声 " + " ".join(f"{d}{x:.1f}" for d, x in zip(DEMONS, s)))
print("   認識の悪魔の声 " + "  ".join(f"{c}:{v:+.1f}" for c, v in loud.items()) + f" → 決める悪魔の答え「{ans}」")

121959・GPS

目標とのを小さくする手を選ぶ

どんな問題にも使える解き方は、作れるのか。

ニューウェル、ショー、サイモンは、ロジック・セオリストをもとにを作り、1959年6月のパリの会議の予稿として報告した（報告の日付は1958年12月30日）。一般と名がついたのは、問題の中身（論理・代数・三角の公式など）と解き方を切り離して作ったからだ。

解き方の中心は、目的と手段の分析だ。現在の状態と目標を比べて違いを見つけ、その違いを減らす手を選ぶ。手を使う条件がそろっていなければ、その条件を満たすことを新しい小さな目標にする。こうして目標の中に目標が作られ、同じ手順が何段にも重なって使われる。

右の図の最初の問題は、このサイトが作った、バタートーストを作る問題だ。どの手がどの違いを減らすかという表を入れ替えれば、同じ解き方が別の問題にも使える。

報告の目的には、大学生が論理の問題を声に出して考えながら解いた記録に、プログラムのふるまいを近づけることもあった。報告で示された例は、記号論理・初歩の代数・三角の公式だった。

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_gps_means_ends.py

# u03 GPS の「目的と手段の分析」：現在と目標の「ちがい」を見つけ、それを小さくする操作を選ぶ
#
# どの出来事か：1958 年 12 月 30 日付の報告、ニューウェル、ショー、サイモンの GPS（一般問題解決器。記録 gps_1959）。
#   ロジック・セオリストから生まれ、「問題の中身」（論理・代数・三角の公式 など）と「解き方」を分けて作った。
#   解き方の中心が「目的と手段の分析」：現在の状態と目標を比較して違いを見つけ、違いを減らす操作を選ぶ。
#   操作が使えない時は、「その手を使える形にする」ことを新しい小さな目標にする（目標の中に目標ができる）。
# 仕組み：問題の内容は、このサイトが作った例「朝ごはんのバタートーストを作る」。
#   操作ごとに「使う条件」「できること」を書いた表（問題の中身）と、解き方（transform・apply）を分けてある。
#   表を取りかえれば、同じ解き方がほかの問題にも使える。これが GPS の「一般」の意味。
# 試してみよう：
#   - START に "冷蔵庫が開いている" を足すと、操作の数はどう変わるか
#   - OPERATORS を別の問題（たとえば、学校へ行く）に書きかえて、同じ transform で解いてみる

OPERATORS = [   # (操作の名前, 使う条件, できること, なくなること)
    ("冷蔵庫を開ける", [], ["冷蔵庫が開いている"], []),
    ("バターを出す", ["冷蔵庫が開いている"], ["バターが出ている"], []),
    ("パンの袋を開ける", [], ["袋が開いている"], []),
    ("パンを出す", ["袋が開いている"], ["パンを持っている"], []),
    ("パンをトースターに入れる", ["パンを持っている"], ["パンがトースターの中"], ["パンを持っている"]),
    ("パンを焼く", ["パンがトースターの中"], ["パンが焼けている"], []),
    ("バターをぬる", ["パンが焼けている", "バターが出ている"], ["バタートーストができた"], []),
]
START = []
GOAL = ["バタートーストができた"]
steps = []

def transform(state, goal, depth=0):
    """現在の state を、goal を満たす状態にする（GPS の目標の型 1）。"""
    pad = "  " * depth
    for want in goal:
        if want in state:
            continue
        print(f"{pad}ちがい：「{want}」がまだ無い")
        op = next((o for o in OPERATORS if want in o[2]), None)   # 違いを減らす操作を表から探す
        if op is None:
            print(f"{pad}  → 減らす操作が無い。あきらめる")
            return None
        print(f"{pad}  → 減らす操作：「{op[0]}」")
        state = apply(state, op, depth + 1)
        if state is None:
            return None
    return state

def apply(state, op, depth):
    """操作 op を適用する（GPS の目標の型 2）。条件が足りなければ、まずそれを目標にする。"""
    name, need, add, remove = op
    missing = [c for c in need if c not in state]
    if missing:
        print("  " * depth + f"「{name}」を使う条件が足りない → 小さな目標：" + "、".join(missing))
        state = transform(state, missing, depth + 1)
        if state is None:
            return None
    steps.append(name)
    print("  " * depth + f"★ 操作 {len(steps)}：{name}")
    return [s for s in state if s not in remove] + [a for a in add if a not in state]

print("目標：", "、".join(GOAL), "\n")
final = transform(list(START), GOAL)
print("\nできあがり：" if final else "\n解けなかった", "→".join(steps))
print(f"使った操作の数 {len(steps)}")

131959・日本

ワレガオンガクヲコノム

そのころ日本では、どんな「考える機械」が作られていたか。

1958年の夏ごろ、電気試験所で、英語を日本語に翻訳する専用の計算機「やまと」の計画が始まった。辞書を納める大きな記憶装置を持つ計算機が手元になく、トランジスタ計算機ETL Mark IVの回路を使って専用機を作った。予算は600万円、記憶装置は82万ビットの磁気ドラムだった。1959年2月、I like musicと穴をあけた紙テープを入れると、と打ち出した。

日本語入力（漢字や単語の区切り）の難しさを避けるため、英語から日本語への翻訳を選んだ。それでも、動詞を文末に回し、前置詞を動かし、ガやヲなどの助詞を補う必要があった。代名詞はIをワレ、youをナレ、heをカレにした。右の図で、翻訳の手順を1段階ずつ進めてみよう。

計画を指示した和田弘は、最初の訳を打ち始めるまでの13秒を、とても長く感じたと回想している。成果は1959年6月、パリの第1回国際情報処理会議で発表された。

図の辞書と規則は、代名詞の訳を除き、このサイトが作った例。パリで示した I have some eggs in my hand. を、やまとがどう訳したかは資料にない。

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_yamato_translate.py

# u03 「やまと」のように訳す：英文を、辞書と並べ替えの規則でカタカナの日本語に
#
# どの出来事か：1959年、電気試験所の英日翻訳専用機「やまと」（記録 etl_yamato_mt_1959）。
#   最初に訳した「I like music.」は「ワレガ オンガクヲ コノム」。訳を打ち始めるまで13秒かかった。
#   和田弘の回想によると、英文和訳には動詞を文末に置くこと、前置詞を動かすこと、
#   格助詞（ガ・ヲなど）を補うことなどが必要だった。代名詞 I, you, he, she, it, this, that, who は
#   ワレ、ナレ、カレ、サレ、ソレ、コレ、アレ、タレにした（本人は「ヤマトコトバ」と呼んだ）。
# 仕組み：1語ずつ辞書を引く → 主語・動詞・目的語・前置詞のまとまりに分ける → 日本語の順に並べ替える →
#   助詞を補ってカタカナで出力する。辞書と規則は、代名詞を除き、このサイトが作った小さな例。
#   2番目の文は1959年6月のパリの会議で示された文。やまとの実際の訳は資料にないため、ここの訳はこのサイトの規則による。
# 試してみよう：
#   - SENTENCES に "She likes the moon." を足す（辞書に moon を足す必要がある）
#   - 「I like music very much.」のような文は、この規則でどうなるか

PRONOUN = {"i": "ワレ", "you": "ナレ", "he": "カレ", "she": "サレ", "it": "ソレ", "this": "コレ", "that": "アレ", "who": "タレ"}
POSSESSIVE = {"my": "ワレノ", "your": "ナレノ", "his": "カレノ", "her": "サレノ"}
NOUN = {"music": "オンガク", "egg": "タマゴ", "hand": "テ", "book": "ホン", "moon": "ツキ"}
VERB = {"like": "コノム", "have": "モツ", "read": "ヨム", "see": "ミル"}
PREP = {"in": "ニ", "on": "ノウエニ", "with": "ト"}
DET = {"some": "イクツカノ", "the": "", "a": ""}
SENTENCES = ["I like music.", "I have some eggs in my hand.", "He likes music.", "You read a book."]

def base(word):
    """名詞・動詞の語尾（-s）を取り除き、辞書の形に戻す。"""
    if word in NOUN or word in VERB:
        return word
    if word.endswith("s") and (word[:-1] in NOUN or word[:-1] in VERB):
        return word[:-1]
    return word

def translate(sentence, show=True):
    words = [base(w) for w in sentence.lower().rstrip(".").split()]
    if show:
        print("1. 単語に分けて、語尾を取り除く：", words)
    subj, verb = words[0], words[1]
    rest = words[2:]
    obj, phrases, cur = [], [], None
    for w in rest:                                   # 目的語と、前置詞のまとまりに分ける
        if w in PREP:
            cur = [w]
            phrases.append(cur)
        elif cur is not None:
            cur.append(w)
        else:
            obj.append(w)
    if show:
        print(f"2. 文の役割を決める：主語 {subj} ／ 動詞 {verb} ／ 目的語 {obj} ／ 前置詞のまとまり {phrases}")

def noun_phrase(ws):
        parts = [DET.get(w, "") + POSSESSIVE.get(w, "") + NOUN.get(w, "") + PRONOUN.get(w, "") for w in ws]
        return " ".join(p for p in parts if p)
    jp = [PRONOUN.get(subj, NOUN.get(subj, subj)) + "ガ"]            # 主語＋ガ
    for p in phrases:                                                # 前置詞は名詞の後ろへ
        jp.append(noun_phrase(p[1:]) + PREP[p[0]])
    if obj:
        jp.append(noun_phrase(obj) + "ヲ")                            # 目的語＋ヲ
    jp.append(VERB.get(verb, verb))                                  # 動詞は文末へ
    if show:
        print("3. 日本語の語順に並べて、助詞を補う：", jp)
    return " ".join(jp)

for s in SENTENCES:
    print(f"【{s}】")
    print("   → " + translate(s) + "\n")
print("（やまとは、最初の訳を打ち始めるまで 13 秒かかった。この Python は 1 秒もかからない）")

141959・機械学習

点数の付け方を、自分で直す

プログラムは、書いた本人より強くなれるか。

IBMのサミュエルは、チェッカー（8×8の盤で、こまを飛び越して取り合うゲーム）で、コンピュータが経験から学習する研究を続けた。学習する版は1956年2月24日にテレビで実演された。1959年の論文の要約には、8〜10時間の対局で、プログラムを書いた本人よりうまく指せるようになる、と書かれている。

局面の点数は、こまの差・動ける手の多さ・中央をとっているかなどの特徴に、重みをかけて足したものだ。数手先まで読み、自分は大きい方、相手は小さい方を選ぶとして点数を上へ運ぶ（ミニマックス）。学習法の1つは、読む前の点数が、読んで運んだ点数に近づくように重みを直すこと。右の図で「学ぶ」を押してみよう。

解き方を全部書かず、例や経験から学ばせるのが機械学習だ。

w ← w＋η（運んだ点数 − 読む前の点数）× 特徴

w: 重み
η: 修正の大きさ
点数: 特徴 × 重みの合計（図の数値はこのサイトが作った例）

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_samuel_weights.py

# u03 サミュエルの学習法：先を読んだ評価値に近づくように、重みを自分で直す
#
# どの出来事か：1959年、IBMのサミュエルの論文「チェッカーのゲームを使った、機械が学ぶことの研究」（記録 samuel_checkers_1959）。
#   盤面から駒の数の差・動ける手の多さ・中央の支配など「特徴」の数値を集め、重みをかけて足し合わせて局面の評価値にした。
#   数手先まで読み、自分は最大、相手は最小を選ぶミニマックス法で手を決めた。
#   学習方法の 1 つは、先読み前の評価値が先読み後の評価値に近づくように重みを直すこと（説明は Nilsson 2010 による）。
# 仕組み：チェッカーは大きいので、三目並べで同じ仕組みを動かす（ゲームと特徴はこのサイトが作った例）。
#   特徴：自分があと1つでそろう列・相手があと1つでそろう列・自分だけが置いている列・中央・角。
#   自己対戦しながら、1手ごとに「読む前の点数」を「2 手先まで読んだ点数」に少し近づける。
# 試してみよう：
#   - GAMES を 0 にして学習させないと、ランダムに打つ相手への成績はどうなるか
#   - RATE を大きくすると、重みはどう変化するか

import random

random.seed(1959)
GAMES = 300       # 学習用の自己対戦の回数
RATE = 0.01       # 1回に重みを更新する大きさ（学習率）
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
NAMES = ["あと 1 つでそろう（自分）", "あと 1 つでそろう（相手）", "自分だけの列", "まん中", "角"]
w = [0.0] * len(NAMES)      # 重みの初期値（最初はどの特徴も重視しない）

def winner(b):
    for i, j, k in LINES:
        if b[i] != "." and b[i] == b[j] == b[k]:
            return b[i]
    return None

def features(b, me):
    you = "O" if me == "X" else "X"
    f = [0, 0, 0, 0, 0]
    for line in LINES:
        cells = [b[i] for i in line]
        if cells.count(me) == 2 and cells.count(".") == 1:
            f[0] += 1
        if cells.count(you) == 2 and cells.count(".") == 1:
            f[1] += 1
        if cells.count(me) == 1 and cells.count(".") == 2:
            f[2] += 1
    f[3] = (b[4] == me) - (b[4] == you)
    f[4] = sum((b[i] == me) - (b[i] == you) for i in (0, 2, 6, 8))
    return f

def static(b, me):
    """先読み前の評価値：特徴 × 重み の合計。勝敗が決まっていれば ±10。"""
    win = winner(b)
    if win:
        return 10 if win == me else -10
    if "." not in b:
        return 0
    return sum(wi * fi for wi, fi in zip(w, features(b, me)))

def moves(b):
    return [i for i, c in enumerate(b) if c == "."]

def search(b, me, turn, depth):
    """ミニマックス法：自分の番は最大、相手の番は最小を選んで、評価値を上の局面へ運ぶ。"""
    if depth == 0 or winner(b) or "." not in b:
        return static(b, me), None
    best = None
    for m in moves(b):
        nb = b[:m] + turn + b[m + 1:]
        v, _ = search(nb, me, "O" if turn == "X" else "X", depth - 1)
        if best is None or (v > best[0] if turn == me else v < best[0]):
            best = (v, m)
    return best

def play(first, second, learn=False):
    b, turn = "." * 9, "X"
    players = {"X": first, "O": second}
    while not winner(b) and "." in b:
        if players[turn] == "random":
            m = random.choice(moves(b))
        else:
            v, m = search(b, turn, turn, 2)
            if learn:                            # 先読み前の評価値を、先読み後の評価値に近づける
                f, s = features(b, turn), static(b, turn)
                for i in range(len(w)):
                    w[i] += RATE * (v - s) * f[i]
        b = b[:m] + turn + b[m + 1:]
        turn = "O" if turn == "X" else "X"
    return winner(b)

def test(n=200):
    r = {"勝ち": 0, "引き分け": 0, "負け": 0}
    for g in range(n):
        me = "X" if g % 2 == 0 else "O"
        res = play("ai", "random") if me == "X" else play("random", "ai")
        r["勝ち" if res == me else "負け" if res else "引き分け"] += 1
    return r

random.seed(1)
print("学習前：ランダムに打つ相手と 200 回対戦 →", test())
random.seed(1959)
for g in range(GAMES):
    play("ai", "ai", learn=True)
print("重み：", "  ".join(f"{n} {x:+.2f}" for n, x in zip(NAMES, w)))
random.seed(1)
print(f"自己対戦を {GAMES} 回行って学習した後 →", test())

151960・Mark I

でたらめな配線とモーターで回すつまみ

学習する機械を、プログラムではなく実物の機械として作ると？

1960年6月23日、パーセプトロンの専用機械Mark Iが初めて公開された。重みはモーターで回す（ポテンショメーター）で調整し、配線は大きな差し替え盤でつないだ。1961年の報告によると、A細胞512個と、答えを出すR細胞8個を備えていた。組み立てはワイトマンとマーティン、実験はヘイが担当した。

構造は3段。網膜（S）の点からA細胞へは、ランダムに選んだ点につなぐだけで、ここは学習しない。学習するのはA細胞からR細胞への重みだけだ。右の図は、同じ報告の実験1にならい、上下・左右がつながった輪の網膜で、横の棒と縦の棒を識別させる。

A細胞を通さずに網膜を直接つなぐと、何周学習しても誤りが消えない。どの重みにしても、横の棒全体の点数の平均と、縦の棒全体の点数の平均が同じになるからだ。ランダムなA細胞を80個はさむと、点の組み合わせをとらえる細胞が混ざり、数周で誤りが0になる。

報告書には、教師役がわざと30%間違えて教えても、EとXを100%識別できるようになった実験も記録されている（誤りを正す学習法とは別の方法）。Mark Iは現在、スミソニアン協会にある。

1周（16本）ごとの誤りの数

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_mark1_alpha.py

# u03 Mark I の構造：ランダムな配線（A 細胞）と、学習するつまみ（重み）
#
# どの出来事か：1960 年に公開されたローゼンブラットのパーセプトロン Mark I（記録 perceptron_1957）。
#   ローゼンブラットの 1961 年の報告によると、Mark I は A 細胞 512 個・出力の R 細胞 8 個をもち、
#   重みはモーターで回すつまみ（ポテンショメーター）、配線は大きな差し替え盤だった。
#   網膜（S）→ A 細胞 → R 細胞 と並ぶ構造で、網膜から A 細胞への配線はランダムに選んだ点につなぐだけで学習しない。
#   学習するのは A 細胞から R 細胞への重みだけで、間違えた時だけ修正する（誤り訂正学習）。
# 仕組み：同じ報告の実験 1 にならって、横の棒と縦の棒を識別させる（網膜はここでは 8×8 の小さなもの。
#   上と下、左と右がつながった「輪」になっていて、棒はどの位置にも置ける）。
#   A 細胞が 0 個（網膜を R 細胞に直接つなぐ）だと、何回学習しても誤りが残る。
#   横の棒も縦の棒も光る点の数は同じで、どの重みでも「全部の横の棒の点数の平均」と「全部の縦の棒の点数の平均」が
#   同じになってしまうからだ。ランダムな A 細胞を挟むと、識別できるようになる。
# 試してみよう：
#   - LINKS（A 細胞 1 個が見る点の数）を 1 にすると、どうなるか
#   - A 細胞の数を 512（Mark I と同じ）にしてみる

import random

random.seed(1960)
N = 8          # 網膜は 8×8
WIDTH = 2      # 棒の太さ
LINKS = 4      # A 細胞 1 個が見る網膜の点の数
SWEEPS = 60    # 全部の棒を見せる回数（いちばん多くて）

def bars():
    out = []
    for p in range(N):
        h = [[1 if (r - p) % N < WIDTH else 0 for c in range(N)] for r in range(N)]
        v = [[1 if (c - p) % N < WIDTH else 0 for c in range(N)] for r in range(N)]
        out += [(h, 1), (v, -1)]          # 横の棒＝+1、縦の棒＝-1
    return out

def make_a_units(n):
    units = []
    for _ in range(n):
        pts = [(random.randrange(N), random.randrange(N), random.choice((1, -1))) for _ in range(LINKS)]
        units.append(pts)                 # ランダムな点と、+（光ると上げる）か -（光ると下げる）。＋－の決め方はこのサイトが決めたもの
    return units

def a_layer(img, units):
    if not units:                          # A 細胞なし：網膜の点をそのまま使う
        return [x for row in img for x in row]
    return [1 if sum(s * img[r][c] for r, c, s in u) >= 1 else 0 for u in units]

def train(n_units):
    units = make_a_units(n_units)
    data = [(a_layer(img, units), t) for img, t in bars()]
    w = [0] * len(data[0][0])
    b = 0
    for sweep in range(1, SWEEPS + 1):
        mistakes = 0
        for x, t in data:
            y = 1 if sum(wi * xi for wi, xi in zip(w, x)) + b > 0 else -1
            if y != t:                     # 間違えた時だけ、つまみ（重み）を回す
                mistakes += 1
                w = [wi + t * xi for wi, xi in zip(w, x)]
                b += t
        if mistakes == 0:
            return sweep, 0
    return SWEEPS, mistakes

print(f"横の棒 {N} 本と縦の棒 {N} 本（8×8 の輪の網膜）を識別する\n")
for n in (0, 5, 20, 80, 320):
    sweeps, left = train(n)
    name = "A 細胞なし（網膜を直接つなぐ）" if n == 0 else f"ランダムな A 細胞 {n} 個"
    if left == 0:
        print(f"  {name:<22} → {sweeps} 回目で、誤りが 0 になった")
    else:
        print(f"  {name:<22} → {sweeps} 回学習しても、誤りが {left} 個残る " + "■" * left)

161960・人と計算機

1台の計算機をみんなで分けて使う

機械に全部考えさせる前に、人と計算機はどう組めばよいか。

1960年3月、リックライダーは論文を発表した。イチジクの木と花粉を運ぶ虫が助け合うように、人が目標を決め、仮説を立て、基準を決めて評価し、計算機は定型的な作業を受け持つ協調の形を考えた。本人が1957年の春と夏に自身の作業を記録したところ、考える時間のおよそ85%は、考えるための準備（探す・計算する・グラフを描くなど）に使われていたという。

そのために必要な技術の1つが、タイムシェアリング（1台の計算機の時間を、大勢で細かく分けて使う仕組み）だ。当時の大型計算機は、1人と一緒に考えるには速すぎて費用も高いため、利用時間を多くの人で分けるべきだと論じた。右の図で、順番待ちと比べてみよう。計算機が処理する時間の合計は同じでも、最初の返事までの待ち時間がずっと短くなる。

知ってるつもりよく言われる話：リックライダーは1980年までに機械が考えるようになると予言した
元の資料では：論文のは空軍の研究会の見積もりを紹介したもの。本人は、人と計算機が組む時代の長さについて（訳）と幅をもたせた。

171976・答え合わせ

4色問題：人の筋道とコンピュータの力仕事

コンピュータが定理を証明したと言えるのはどんな時か。

（訳）という予言の10年以内には、そう言える出来事の記録は見当たらない。1976年、アペルとハーケンが（どんな地図も4色で塗り分けられるという、1852年ごろからの問題）を証明した。しかし証明の筋道や形の分類手順は人が作り、コンピュータは2000近くの形を1つずつ調べる役だった。

右の図は、このサイトが作った例の地図をコンピュータに塗らせるものだ。国を1つずつ塗り、塗れる色がなくなったら1つ前に戻る（バックトラック）。A・B・C・Dは互いに全部隣り合うため、3色ではどう試しても塗れない。1枚の地図を塗り分ける探索計算と、すべての地図について成り立つ定理の証明とは別ものだ。

1996年10月には、証明探索プログラムEQPが、1930年代から解けていなかったの証明を、約8日かけて自動で見つけた。どちらの場合も、問題そのものは人が前から提示していた。

知ってるつもりよく言われる話：1976年にコンピュータが四色定理を証明した
元の資料では：発表の本文では、分類の手順は人が手で作り、コンピュータは多くの形を1つずつ調べる役だった。

「さわってみる」と同じ仕組みを、Pythonで書いたコードです。▶ 動かすを押すと、下に結果が出ます。数を書きかえて、もう一度動かしてみよう。

u03_four_colors.py

# u03 4色で塗り分ける：隣同士が同じ色にならないように、試しては戻る
#
# どの出来事か：1957 年の予言「10 年以内に、計算機が大事な新しい数学の定理を見つけて証明する」の、その後
#   （記録 simon_newell_theorem_1958）。1976年、アペルとハーケンは四色定理（どんな地図も4色で塗り分けられる）を
#   証明した。証明の筋道と形の分類手順は人間が作り、コンピュータは2000近くの形を1つずつ調べる役だった。
# 仕組み：このサイトが作った例の地図（国A〜J）を、隣同士が同じ色にならないように塗る。
#   国を1つずつ順に塗り、塗れる色がなくなったら、1つ前の国に戻って色を変える（バックトラック法）。
#   これは1枚の地図を塗る計算で、定理の証明（すべての地図について成り立つこと）とは別のものである。
# 試してみよう：
#   - COLORS を 3 にすると、この地図は塗れるか（A・B・C・D の 4 つの国は、互いにすべて隣り合っている）
#   - SMART を False にすると（隣が多い国から先に塗る工夫をやめると）、試す回数はどう変わるか。
#     3色の時と4色の時で比べる

COLORS = 4
SMART = True
MAP = [   # このサイトが作った例（1文字が1マス。同じ文字が1つの国）
    "BBBCCCC",
    "BBAACCC",
    "BDAACFF",
    "DDDDDFF",
    "EEGGGII",
    "EHHJJII",
]
NAMES = ["赤", "青", "黄", "緑", "紫"]

NEIGHBORS = {}   # マスが上下・左右で接している国同士が「となり」
for r, row in enumerate(MAP):
    for c, a in enumerate(row):
        NEIGHBORS.setdefault(a, set())
        for rr, cc in ((r + 1, c), (r, c + 1)):
            if rr < len(MAP) and cc < len(row) and MAP[rr][cc] != a:
                b = MAP[rr][cc]
                NEIGHBORS[a].add(b)
                NEIGHBORS.setdefault(b, set()).add(a)

order = sorted(NEIGHBORS, key=lambda c: (-len(NEIGHBORS[c]), c)) if SMART else sorted(NEIGHBORS)
color = {}
tries = backs = 0

def paint(i):
    global tries, backs
    if i == len(order):
        return True
    country = order[i]
    for k in range(COLORS):
        tries += 1
        if all(color.get(n) != k for n in NEIGHBORS[country]):
            color[country] = k
            if paint(i + 1):
                return True
            del color[country]
    backs += 1          # どの色もだめ → 1つ前に戻る
    return False

ok = paint(0)
print(f"{COLORS} 色で、塗る順番 {' → '.join(order)}")
if ok:
    print("塗れた：", "  ".join(f"{c}={NAMES[color[c]]}" for c in sorted(color)))
else:
    print("塗れなかった")
print(f"色を試した回数 {tries}、戻った回数 {backs}")
bad = [(a, b) for a in sorted(NEIGHBORS) for b in sorted(NEIGHBORS[a]) if a < b and ok and color[a] == color[b]]
print("隣同士で同じ色：", bad if bad else "なし")
if ok:
    print("\n地図（色の1文字目）")
    for row in MAP:
        print("  " + "".join(NAMES[color[a]][0] for a in row))

「人工知能」を掲げた夏の計画書

ひと夏の研究会はどんな集まりだったか

証明を片っ端から作ると

答えの側から、逆向きに探す

間違えた時だけ、重みを直す

「10年以内に」4つの予言

答え合わせの日を、自分で書いた

カードの印は、右か左か

かっこの入れ子で、式を式のまま扱う

空港へ行くため最初にする行動を導く

悪魔たちの叫び声で文字を認識する

目標との「ちがい」を小さくする手を選ぶ

ワレガ オンガクヲ コノム

点数の付け方を、自分で直す

でたらめな配線とモーターで回すつまみ

1台の計算機をみんなで分けて使う

4色問題：人の筋道とコンピュータの力仕事

この章で、まだ分かっていないこと

を掲げた夏の計画書

目標とのを小さくする手を選ぶ

ワレガオンガクヲコノム