Difference between revisions of "AND and OR rules"

From HexWiki
Jump to: navigation, search
 
(almost completely rewritten the article, there are still things to be done, if anybody volunteere...)
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
AND and OR rules are ways to describe how well two distant groups are [[connection|connected]].
+
'''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.
  
−
The AND rule states that for a given player (say [[Red]]), two of their pieces can be connected if it is their turn. In the example below, if Red is to play then she can connect the two pieces. The pieces are said to be connected weakly.
 
 
<hex> R3 C5 Vb2 Sc2 Vd2 </hex>
 
<hex> R3 C5 Vb2 Sc2 Vd2 </hex>
  
−
==OR==
+
== OR Rule ==
  
−
The OR rule states that whoever turn it is, the pieces can be connected. Hence using the OR rule is a way to create [[virtual connection|virtual connections]]. The [[bridge]] is the most famous [[pattern]] involving the OR rule. In the example, even if it is [[Blue]]'s turn, Red can maintain the connection because Blue cannot occupy both starred cells in one move.
+
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>
  
−
==Relations==
+
== Completeness ==
  
−
Two not intersecting AND-connections make one OR-connection like in the bridge above. This is due to th fact that the opponent cannot counter both connection.
+
Anshelevich showed that not every virtual connection could be induced using the rules.
  
−
Two consecutive OR-connections make one AND-connection. If Red plays the star hexa then she has connected strongly the two extreme hexas.
+
However the rules can be [[generalised AND and OR rules|generalised]] in such a way that makes them complete.
−
<hex> R5 C5 Vb2 Sc3 Vd4 </hex>
+
 
 +
== [[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.
 +
* 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: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.

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

This article is a stub. You can help HexWiki by expanding it.
Retrieved from "https://www.hexwiki.net/index.php?title=AND_and_OR_rules&oldid=4539"