Ticket #107: check_eye_patterns.pike

#!/usr/bin/env pike

array(Eyegraph) database = ({});

class Eyegraph
{
  int number;
  mapping(string:Eyevertex) vertices = ([]);
  Eyevalue eyevalue = Eyevalue("0000");
  int esize = 0;
  int msize = 0;
  string position = "center";
  string coded_string;

  void create(int n)
  {
    number = n;
  }

  void add_vertex(Eyevertex vertex)
  {
    vertices[vertex->name] = vertex;
    if (vertex->is_margin())
      msize++;
    esize++;
    if (vertex->edge == 1 && position == "center")
      position = "edge";
    else if (vertex->edge == 2)
      position = "corner";
  }

  void eliminate_vertex(string v, string recurse)
  {
    array(string) neighbors = vertices[v]->neighbors;
    foreach (neighbors, string v2)
      vertices[v2]->neighbors -= ({v});

    if (vertices[v]->is_margin())
      msize--;
    esize--;

    if (recurse == "recursive")
      foreach (neighbors, string v2) {
        if (!vertices[v2])
          continue;
        switch (vertices[v2]->symbol) {
        case ".":
          vertices[v2]->symbol = "!";
          msize++;
          break;
        case "X":
        case "$":
          eliminate_vertex(v2, "recursive");
          break;
        }
      }

    m_delete(vertices, v);
  }

  Eyevalue guess_eyevalue()
  {
    int margins_adjacent_to_margin = 0;
    foreach (indices(vertices), string v) {
      if (vertices[v]->is_margin()) {
        foreach (vertices[v]->neighbors, string v2) {
          if (vertices[v2]->is_margin()) {
            margins_adjacent_to_margin++;
            break;
          }
        }
      }
    }
    int effective_eyesize = esize - 2*msize - margins_adjacent_to_margin;

    if (effective_eyesize > 3)
      return Eyevalue("2222");

    if (effective_eyesize > 0)
      return Eyevalue("1111");

    if (esize - msize > 2)
      return Eyevalue("0011");

    return Eyevalue("0000");
  }

  array(string) find_subgraph(string v, void|array(string) subgraph)
  {
    if (!subgraph)
      subgraph = ({});

    subgraph += ({v});
    foreach (vertices[v]->neighbors, string v2) {
      if (search(subgraph, v2) < 0
          && (!vertices[v]->is_margin()
              || !vertices[v2]->is_margin()))
        subgraph = find_subgraph(v2, subgraph);
    }
    
    return subgraph;
  }

  void remove_captured_stones()
  {
    multiset checked = (<>);
    foreach (indices(vertices), string v) {
      if (checked[v])
        continue;

      array(string) connected = find_subgraph(v);

      int captured = 1;
      foreach (connected, string v2) {
        if (search("X$", vertices[v2]->symbol) < 0) {
          captured = 0;
          break;
        }
      }
      
      foreach (connected, string v2) {
        if (captured)
          vertices[v2]->symbol = (["X":".", "$":"!"])[vertices[v2]->symbol];
        checked[v2] = 1;
      }
    }
  }

  array(Eyegraph) split_into_subgraphs()
  {
    multiset checked = (<>);
    array(Eyegraph) subgraphs = ({});

    foreach (indices(vertices), string v) {
      if (checked[v])
        continue;

      array(string) connected = find_subgraph(v);
      Eyegraph g = Eyegraph(-1);

      foreach (connected, string v2) {
        g->add_vertex(vertices[v2]->copy());
        checked[v2] = 1;
      }

      g->prune_invalid_neighbors();

      subgraphs += ({g});
    }
    
    return subgraphs;
  }

  void prune_invalid_neighbors()
  {
    foreach (values(vertices), Eyevertex v)
      for (int k = sizeof(v->neighbors) - 1; k >= 0; k--)
        if (!vertices[v->neighbors[k]])
          v->neighbors -= ({v->neighbors[k]});
  }

  array(string) attack_points(void|mapping(string:string) map)
  {
    array(string) result = ({});
    foreach (indices(vertices), string v)
      if (vertices[v]->is_attack_point()) {
        if (!map)
          result += ({v});
        else
          result += ({map[v]});
      }

    return result;
  }

  array(string) defense_points(void|mapping(string:string) map)
  {
    array(string) result = ({});
    foreach (indices(vertices), string v)
      if (vertices[v]->is_defense_point()) {
        if (!map)
          result += ({v});
        else
          result += ({map[v]});
      }

    return result;
  }

  array(string) empty_points(void|mapping(string:string) map)
  {
    array(string) result = ({});
    foreach (indices(vertices), string v)
      if (vertices[v]->is_empty_point()) {
        if (!map)
          result += ({v});
        else
          result += ({map[v]});
      }

    return result;
  }

  Eyegraph copy()
  {
    Eyegraph g = Eyegraph(number);
    g->eyevalue = eyevalue;
    g->esize = esize;
    g->msize = msize;
    foreach (indices(vertices), string s)
      g->vertices[s] = vertices[s]->copy();
    return g;
  }

  void print()
  {
    write("%d: %s %d %d\n", number, (string) eyevalue, esize, msize);
    foreach (values(vertices), Eyevertex vertex)
      vertex->print();
  }

  array(string) stringify()
  {
    array(string) result = ({});
    foreach (values(vertices), Eyevertex v) {
      int i, j;
      sscanf(v->name, "%d,%d", i, j);
      i--;
      j--;
      while (sizeof(result) < i + 1)
        result += ({""});
      while (strlen(result[i]) < j+1)
        result[i] += " ";
      result[i][j] = v->symbol[0];
    }
    return result;
  }

  void prettyprint()
  {
    write(stringify() * "\n" + "\n");
    write("%d: %s\n", number, (string) eyevalue);
  }
}

class Eyevertex
{
  string symbol;
  string name;
  array(string) neighbors = ({});
  int edge = 0;
  array(string) edgenames = ({"", ", edge", ", corner"});

  void create(string s, int i, int j)
  {
    symbol = s;
    name = i + "," + j;
  }

  void add_neighbor(array(string) diagram, int i, int j)
  {
    if (diagram[i][j] == '-' || diagram[i][j] == '|')
      edge++;
    else if (diagram[i][j] != ' ')
      neighbors += ({i + "," + j});
  }

  int is_margin()
  {
    return (search("!$@()", symbol) >= 0);
  }

  int is_attack_point()
  {
    return (search("*<@(", symbol) >= 0);
  }

  int is_defense_point()
  {
    return (search("*>@)", symbol) >= 0);
  }

  int is_empty_point()
  {
    return (search(".*<>!@()", symbol) >= 0);
  }

  Eyevertex copy()
  {
    Eyevertex v = Eyevertex("", 0, 0);
    v->symbol = symbol;
    v->name = name;
    v->neighbors = neighbors;
    v->edge = edge;
    return v;
  }

  void print()
  {
    write("%s (%s%s): %s\n", name, symbol, edgenames[edge], neighbors * ", ");
  }
}

class Eyevalue
{
  int a, b, c, d;
  
  void create(string|Eyevalue x)
  {
    if (stringp(x))
      [a, b, c, d] = (array(int)) (x / "");
    else {
      a = x->a;
      b = x->b;
      c = x->c;
      d = x->d;
    }
  }

  Eyevalue `+(Eyevalue v)
  {
    Eyevalue result = Eyevalue("0000");
    result->b = min(max(b + v->b, min(a + v->d, b + v->c)),
                    max(b + v->b, min(d + v->a, c + v->b)));
    result->c = max(min(c + v->c, max(d + v->a, c + v->b)),
                    min(c + v->c, max(a + v->d, b + v->c)));
    result->a = min(a + v->c, c + v->a, max(a + v->b, b + v->a));
    result->d = max(d + v->b, b + v->d, min(d + v->c, c + v->d));

    // Annoying exception, but 0011+0002 must not be 0012.
    if ((d - c == 2 && v->c - v->b == 1)
        || (c - b == 1 && v->d - v->c == 2)) {
      result->d = max(min(c + v->d, d + v->b), min(d + v->c, b + v->d));
    }

    return result;
  }

  int `>(Eyevalue v)
  {
    return !(a <= v->a && b <= v->b && c <= v->c && d <= v->d);
  }

  int `<(Eyevalue v)
  {
    return !(a >= v->a && b >= v->b && c >= v->c && d >= v->d);
  }

  int severity()
  {
    if (b == c)
      return 0;
    else
      return (d + c - b - a);
  }

  int check_consistency(Eyevalue v, string attack_or_defend)
  {
    string s1 = (string) this_object()->normalize();
    string s2 = (string) v->normalize();
    if (attack_or_defend == "attack") {
      if (s1 == "0000" || s1 == "0001" || s1 == "0002")
        return 1;
      if ((s1 == "0011" || s1 == "0012" || s1 == "0022")
          && (s2 == "0000" || s2 == "0001" || s2 == "0002"))
        return 1;
      if ((s1 == "0111" || s1 == "0112" || s1 == "1111" || s1 == "1112")
          && v >= Eyevalue("0011"))
        return 1;
      if (s1 == "0122" && s2 == "0011")
        return 1;
      if ((s1 == "0222" || s1 == "1222" || s1 == "2222")
          && v >= Eyevalue("0022"))
        return 1;
      if (s1 == "1122" 
          && (s2 == "0012" || s2 == "0111" || s2 == "0112"
              || s2 == "1111" || s2 == "1112"))
        return 1;

      return 0;
    //      return (min(a, 2) <= v->b && min(b, 2) <= v->c);
    }
    else {
      if ((s1 == "0000" || s1 == "0001" || s1 == "0002")
          && v->normalize() <= Eyevalue("0022"))
        return 1;
      if (s1 == "0011" 
          && (s2 == "0122" || s2 == "1112" || s2 == "0112"
              || s2 == "1111" || s2 == "0111"))
        return 1;
      if (s1 == "0012" && s2 == "1122")
        return 1;
#if 0
      if ((s1 == "0111" || s1 == "0112" || s1 == "1111" || s1 == "1112")
          && v->normalize() <= Eyevalue("1122"))
        return 1;
#endif
      if ((s1 == "0111" || s1 == "1111")
          && (s2 == "0122" || v->normalize() <= Eyevalue("1112")))
        return 1;
      if ((s1 == "0112" || s1 == "1112")
          && v->normalize() <= Eyevalue("1122"))
        return 1;
      if ((s1 == "1122" || s1 == "0122" || s1 == "0022")
          && (s2 == "2222" || s2 == "1222" || s2 == "0222"))
        return 1;
      if (s1 == "0222" || s1 == "1222" || s1 == "2222")
        return 1;

      return 0;
  //    return (c >= min(v->b, 2) && (d >= min(v->c, 2)
  //                              || (c > v->a && c >= v->b)));
    }
  }

  int min_eyes()
  {
    return b;
  }

  int max_eyes()
  {
    return c;
  }
  
  Eyevalue normalize()
  {
    Eyevalue e = Eyevalue("0000");
    e->a = min(a, 2);
    e->b = min(b, 2);
    e->c = min(c, 2);
    e->d = min(d, 2);
    return e;
  }

  mixed cast(string type)
  {
    if (type == "string")
      return sprintf("%d%d%d%d", a, b, c, d);
  }
}

mapping(string:mapping(string:string)) addition_table =
(["0"  : (["0":"0", "1/2":"1/2", "1":"1", "1*":"1*", "3/2":"3/2", "2":"2"]),
  "1/2": (["0":"1/2", "1/2":"1", "1":"3/2", "1*":"3/2", "3/2":"2", "2":"2"]),
  "1"  : (["0":"1", "1/2":"3/2", "1":"2", "1*":"3/2", "3/2":"2", "2":"2"]),
  "1*" : (["0":"1*", "1/2":"3/2", "1":"3/2", "1*":"2", "3/2":"2", "2":"2"]),
  "3/2": (["0":"3/2", "1/2":"2", "1":"2", "1*":"2", "3/2":"2", "2":"2"]),
  "2":   (["0":"2", "1/2":"2", "1":"2", "1*":"2", "3/2":"2", "2":"2"]),
]);

string add_eye_values(string e1, string e2)
{
  // write("add: %s %s %s\n", e1, e2, addition_table[e1][e2]);
  return addition_table[e1][e2];
}

class GtpEngine
{
  object f1 = Stdio.File();
  object pipe1 = f1->pipe();
  object f2 = Stdio.FILE();
  object pipe2 = f2->pipe();

  void create() 
  {
    array(string) program_start_array = ({"../interface/gnugo", "--quiet", "--mode", "gtp"});
    Process.create_process(program_start_array, (["stdin":pipe1, "stdout":pipe2]));
  }
  
  string command(string s)
  {
    array(string) result = ({});
    string a;
    f1->write(s + "\n");
    while (1) {
      a = f2->gets();
      if (a == "")
        break;
      result += ({a});
    }
    result[0] = result[0][2..];
    return result * "\n";
  }

  string shutdown()
  {
    command("quit");
    f1->close();
    f2->close();
  }
}

void play_in_graph(Eyegraph g, string v, string who)
{
  string symbol = g->vertices[v]->symbol;
  if (search("X$", symbol) >= 0) {
    werror("Invalid play!\n");
    return;
  }
  
  if (who == "O")
    g->eliminate_vertex(v, "nonrecursive");
  else {
    if (symbol == ".")
      g->vertices[v]->symbol = "X";
    else
      g->eliminate_vertex(v, "recursive");
  }

  g->remove_captured_stones();
}

mapping(string:string)
graph_match(Eyegraph eyespace, Eyegraph graph,
            void|mapping(string:string) map)
{
  int debug = 0;

  if (!map) {
    if (graph->esize != eyespace->esize
        || graph->msize != eyespace->msize)
      return 0;
    else
      map = ([]);
  }

  if (debug)
    write("%O\n", map);

  array(string) remaining_indices = indices(graph->vertices) - values(map);
  if (sizeof(remaining_indices) == 0)
    return map;
  
  string next_vertex = (indices(eyespace->vertices) - indices(map))[0];

  if (debug)
    write("next_vertex = %s\n", next_vertex);

  foreach (remaining_indices, string v) {
    map[next_vertex] = v;
    Eyevertex v1 = eyespace->vertices[next_vertex];
    Eyevertex v2 = graph->vertices[v];

    // Number of neighbors.
    if (sizeof(v1->neighbors) != sizeof(v2->neighbors)) {
      if (debug)
        write("mismatch 1\n");
      continue;
    }
    
    // Is marginal?
    if (v1->is_margin() && !v2->is_margin()) {
      if (debug)
        write("mismatch 2\n");
      continue;
    }

    // Is not marginal?
    if (!v1->is_margin() && v2->is_margin()) {
      if (debug)
        write("mismatch 3\n");
      continue;
    }

    // Is stone?
    if (search("X$", v1->symbol) >= 0
        && search("Xx$", v2->symbol) < 0) {
      if (debug)
        write("mismatch 4\n");
      continue;
    }

    // Is empty?
    if (search(".!", v1->symbol) >= 0
        && search("X$", v2->symbol) >= 0) {
      if (debug)
        write("mismatch 5\n");
      continue;
    }

    // Is edge?
    if (v1->edge < v2->edge) {
      if (debug)
        write("mismatch 6\n");
      continue;
    }

    // Check neighbors.
    array(string) mapped_neighbors1 =
      v1->neighbors - (v1->neighbors - indices(map));
    array(string) mapped_neighbors2 =
      v2->neighbors - (v2->neighbors - values(map));

    if (debug) {
      write("mapped_neighbors1: %s\n", mapped_neighbors1 * " ");
      write("mapped_neighbors2: %s\n", mapped_neighbors2 * " ");
    }

    int ok = 1;
    foreach (mapped_neighbors1, string mn)
      if (search(mapped_neighbors2, map[mn]) < 0) {
        ok = 0;
        break;
      }
    
    if (!ok) {
      if (debug)
      write("mismatch 7\n");
      continue;
    }

    mapping(string:string) result_map = graph_match(eyespace, graph, map);
    if (result_map)
      return result_map;
  }
  
  m_delete(map, next_vertex);

  return 0;
}

array(mixed)
match_database(Eyegraph eyespace)
{
  mapping(string:string) map;

  foreach (database, Eyegraph graph) {
    map = graph_match(eyespace, graph);
    if (map)
      return ({graph, map});
  }
  
  return ({0, 0});
}

Eyegraph
finish_pattern(int n, array(string) diagram, string colon_line)
{
  int i, j;
  Eyegraph graph = Eyegraph(n);
  
  graph->coded_string = replace(diagram * "%", " ", "O");
  
  diagram = ({""}) + diagram + ({""});
  for (i = 0; i < sizeof(diagram); i++)
    diagram[i] = (" " + diagram[i] + " "*15)[0..14];
  for (i = 1; i < sizeof(diagram) - 1; i++) {
    string row = diagram[i];
    for (j = 1; j < strlen(row); j++) {
      if (search(" |-+", row[j..j]) < 0) {
        Eyevertex vertex = Eyevertex(row[j..j], i, j);
        vertex->add_neighbor(diagram, i-1, j);
        vertex->add_neighbor(diagram, i+1, j);
        vertex->add_neighbor(diagram, i, j-1);
        vertex->add_neighbor(diagram, i, j+1);
        graph->add_vertex(vertex);
      }
    }
  }
  
  graph->eyevalue = Eyevalue(colon_line - ":");
  return graph;
}

void
read_eyes_db()
{
  string eyes_db = Stdio.read_file("eyes.db");
  int n;
  Eyegraph graph;
  string state = "waiting for pattern";
  array(string) diagram = ({});

  foreach (eyes_db / "\n", string row) {
    if (row[0..0] == "#")
      continue;
    if (row == "")
      continue;

    switch (state) {
    case "waiting for pattern":
      if (sscanf(row, "Pattern %d", n) == 1) {
        state = "reading diagram";
      }
      break;
    case "reading diagram":
      if (row[0..0] == ":") {
        graph = finish_pattern(n, diagram, row);
        database += ({graph});
        diagram = ({});
        state = "waiting for pattern";
      }
      else {
        diagram += ({row});
      }
      break;
    default:
      werror("Unknown state: '%s'\n", state);
      break;
    }
  }
}

mapping(string:int) severity_values = 
(["0":0, "1/2":1, "1":0, "1*":2, "3/2":1, "2":0]);

array(mixed) compute_eye(Eyegraph g, void|int normalize)
{
  Eyevalue eyevalue = Eyevalue("0000");
  array(string) apoints = ({});
  array(string) dpoints = ({});
  int severity = 0;
  array(string) matched_by = ({});

  foreach (g->split_into_subgraphs(), Eyegraph g2) {
    Eyegraph match;
    mapping(string:string) map;
    [match, map] = match_database(g2);
    if (match) {
      matched_by += ({(string) match->number});
      map = mkmapping(values(map), indices(map));
      if (match->eyevalue->severity() == severity && severity >= 0) {
        apoints += match->attack_points(map);
        dpoints += match->defense_points(map);
      }
      else if (match->eyevalue->severity() > severity) {
        apoints = match->attack_points(map);
        dpoints = match->defense_points(map);
        severity = match->eyevalue->severity();
      }
      eyevalue = eyevalue + match->eyevalue;
    }
    else {
      matched_by += ({"guess"});
      eyevalue = eyevalue + g2->guess_eyevalue();
    }
  }

  if (0 && eyevalue->severity() == 0) {
    apoints = ({});
    dpoints = ({});
  }

  if (normalize)
    eyevalue = eyevalue->normalize();

  return ({eyevalue, matched_by, apoints, dpoints});
}

void complain_about_inconsistency(Eyegraph g, Eyegraph g2,
                                  Eyevalue eyevalue, Eyevalue new_eyevalue,
                                  array(string) matched_by,
                                  array(string) new_matched_by)
{
  write("===========\n");
  g->prettyprint();
  write("valued %s by %s\n", (string) eyevalue, matched_by * ", ");
  g2->prettyprint();
  write("valued %s by %s\n", (string) new_eyevalue, new_matched_by * ", ");
}

void test_consistency(Eyegraph g)
{
  array(string) attack_points = ({});
  array(string) defense_points = ({});
  Eyevalue eyevalue;
  Eyevalue new_eyevalue;
  array(string) matched_by;
  array(string) new_matched_by;
  [eyevalue, matched_by, attack_points, defense_points] = compute_eye(g);

  if (eyevalue->severity() > 0) {
    foreach (attack_points, string v) {
      Eyegraph g2 = g->copy();
      play_in_graph(g2, v, "X");
      [new_eyevalue, new_matched_by] = compute_eye(g2)[0..1];
      if (!eyevalue->check_consistency(new_eyevalue, "attack"))
        complain_about_inconsistency(g, g2, eyevalue, new_eyevalue,
                                     matched_by, new_matched_by);
    }
      
    foreach (defense_points, string v) {
      Eyegraph g2 = g->copy();
      play_in_graph(g2, v, "O");
      [new_eyevalue, new_matched_by] = compute_eye(g2)[0..1];
      if (!eyevalue->check_consistency(new_eyevalue, "defense"))
        complain_about_inconsistency(g, g2, eyevalue, new_eyevalue,
                                     matched_by, new_matched_by);
    }
  }
  else {
    foreach (g->empty_points(), string v) {
      if (eyevalue->max_eyes() > 0) {
        Eyegraph g2 = g->copy();
        play_in_graph(g2, v, "X");
        [new_eyevalue, new_matched_by] = compute_eye(g2)[0..1];
        if (!eyevalue->check_consistency(new_eyevalue, "attack"))
          complain_about_inconsistency(g, g2, eyevalue, new_eyevalue,
                                       matched_by, new_matched_by);
      }
      
      if (eyevalue->min_eyes() < 2) {
        Eyegraph g2 = g->copy();
        play_in_graph(g2, v, "O");
        [new_eyevalue, new_matched_by] = compute_eye(g2)[0..1];
        if (!eyevalue->check_consistency(new_eyevalue, "defense"))
          complain_about_inconsistency(g, g2, eyevalue, new_eyevalue,
                                       matched_by, new_matched_by);
      }
    }
  }
}

void test_template(array(string) template, int|void max_margins)
{
  int i, j;

  array(array(int)) vertices = ({});
  
  int configurations = 1;
  for (i = 0; i < sizeof(template); i++)
    for (j = 0; j < strlen(template[i]); j++)
      if (template[i][j] == '.') {
        vertices += ({ ({i, j}) });
        configurations *= 3;
      }

  if (zero_type(max_margins))
    max_margins = sizeof(vertices);

  for (i = 0; i < configurations; i++) {
    int k = i;
    for (j = 0; j < sizeof(vertices); j++) {
      template[vertices[j][0]][vertices[j][1]] = ({'.', '!', 'X'})[k%3];
      k /= 3;
    }
    Eyegraph g = finish_pattern(-1, template, ":0000");

    // eyespaces with marginal vertices with all neighbors in the
    // eyespace are unreasonable and should be ignored.
    int unreasonable = 0;
    int margins = 0;
    foreach (values(g->vertices), Eyevertex v) {
      if (v->is_margin()) {
        margins++;
        if (sizeof(v->neighbors) == 4)
          unreasonable = 1;
      }
    }

    if (!unreasonable && margins <= max_margins)
      test_consistency(g);
  }
}

void test_database_correctness()
{
  int i;
  
  GtpEngine gtp = GtpEngine();

  for (i = 0; i < sizeof(database); i++) {
    int number = database[i]->number;
    if (has_value(({63619}), number))  // unrealizable by analyze_eyegraph
      continue;
#if 0
    write("-------\n");
#endif
    string coded_eyegraph = database[i]->coded_string;
    coded_eyegraph = replace(coded_eyegraph, ")", "!");
    coded_eyegraph = replace(coded_eyegraph, "(", "!");
    coded_eyegraph = replace(coded_eyegraph, "@", "!");
    coded_eyegraph = replace(coded_eyegraph, ">", ".");
    coded_eyegraph = replace(coded_eyegraph, "<", ".");
    coded_eyegraph = replace(coded_eyegraph, "*", ".");
    
#if 0
    database[i]->prettyprint();
#endif
    if (has_value(coded_eyegraph, "$")) {
#if 0
      write("Skipping.\n");
#endif
      continue;
    }

    array(string) coded_eyegraphs = ({coded_eyegraph});
    while (has_value(coded_eyegraphs[0], "x")) {
      string a, b;
      sscanf(coded_eyegraphs[0], "%sx%s", a, b);
      coded_eyegraphs = coded_eyegraphs[1..] + ({a + "." + b, a + "X" + b});
    }

    int matches = 0;
    array(string) other_matches = ({});
    array(string) trace_messages = ({});
    trace_messages += ({database[i]->stringify() * "\n"});
    trace_messages += ({sprintf("%d: %s\n", database[i]->number,
                                (string) database[i]->eyevalue)});

    foreach (coded_eyegraphs, coded_eyegraph) {
      if (!has_value(coded_eyegraph, ".") && !has_value(coded_eyegraph, "!"))
        continue;

      array(string) eyegraph = replace(coded_eyegraph, "O", " ") / "%";
      Eyegraph e = finish_pattern(-1, eyegraph, ":0000");
      array(string) attack_points = ({});
      array(string) defense_points = ({});
      Eyevalue eyevalue;
      array(string) matched_by;
      [eyevalue, matched_by, attack_points, defense_points] = compute_eye(e);
#if 0
      write(sprintf("%s: %s\n", matched_by * ",", (string) eyevalue));
#endif
      if (matched_by[0] != (string) database[i]->number)
        other_matches |= ({matched_by[0]});
      else {
        matches++;

        string analyzed_eyegraph = gtp->command("analyze_eyegraph " + coded_eyegraph);
        
        trace_messages += ({analyzed_eyegraph + "\n"});

        if (analyzed_eyegraph == "failed to analyze")
          trace_messages += ({"!!!!!!!!!!!!! failed to analyze\n"});
        else {
          string eyevalue2 = (analyzed_eyegraph / "\n")[0];
          if (eyevalue2 != (string) eyevalue)
            trace_messages += ({"!!!!!!!!!!!!! eyevalue mismatch\n"});
          else {
            array(string) eyegraph2 = (analyzed_eyegraph / "\n")[1..];
            foreach (attack_points, string apoints) {
              int a, b;
              sscanf(apoints, "%d,%d", a, b);
              if (!has_value("(<@*", eyegraph2[a-1][b-1..b-1]))
                trace_messages += ({"!!!!!!!!!!!!! bad attack point at " + a + "," + b + "\n"});
            }
            foreach (defense_points, string dpoints) {
              int a, b;
              sscanf(dpoints, "%d,%d", a, b);
              if (!has_value(")>@*", eyegraph2[a-1][b-1..b-1]))
                trace_messages += ({"!!!!!!!!!!!!! bad defense point at " + a + "," + b + "\n"});
            }
          }
        }
      }
    }

    if (matches == 0)
      trace_messages += ({"!!!!!!!!!!!!! Unmatched, covered by " + sort(other_matches) * "," + "\n"});

    if (has_value(trace_messages * "", "!!!!")) {
      write("---------\n");
      write(trace_messages * "\n" + "\n");
    }
  }
  gtp->shutdown();
}

// FIXME: Refactor common parts with previous function.
void test_template_correctness(string coded_eyegraph, int|void lax)
{
  GtpEngine gtp = GtpEngine();

  array(string) coded_eyegraphs = ({coded_eyegraph});
  while (has_value(coded_eyegraphs[0], "x")) {
    string a, b;
    sscanf(coded_eyegraphs[0], "%sx%s", a, b);
    coded_eyegraphs = coded_eyegraphs[1..] + ({a + "." + b, a + "X" + b});
  }
  while (has_value(coded_eyegraphs[0], "?")) {
    string a, b;
    sscanf(coded_eyegraphs[0], "%s?%s", a, b);
    coded_eyegraphs = coded_eyegraphs[1..] + ({a + "." + b, a + "X" + b,
                                               a + "!" + b});
  }
  
  foreach (coded_eyegraphs, coded_eyegraph) {
    if (!has_value(coded_eyegraph, ".") && !has_value(coded_eyegraph, "!"))
      continue;
    
    array(string) eyegraph = replace(coded_eyegraph, "O", " ") / "%";
    Eyegraph e = finish_pattern(-1, eyegraph, ":0000");
    array(string) attack_points = ({});
    array(string) defense_points = ({});
    Eyevalue eyevalue;
    array(string) matched_by;
    [eyevalue, matched_by, attack_points, defense_points] = compute_eye(e, 1);
    string match_message = sprintf("%s: %s\n", matched_by * ",",
                                   (string) eyevalue);
#if 0
    write(match_message);
#endif
      
    string analyzed_eyegraph = gtp->command("analyze_eyegraph "
                                            + coded_eyegraph);
    
    array(string) problems = ({});
    
    if (analyzed_eyegraph == "failed to analyze")
      problems += ({"!!!!!!!!!!!!! failed to analyze\n"});
    else {
      string eyevalue2 = (analyzed_eyegraph / "\n")[0];
      if ((!lax && eyevalue2 != (string) eyevalue)
          || (lax && (eyevalue2[1..2] != ((string) eyevalue)[1..2]
                      || (eyevalue2[1] != eyevalue2[2]
                          && eyevalue2 != (string) eyevalue)))) {
        if (eyevalue2[1..1] == eyevalue2[2..2]
            || (sizeof(analyzed_eyegraph / "" & "(<@*" / "") > 0
                && sizeof(analyzed_eyegraph / "" & ")>@*" / "") > 0))
          problems += ({"!!!!!!!!!!!!! eyevalue mismatch\n"});
      }
      else {
        array(string) eyegraph2 = (analyzed_eyegraph / "\n")[1..];
        foreach (attack_points, string apoints) {
          int a, b;
          sscanf(apoints, "%d,%d", a, b);
          if (!has_value("(<@*", eyegraph2[a-1][b-1..b-1]))
            problems += ({"!!!!!!!!!!!!! bad attack point at "
                          + a + "," + b + "\n"});
        }
        foreach (defense_points, string dpoints) {
          int a, b;
          sscanf(dpoints, "%d,%d", a, b);
          if (!has_value(")>@*", eyegraph2[a-1][b-1..b-1]))
            problems += ({"!!!!!!!!!!!!! bad defense point at "
                          + a + "," + b + "\n"});
        }
      }
    }
    
    if (has_value(problems * "", "!!!!")) {
      write("---------\n");
      write(match_message);
      write(analyzed_eyegraph + "\n");
      write(problems * "\n" + "\n");
    }
  }

  gtp->shutdown();
}


int main(int argc, array(string) argv)
{
  read_eyes_db();

  // Check that all existing patterns are consistent with
  // analyze_eyegraph evaluations. Also check whether there are
  // patterns which will never be used because earlier patterns match
  // before it.
#if 1
  test_database_correctness();
#endif

  // Check that the specified configurations are evaluated identically
  // by analyze_eyegraph and database matching plus guess_eye rules.
#if 1
  // 100
  test_template_correctness("?", 0);
  // 200
  test_template_correctness("??", 0);
  // 300
  test_template_correctness("???", 0);
  // 4000
  test_template_correctness("|?%|xx?%+---", 0);
  // 4100
  test_template_correctness("????", 0);
  // 4200
  test_template_correctness("O?%???", 0);
  // 4300
  test_template_correctness("??%??", 0);
  // 5000
  test_template_correctness("|x%|x%|xxx%+---", 0);
  test_template_correctness("|!%|.%|xxx%+---", 0);
  test_template_correctness("|!%|.%|x.!%+---", 0);
  test_template_correctness("|x%|xxxx%+---", 0);
  test_template_correctness("|!%|.xxx%+---", 0);
  test_template_correctness("|x%|xx.!%+---", 0);
  test_template_correctness("|!%|.x.!%+---", 0);
  test_template_correctness("|xxx%|xOx%+---", 0);
  test_template_correctness("|xx%|Oxx?%+----", 0);
  // 5100
  test_template_correctness("?????", 0);
  // 5200
  test_template_correctness("Ox%xxxx", 0);
  test_template_correctness("Ox%!xxx", 0);
  test_template_correctness("Ox%x!xx", 0);
  test_template_correctness("Ox%xx!x", 0);
  test_template_correctness("Ox%xxx!", 0);
  test_template_correctness("O!%!xxx", 0);
  test_template_correctness("Ox%!!xx", 0);
  test_template_correctness("Ox%!x!x", 0);
  test_template_correctness("Ox%!xx!", 0);
  test_template_correctness("Ox%x!x!", 0);
  test_template_correctness("O!%!x!x", 0);
  test_template_correctness("O!%!xx!", 0);
  // 5300
  test_template_correctness("xx%xxx", 0);
  test_template_correctness("!x%xxx", 0);
  test_template_correctness("x!%xxx", 0);
  test_template_correctness("xx%x!x", 0);
  test_template_correctness("xx%xx!", 0);
  test_template_correctness("!!%xxx", 0);
  test_template_correctness("!x%x!x", 0);
  test_template_correctness("!x%xx!", 0);
  test_template_correctness("x!%!xx", 0);
  test_template_correctness("x!%x!x", 0);
  test_template_correctness("x!%xx!", 0);
  test_template_correctness("!!%!xx", 0);
  test_template_correctness("!!%xx!", 0);
  test_template_correctness("x!%!x!", 0);
  test_template_correctness("!!%!x!", 0);
  // 5400
  test_template_correctness("Ox%xxx%Ox", 0);
  test_template_correctness("Ox%!xx%Ox", 0);
  test_template_correctness("O!%!xx%Ox", 0);
  test_template_correctness("O!%!x!%Ox", 0);
  test_template_correctness("O!%!x!%O!", 0);
  // 60000
  test_template_correctness("??????", 0);
  test_template_correctness("?xxxx?%------", 0);
  test_template_correctness("|?%|xxxx?%+-----", 0);
  test_template_correctness("|?%|x%|xxx?%+----", 0);
  test_template_correctness("|!%|.%|xx%|Oxx%+---", 0);
  test_template_correctness("|xxx%|xOx!%+----", 0);
  // 61000
  test_template_correctness("Ox%xxxxx", 0);
  test_template_correctness("O!%xxxxx", 0);
  test_template_correctness("Ox%!xxxx", 0);
  test_template_correctness("Ox%x!xxx", 0);
  test_template_correctness("Ox%xx!xx", 0);
  test_template_correctness("Ox%xxx!x", 0);
  test_template_correctness("Ox%xxxx!", 0);
  test_template_correctness("O!%!xxxx", 0);
  test_template_correctness("O!%xx!xx", 0);
  test_template_correctness("O!%xxx!x", 0);
  test_template_correctness("O!%xxxx!", 0);
  test_template_correctness("Ox%x!x!x", 0);
  test_template_correctness("Ox%x!xx!", 0);
  test_template_correctness("Ox%xx!x!", 0);
  test_template_correctness("O!%!x!xx", 0);
  test_template_correctness("O!%!xx!x", 0);
  test_template_correctness("O!%!xxx!", 0);
  test_template_correctness("O!%xx!x!", 0);
  test_template_correctness("O!%!x!x!", 0);
  // 62000
  test_template_correctness("OOx%xxxxx", 0);
  test_template_correctness("OO!%xxxxx", 0);
  test_template_correctness("OOx%!xxxx", 0);
  test_template_correctness("OOx%x!xxx", 0);
  test_template_correctness("OOx%xx!xx", 0);
  test_template_correctness("OO!%!xxxx", 0);
  test_template_correctness("OO!%x!xxx", 0);
  test_template_correctness("OOx%!x!xx", 0);
  test_template_correctness("OOx%!xx!x", 0);
  test_template_correctness("OOx%!xxx!", 0);
  test_template_correctness("OOx%x!x!x", 0);
  test_template_correctness("OO!%!xx!x", 0);
  test_template_correctness("OO!%!xxx!", 0);
  test_template_correctness("OOx%!x!x!", 0);
  // 63000
  test_template_correctness("Oxx%xxxx", 0);
  test_template_correctness("Oxx%xxxx%----", 0);
  test_template_correctness("Oxx%!xxx", 0);
  test_template_correctness("Oxx%!xxx%----", 0);
  test_template_correctness("Oxx%x!xx", 0);
  test_template_correctness("O!x%xxxx", 0);
  test_template_correctness("Oxx%!x!x", 0);
  test_template_correctness("Oxx%!xx!", 0);
  test_template_correctness("Oxx%!xx!%----", 0);
  test_template_correctness("O!x%!xxx", 0);
  test_template_correctness("Ox!%!xxx", 0);
  test_template_correctness("Ox!%x!xx", 0);
  test_template_correctness("O!x%!x!x", 0);
  test_template_correctness("O!x%!xx!", 0);
  // 64000
  test_template_correctness("xx%xxxx", 0);
  test_template_correctness("xx%xxxx%----", 0);
  test_template_correctness("|xx%|xxxx%+----", 0);
  test_template_correctness("xx%xxx!", 0);
  test_template_correctness("xx%xxx!%----", 0);
  test_template_correctness("|xx%|xxx!%+----", 0);
  test_template_correctness("xx%xx!x", 0);
  test_template_correctness("xx%x!xx", 0);
  test_template_correctness("xx%!xxx", 0);
  test_template_correctness("!x%xxxx", 0);
  test_template_correctness("xx%x!x!", 0);
  test_template_correctness("xx%!xx!", 0);
  test_template_correctness("!x%xxx!", 0);
  test_template_correctness("xx%!x!x", 0);
  test_template_correctness("!x%xx!x", 0);
  test_template_correctness("!x%x!xx", 0);
  test_template_correctness("x!%!xxx", 0);
  test_template_correctness("!x%x!x!", 0);
  test_template_correctness("x!%!xx!", 0);
  test_template_correctness("x!%!x!x", 0);
  // 65000
  test_template_correctness("xxx%xxx", 0);
  test_template_correctness("xxx%xxx%---", 0);
  test_template_correctness("|xxx%|xxx%+---", 0);
  test_template_correctness("!xx%xxx", 0);
  test_template_correctness("x!x%xxx", 0);
  test_template_correctness("!x!%xxx", 0);
  test_template_correctness("!xx%x!x", 0);
  test_template_correctness("!xx%xx!", 0);
  test_template_correctness("!xx%!xx", 0);
  // 66000
  test_template_correctness("Oxxx%xxx", 0);
  test_template_correctness("Oxxx%!xx", 0);
  test_template_correctness("O!xx%xxx", 0);
  test_template_correctness("Ox!x%xxx", 0);
  test_template_correctness("Oxx!%!xx", 0);
  test_template_correctness("Oxxx%!x!", 0);
  // 67000
  test_template_correctness("Ox%xxxx%Ox", 0);
  test_template_correctness("Ox%!xxx%Ox", 0);
  test_template_correctness("Ox%xxx!%Ox", 0);
  test_template_correctness("O!%!xxx%Ox", 0);
  test_template_correctness("Ox%!xx!%Ox", 0);
  test_template_correctness("O!%!xxx%O!", 0);
  test_template_correctness("O!%!xx!%Ox", 0);
  test_template_correctness("O!%!xx!%O!", 0);
  // 68000
  test_template_correctness("Ox%xxxx%OOx", 0);
  test_template_correctness("Ox%!xxx%OOx", 0);
  test_template_correctness("O!%!xxx%OOx", 0);
  test_template_correctness("Ox%!xx!%OOx", 0);
  test_template_correctness("O!%!xx!%OOx", 0);
  test_template_correctness("O!%!xx!%OO!", 0);
  // 69000
  test_template_correctness("xx%xxx%Ox", 0);
  test_template_correctness("!x%xxx%Ox", 0);
  test_template_correctness("x!%xxx%Ox", 0);
  test_template_correctness("xx%xx!%Ox", 0);
  test_template_correctness("!!%xxx%Ox", 0);
  test_template_correctness("!x%xx!%Ox", 0);
  test_template_correctness("x!%!xx%Ox", 0);
  test_template_correctness("x!%xx!%Ox", 0);
  test_template_correctness("x!%xxx%O!", 0);
  test_template_correctness("xx%xx!%O!", 0);
  test_template_correctness("!x%xx!%O!", 0);
  test_template_correctness("x!%xx!%O!", 0);
  test_template_correctness("x!%!x!%O!", 0);
  // 70000
  test_template_correctness("xxxxxxx", 0);
  test_template_correctness("!.xxxxx", 0);
  test_template_correctness("!.xxx.!", 0);
  test_template_correctness("|x%|x%|x%|xxxx%+----", 0);
  test_template_correctness("|!%|.%|x%|xxxx%+----", 0);
  test_template_correctness("|!%|.%|x%|xx.!%+----", 0);
  // 70500
  test_template_correctness("Ox%xxxxxx", 0);
  test_template_correctness("Ox%xxxx.!", 0);
  test_template_correctness("Ox%!.xxxx", 0);
  test_template_correctness("Ox%!.xx.!", 0);
  test_template_correctness("O!%!.xxxx", 0);
  test_template_correctness("O!%!.xx.!", 0);
  // 71000
  test_template_correctness("OOx%xxxxxx", 0);
  test_template_correctness("OOx%!.xxxx", 0);
  test_template_correctness("OOx%xxxx.!", 0);
  test_template_correctness("OO!%xx.xxx", 0);
  test_template_correctness("OOx%!.xx.!", 0);
  test_template_correctness("OO!%xx.x.!", 0);
  test_template_correctness("OO!%!..xxx", 0);
  test_template_correctness("OO!%!..x.!", 0);
  // 71500
  test_template_correctness("OxOx%xxxxx", 0);
  test_template_correctness("OxOx%!.xxx", 0);
  test_template_correctness("OxOx%!.x.!", 0);
  test_template_correctness("O!Ox%!.xxx", 0);
  test_template_correctness("O!Ox%!.x.!", 0);
  test_template_correctness("O!O!%!.x.!", 0);
  // 72000
  test_template_correctness("Ox%xxxxx%Ox", 0);
  test_template_correctness("Ox%xxx.!%Ox", 0);
  test_template_correctness("Ox%!.xxx%Ox", 0);
  test_template_correctness("Ox%!.x.!%Ox", 0);
  test_template_correctness("O!%!.xxx%Ox", 0);
  test_template_correctness("O!%!.x.!%Ox", 0);
  test_template_correctness("O!%!.xxx%O!", 0);
  test_template_correctness("O!%!.x.!%O!", 0);
  // 72500
  test_template_correctness("OOx%xxxxx%Ox", 0);
  test_template_correctness("OOx%!.xxx%Ox", 0);
  test_template_correctness("OOx%xxx.!%Ox", 0);
  test_template_correctness("OO!%xx.xx%Ox", 0);
  test_template_correctness("OO!%xx..!%Ox", 0);
  test_template_correctness("OOx%!.x.!%Ox", 0);
  // 73000
  test_template_correctness("OOx%xxxxx%OOx", 0);
  test_template_correctness("OOx%?.xxx%OOx", 0);
  test_template_correctness("OO?%xx.xx%OOx", 0);
  test_template_correctness("OOx%?.x.?%OOx", 0);
  test_template_correctness("OO?%?..xx%OOx", 0);
  // 73500
  test_template_correctness("OOx%OOx%xxxxx", 0);
  test_template_correctness("OO?%OO.%xxxxx", 0);
  test_template_correctness("OO?%OO.%?.xxx", 0);
  test_template_correctness("OO?%OO.%?.x.?", 0);
  // 74000
  test_template_correctness("xx%xxxxx", 0);
  test_template_correctness("xx%xxx.!", 0);
  test_template_correctness("|xx%|xxx.!%+-----", 0);
  test_template_correctness("xx%xx.!.", 0);
  // 74500
  test_template_correctness("Oxx%xxxxx", 0);
  test_template_correctness("Oxx%xxxxx%-----", 0);
  test_template_correctness("|x%|x%|xxx%|xx%+--", 0);
  test_template_correctness("Oxx%!.xxx", 0);
  test_template_correctness("Oxx%!.xxx%-----", 0);
  test_template_correctness("|x%|x%|x.!%|xx%+--", 0);
  test_template_correctness("Oxx%xxx.!", 0);
  test_template_correctness("Oxx%xxx.!%-----", 0);
  test_template_correctness("|!%|.%|xxx%|xx%+--", 0);
  test_template_correctness("Oxx%!.x.!", 0);
  test_template_correctness("Oxx%!.x.!%-----", 0);
  test_template_correctness("|!%|.%|x.!%|xx%+--", 0);
  // 75000
  test_template_correctness("OOxxx%xxxx", 0);
  test_template_correctness("OOxxx%xxxx%----", 0);
  test_template_correctness("Oxxxx%xxx%---", 0);
  test_template_correctness("|x%|x%|xx%|xxx%+---", 0);
  test_template_correctness("OOxxx%!.xx", 0);
  test_template_correctness("OOxxx%!.xx%----", 0);
  test_template_correctness("Oxx.!%xxx%---", 0);
  test_template_correctness("|!%|.%|xx%|xxx%+---", 0);
  test_template_correctness("OOx.!%xxxx", 0);
  test_template_correctness("OOx.!%xxxx%----", 0);
  test_template_correctness("Oxxxx%!.x%---", 0);
  test_template_correctness("|x%|x%|xx%|x.!%+---", 0);
  test_template_correctness("OOx.!%!.xx", 0);
  test_template_correctness("OOx.!%!.xx%----", 0);
  test_template_correctness("Oxx.!%!.x%---", 0);
  test_template_correctness("|!%|.%|xx%|x.!%+---", 0);
  // 75500
  test_template_correctness("xx%xxxx%Ox", 0);
  test_template_correctness("|Ox%|xxxx%|xx%+--", 0);
  test_template_correctness("xx%xx.!%Ox", 0);
  test_template_correctness("|Ox%|xx.!%|xx%+--", 0);
  // 76000
  test_template_correctness("Oxx%xxxx%Ox", 0);
  test_template_correctness("Oxx%xx.!%Ox", 0);
  test_template_correctness("Oxx%!.xx%Ox", 0);
  test_template_correctness("Oxx%!..!%Ox", 0);
  // 76500
  test_template_correctness("Ox%xxx%Oxxx", 0);
  test_template_correctness("Ox%!.x%Oxxx", 0);
  test_template_correctness("Ox%xxx%Ox.!", 0);
  test_template_correctness("Ox%!.x%Ox.!", 0);
  // 77000
  test_template_correctness("Ox%Oxx%xxxx", 0);
  test_template_correctness("Ox%Oxx%xx.!", 0);
  test_template_correctness("Ox%Oxx%!.xx", 0);
  test_template_correctness("O!%O.x%xxxx", 0);
  test_template_correctness("O!%O.x%!.xx", 0);
  test_template_correctness("Ox%Oxx%!..!", 0);
  test_template_correctness("O!%O.x%xx.!", 0);
  test_template_correctness("O!%O.x%!..!", 0);
  // 77500
  test_template_correctness("OOx%xxxx%xx", 0);
  test_template_correctness("OOx%xx.!%xx", 0);
  test_template_correctness("OO!%xx.!%xx", 0);
  // 78000
  test_template_correctness("xx%xxx%Oxx", 0);
  test_template_correctness("|Oxx%|xxx%|xx%+--", 0);
  test_template_correctness("!.%.xx%Oxx", 0);
  test_template_correctness("|O.!%|xx.%|xx%+--", 0);
  // 78500
  test_template_correctness("xxx%xxxx", 0);
  test_template_correctness("----%xxxx%xxx", 0);