Expert systems — the machine that reasoned

RULES = [
    (['hair'],                                   'mammal'),
    (['gives milk'],                             'mammal'),
    (['feathers'],                               'bird'),
    (['lays eggs', 'flies'],                     'bird'),
    (['mammal', 'eats meat'],                    'carnivore'),
    (['mammal', 'pointed teeth', 'claws'],       'carnivore'),
    (['mammal', 'hooves'],                       'ungulate'),
    (['mammal', 'chews cud'],                    'ungulate'),
    (['carnivore', 'tawny', 'dark spots'],       'cheetah'),
    (['carnivore', 'tawny', 'black stripes'],    'tiger'),
    (['ungulate', 'long neck', 'long legs', 'dark spots'], 'giraffe'),
    (['ungulate', 'black stripes'],              'zebra'),
    (['bird', 'cannot fly', 'long neck', 'long legs'],     'ostrich'),
    (['bird', 'cannot fly', 'swims'],            'penguin'),
    (['bird', 'good flyer'],                     'albatross'),
]

ANIMALS = {'cheetah','tiger','giraffe','zebra','ostrich','penguin','albatross'}
DERIVED = {c for _, c in RULES}
ASKABLE = sorted({f for conds, _ in RULES for f in conds} - DERIVED)

record('n_rules', len(RULES))
record('n_animals', len(ANIMALS))
record('n_askable', len(ASKABLE))

def forward(facts):
    known = set(facts); why = {}; fired = 0; rounds = 0
    changed = True
    while changed:
        changed = False; rounds += 1
        for conds, concl in RULES:
            if concl not in known and all(c in known for c in conds):
                known.add(concl); why[concl] = conds; fired += 1; changed = True
    return known, why, fired, rounds

obs = ['hair', 'eats meat', 'tawny', 'dark spots']
known, why, fired, rounds = forward(obs)

record('demo_observations', ', '.join(obs))
record('demo_conclusion', next(k for k in known if k in ANIMALS))
record('demo_fired', fired)
record('demo_rounds', rounds)

def explain(fact, why, depth=0):
    lines = ['  ' * depth + fact]
    for c in why.get(fact, []):
        lines += explain(c, why, depth + 1)
    return lines

chain = explain('cheetah', why)
record('demo_chain_depth', max(l.count('  ') for l in chain))
print('\n'.join(chain))

def backward(goal, oracle, asked):
    if goal in DERIVED:
        for conds, concl in RULES:
            if concl != goal: continue
            if all(backward(c, oracle, asked) for c in conds):
                return True
        return False
    if goal not in asked:
        asked[goal] = oracle(goal)
    return asked[goal]

TRUTH = {
    'cheetah':   ['hair','eats meat','tawny','dark spots'],
    'tiger':     ['hair','eats meat','tawny','black stripes'],
    'giraffe':   ['hair','hooves','long neck','long legs','dark spots'],
    'zebra':     ['hair','hooves','black stripes'],
    'ostrich':   ['feathers','cannot fly','long neck','long legs'],
    'penguin':   ['feathers','cannot fly','swims'],
    'albatross': ['feathers','good flyer'],
}

counts = {}
for animal, truth in TRUTH.items():
    asked = {}
    for candidate in ['cheetah','tiger','giraffe','zebra','ostrich','penguin','albatross']:
        if backward(candidate, lambda f: f in truth, asked):
            break
    counts[animal] = (candidate, len(asked))

avg = sum(n for _, n in counts.values()) / len(counts)
record('avg_questions', f'{avg:.1f}')
record('questions_cheetah', counts['cheetah'][1])
record('questions_albatross', counts['albatross'][1])
record('all_correct', 'yes' if all(a == g for g, (a, _) in counts.items()) else 'NO')
record('ask_everything', len(ASKABLE))
record('question_saving', f'{100*(1-avg/len(ASKABLE)):.0f}%')

def plot(ax):
    names = list(counts)
    vals = [counts[n][1] for n in names]
    ax.barh(names, vals)
    for i, v in enumerate(vals):
        ax.text(v + .25, i, str(v), va='center', fontsize=10)
    ax.axvline(len(ASKABLE), ls='--', lw=1.2)
    ax.text(len(ASKABLE) - .4, len(names) - 0.6,
            f'asking everything: {len(ASKABLE)}', ha='right', fontsize=9)
    ax.set_xlim(0, len(ASKABLE) + 1.5)
    ax.set_xlabel('questions the system actually asked')
save_fig('questions-asked', plot, figsize=(7, 3.6))

depths = {}
for animal, truth in TRUTH.items():
    _, w, _, _ = forward(truth)
    depths[animal] = max(l.count('  ') for l in explain(animal, w))
record('max_depth', max(depths.values()))
record('min_depth', min(depths.values()))

def plot(ax):
    names = list(depths)
    ax.bar(names, [depths[n] for n in names])
    for i, n in enumerate(names):
        ax.text(i, depths[n] + .06, str(depths[n]), ha='center', fontsize=10)
    ax.set_ylabel('steps of reasoning')
    ax.set_ylim(0, max(depths.values()) + .7)
    ax.tick_params(axis='x', rotation=30)
save_fig('chain-depth', plot, figsize=(7, 3.4))