match-refute diagrams

1 minute read Published: 2018-08-29

Match-refute diagrams are a low-level hybrid between imperative and logic paradigms, related to both first order logic and binary decision diagrams.

Match-refute diagrams operate on first order predicates over discrete symbols. However, predicates are only used for input and output. Nodes in the diagram are named, and pass information to each other through numbered registers. This design, in comparison to most ways of representing first order logic programs, has a clearly understood runtime: O(ns^r) where n is the number of nodes, s is the number of symbols, and r is the number of registers. By limiting the number of registers and symbols, match-refute diagrams can be efficiently evaluated, even if they are randomly generated. Their design is also intended to be effective as an Implicitly Neutral allelic representation for Evolutionary Strategies. I have not yet run experiments exploring the limits of using them for this purpose.

Essentially, the algorithm for evaluating match-refute diagrams is as follows:

Example (rules of tic-tac-toe):

root: player(_ -> %0) { check_move }
check_move: move(_ -> %1, _ -> %2) { check_space }
check_space: board(%1, %2, :blank) { do_move }
do_move: board(%1 -> %1, %2 -> %2, _ -> %3) {
  output next_board(%1, %2, %0)
} {
  output next_board(%1, %2, %3)
}
Themed by (a fork of) after-dark.