AND and OR rules

AND and OR rules are deduction rules that help build virtual connections and semi-connections. It allows to know how well two distant groups are connected. They are mostly known through Vadim Anshelevich's work. He used these rules in his program Hexy.

AND and OR rules can deduce new virtual connections from a set of existing virtual connections. Atomic virtual connections are for instance pair of adjacent cells. They are always used from the point of view of one player.

AND Rule

Consider a pair of virtual connections who share one extremity. If the carriers do not intersect, then the following may be deduced:

• if the shared cell belongs to the opponent, then they do not form another connection.
• if the shared cell is empty, then they form a virtual semi-connection which pivot cell is the shared cell, and which carrier is the union of both carrier.
• if the shared cell belongs to the thinking player, then they form a virtual connection which carrier is the union of both carrier.

OR Rule

Consider a set of virtual semi-connections who share both extremities. If the global intersection of the carriers is empty, then a virtual connection exist between the ends which carrier is the union of the set's carriers.

Completeness

Anshelevich showed that not every virtual connection could be induced using the rules.

However the rules can be generalised in such a way that makes them complete.

TODO

• drawing for incompleteness
• text for complexity
• text for computer usage
• explain the intuitive of the rules
• make it clear if Anshelevich invented the rules, or made them famous (see for instance Jack van Rijswijck PhD).

See Also

• HSearch
• Six

External link

• Jack van Rijswijck.Search and evaluation in Hex. See paragraph 2.1.
• Anshelevich, Vadim V. A hierarichical approach to computer Hex. See paragraph 3.
• Some publications dealing with virtual connections and the And and Or rules, by Anshelevich.