Difference between revisions of "AND and OR rules"
From HexWiki
(added two inner links to be written + category : computer hex + external link) |
(almost completely rewritten the article, there are still things to be done, if anybody volunteere...) |
||
| Line 1: | Line 1: | ||
| − | AND and OR are deduction rules that help build [[virtual connection|virtual connections]] and [[virtual semi-connection|semi-connections]]. It allows to know how well two distant | + | '''AND and OR rules''' are deduction rules that help build [[virtual connection|virtual connections]] and [[virtual semi-connection|semi-connections]]. It allows to know how well two distant [[group]]s are [[connection|connected]]. They are mostly known through [[Vadim Anshelevich]]'s work. He used these rules in his program [[Hexy]]. |
| − | ==AND== | + | 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 [[carrier]]s 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. | ||
| − | |||
<hex> R3 C5 Vb2 Sc2 Vd2 </hex> | <hex> R3 C5 Vb2 Sc2 Vd2 </hex> | ||
| − | ==OR== | + | == 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. | |
<hex> R4 C4 Vb2 Sc2 | <hex> R4 C4 Vb2 Sc2 | ||
Sb3 Vc3 </hex> | Sb3 Vc3 </hex> | ||
| − | == | + | == Completeness == |
| + | |||
| + | Anshelevich showed that not every virtual connection could be induced using the rules. | ||
| + | |||
| + | However the rules can be [[generalised AND and OR rules|generalised]] in such a way that makes them complete. | ||
| − | + | == [[Complexity]] == | |
| + | == Usage in Computer players == | ||
| + | == 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== | ==External link== | ||
| − | *Jack van Rijswijck.[http://home.fuse.net/swmeyers/y-hex.pdf Search and evaluation in Hex]. See paragraph 2.1. | + | * [[Jack van Rijswijck]].[http://home.fuse.net/swmeyers/y-hex.pdf Search and evaluation in Hex]. See paragraph 2.1. |
| − | *Anshelevich, Vadim V. [http://home.earthlink.net/~vanshel/VAnshelevich-ARTINT.pdf A hierarichical approach to computer Hex]. See paragraph 3. | + | * Anshelevich, Vadim V. [http://home.earthlink.net/~vanshel/VAnshelevich-ARTINT.pdf A hierarichical approach to computer Hex]. See paragraph 3. |
| + | * Some [http://home.earthlink.net/~vanshel/Publications.html publications] dealing with virtual connections and the And and Or rules, by Anshelevich. | ||
[[category:Computer Hex]] | [[category:Computer Hex]] | ||
| + | [[category:Theory]] | ||
| + | {{stub}} | ||
Revision as of 22:18, 3 December 2008
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.
Contents
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.
Complexity
Usage in Computer players
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
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.
