AND and OR rules - Revision history

Selinger: minor grammar

2023-10-07T19:01:27Z

minor grammar

Selinger: Fixed typos; clarified the condition on the OR rule.

2021-12-20T18:37:29Z

Fixed typos; clarified the condition on the OR rule.

Selinger: Removed "see also" section, which wasn't linking to anything relevant.

2021-12-17T02:40:44Z

Removed "see also" section, which wasn't linking to anything relevant.

Selinger: Rewrote this article, which was a stub.

2021-12-17T02:38:32Z

Rewrote this article, which was a stub.

Show changes

Halladba: almost completely rewritten the article, there are still things to be done, if anybody volunteere...

2008-12-03T22:18:52Z

almost completely rewritten the article, there are still things to be done, if anybody volunteere...

Halladba: added two inner links to be written + category : computer hex + external link

2007-12-28T12:50:45Z

added two inner links to be written + category : computer hex + external link

Halladba at 00:47, 27 November 2007

2007-11-27T00:47:21Z

New page

AND and OR rules are ways to describe how well two distant groups are [[connection|connected]].

==AND==

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>

==OR==

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.

<hex> R4 C4 Vb2 Sc2
Sb3 Vc3 </hex>

==Relations==

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.

Two consecutive OR-connections make one AND-connection. If Red plays the star hexa then she has connected strongly the two extreme hexas.
<hex> R5 C5 Vb2 Sc3 Vd4 </hex>

==External link==

Jack van Rijswijck.[http://home.fuse.net/swmeyers/y-hex.pdf Search and evaluation in Hex]. See paragraph 2.1.

@@ Line 3: / Line 3: @@
 == Connections and semi-connections ==
-The AND and OR rules are formulated from the viewpoint of one [[player]]. In this article, we take Red's point of view, although analogous rules of course can also be applied to Blue.
+The AND and OR rules are formulated from the viewpoint of one [[player]]. In this article, we take Red's point of view, although analogous rules can of course also be applied to Blue.
 Consider two cells ''x'' and ''y'' and a set ''E'' of cells containing neither ''x'' nor ''y''. Each of the cells ''x'' and ''y'' may either be empty or occupied by Red. We say that ''E'' is a '''virtual connection''' between ''x'' and ''y'' if Red has a second player strategy in the region ''E'' that results in ''x'' and ''y'' being connected. We say that ''E'' is a '''semi-connection''' if Red has a first-player strategy in ''E'' that results in ''x'' and ''y'' being connected. We say that ''x'' and ''y'' are the '''endpoints''' of the connection and ''E'' is its '''carrier'''.

@@ Line 7: / Line 7: @@
 Consider two cells ''x'' and ''y'' and a set ''E'' of cells containing neither ''x'' nor ''y''. Each of the cells ''x'' and ''y'' may either be empty or occupied by Red. We say that ''E'' is a '''virtual connection''' between ''x'' and ''y'' if Red has a second player strategy in the region ''E'' that results in ''x'' and ''y'' being connected. We say that ''E'' is a '''semi-connection''' if Red has a first-player strategy in ''E'' that results in ''x'' and ''y'' being connected. We say that ''x'' and ''y'' are the '''endpoints''' of the connection and ''E'' is its '''carrier'''.
-In other words, a virtual connection is a connection that Red can guarantee even if Blue goes first, whereas a semi-connection is a connection that Red can guarantee if Red goes first. Red can turn any semi-connection into a virtual connection by placing one more stone in it. Conversely, any more by Blue in a Red virtual connection results in at least a semi-connection.
+In other words, a virtual connection is a connection that Red can guarantee even if Blue goes first, whereas a semi-connection is a connection that Red can guarantee if Red goes first. Red can turn any semi-connection into a virtual connection by placing one more stone in it. Conversely, any move by Blue in a Red virtual connection results in at least a semi-connection.
 Here are some examples of virtual connections between ''x'' and ''y'':
@@ Line 56: / Line 56: @@
 == AND rule ==
-The AND rule is concerned with what happens when a connection ''E''₁ from ''x'' to ''y'' and a connection ''E''₂ from ''y'' to ''z'' are joined together "in sequence". Here, we assume that the two connections disjoint carriers (i.e., they do not have any cells in common).
+The AND rule is concerned with what happens when a connection ''E''₁ from ''x'' to ''y'' and a connection ''E''₂ from ''y'' to ''z'' are joined together "in sequence". Here, we assume that the two connections have disjoint carriers, or more precisely, that they do not have any empty cells in common.
 The AND rule states that the connection from ''x'' to ''z'' is:
@@ Line 75: / Line 75: @@
 The OR rule is concerned with what happens when two or more connections from ''x'' to ''y'' are joined together "in parallel". Here we do ''not'' assume that the carriers are pairwise disjoint, i.e., some of the carriers may overlap.
-The OR rule states that if each ''E''₁, ..., ''E''ₙ is a semi-connection from ''x'' to ''y'', and if the intersection of ''all'' of their carriers is empty (i.e., there is no empty cell that is common to all of them), then their union forms a virtual connection from ''x'' to ''y''.
+The OR rule states that if each of ''E''₁, ..., ''E''ₙ is a semi-connection from ''x'' to ''y'', and if there is no empty cell that is common to all of their carriers, then their union forms a virtual connection from ''x'' to ''y''.
 In pictures:

← Older revision		Revision as of 02:40, 17 December 2021
Line 188:		Line 188:

	The AND and OR rules have been used in some computer Hex programs to search for virtual connections. Notably, they were used in Anshelevich's [[Hexy]].		The AND and OR rules have been used in some computer Hex programs to search for virtual connections. Notably, they were used in Anshelevich's [[Hexy]].
−
−	~~== See also ==~~
−
−	*[[Six]]

	== References ==		== References ==

@@ 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 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.
 <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
               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.
+== [[Complexity]] ==
-Two consecutive OR-connections make one AND-connection. If Red plays the star hexa then she has connected strongly the two extreme hexas.
+== See Also ==
-<hex> R5 C5 Vb2 Sc3 Vd4 </hex>
 ==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.
 [[category:Computer Hex]]