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...)
(Rewrote this article, which was a stub.)
Line 1: Line 1:
−
'''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]].
+
The '''AND and OR rules''' are deduction rules that can be used to build [[virtual connection|virtual connections]] and semi-connections. They often make it possible to compute whether two distant [[group]]s are [[connection|connected]]. These rules were published by [[Vadim Anshelevich]] in 2000 and 2002, see the references below. Anshelevich 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.
+
== Connections and semi-connections ==
  
−
== AND Rule==
+
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.
  
−
Consider a pair of virtual connections who share one extremity. If the [[carrier]]s do not intersect, then the following may be deduced:
+
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'''.
−
* 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>
+
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.
  
−
== OR Rule ==
+
Here are some examples of virtual connections between ''x'' and ''y'':
  
−
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.
+
<hexboard size="2x2"
 +
  edges="none"
 +
  coords="none"
 +
  float="inline"
 +
  contents="E x:a1 y:b2"
 +
/> <hexboard size="3x3"
 +
  edges="none"
 +
  coords="none"
 +
  float="inline"
 +
  visible="-a1"
 +
  contents="R x:b1 a2 a3 y:c3"
 +
/> <hexboard size="6x6"
 +
  edges="none"
 +
  coords="none"
 +
  float="inline"
 +
  visible="-area(a1,a4,c1)-area(f6,f4,e6)"
 +
  contents="E x:a5 R b6 d4 d6 e4 c2 e1 y:f2 B c4 d3 e3"
 +
/>
  
−
<hex> R4 C4 Vb2 Sc2
+
And here are some examples of semi-connections:
−
            Sb3 Vc3 </hex>
+
  
−
== Completeness ==
+
<hexboard size="1x3"
 +
  edges="none"
 +
  coords="none"
 +
  float="inline"
 +
  contents="E x:a1 y:c1"
 +
/> <hexboard size="3x3"
 +
  edges="none"
 +
  coords="none"
 +
  float="inline"
 +
  visible="-a1"
 +
  contents="R x:b1 a2 a3 y:c3 B c1"
 +
/> <hexboard size="6x6"
 +
  edges="none"
 +
  coords="none"
 +
  float="inline"
 +
  visible="-area(a1,a4,c1)-area(f6,f4,e6)"
 +
  contents="E x:a5 R b6 d6 e4 c2 e1 y:f2 B c4 d3 e3"
 +
/>
  
−
Anshelevich showed that not every virtual connection could be induced using the rules.
+
Schematically, we will represent a virtual connection by a red box, and a semi-connection by a white box, like this:
 +
[[Image: Connections.png|217px]]
  
−
However the rules can be [[generalised AND and OR rules|generalised]] in such a way that makes them complete.
+
== AND rule ==
  
−
== [[Complexity]] ==
+
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).
−
== 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 ==
+
The AND rule states that the connection from ''x'' to ''z'' is:
 +
 
 +
* A virtual connection if ''E''₁ and ''E''₂ are virtual connections and ''y'' is occupied by Red.
 +
 
 +
* A semi-connection if ''E''₁ and ''E''₂ are virtual connections and ''y'' is empty.
 +
 
 +
* A semi-connection if one of ''E''₁ and ''E''₂ is a virtual connection, the other a semi-connection, and ''y'' is red.
 +
 
 +
In pictures:
 +
 
 +
[[Image: And-rule.png|669px]]
 +
 
 +
 
 +
== OR rule ==
 +
 
 +
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''.
 +
 
 +
In pictures:
 +
 
 +
[[Image: Or-rule.png|550px]]
 +
 
 +
== Application of the rules ==
 +
 
 +
The rules can be applied repeatedly. The simplest kind of virtual connection is when two cells are directly next to each other.
 +
<hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  visible="a3 a2"
 +
  contents="R x:a3 E y:a2"
 +
  />
 +
By the AND rule, we get a semi-connection from ''x'' to ''z'':
 +
<hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 a2"
 +
  contents="R x:a3 E y:a2"
 +
/> AND <hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a2 b1"
 +
  contents="E y:a2 R z:b1"
 +
/> = <hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 a2 b1"
 +
  contents="R x:a3 E y:a2 R z:b1"
 +
/>
 +
Combining this with another semi-connection, we get a virtual connection from ''x'' to ''z'' by the OR rule:
 +
<hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 a2 b1"
 +
  contents="R x:a3 R z:b1"
 +
/> OR <hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 b2 b1"
 +
  contents="R x:a3 R z:b1"
 +
/> = <hexboard size="3x2"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 a2 b2 b1"
 +
  contents="R x:a3 R z:b1"
 +
/>
 +
By the AND rule, we get a semi-connection from ''a'' to ''z'':
 +
<hexboard size="3x4"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 b3 c3"
 +
  contents="R a:a3 R x:c3"
 +
/> AND <hexboard size="3x4"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="c3 c2 d2 d1"
 +
  contents="R x:c3 R z:d1"
 +
/> = <hexboard size="3x4"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 b3 c3 c2 d2 d1"
 +
  contents="R a:a3 R x:c3 R z:d1"
 +
/>
 +
Combining this with another semi-connection by the OR rule, we get a virtual connection from ''a'' to ''z'':
 +
<hexboard size="3x4"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 b3 c3 c2 d2 d1"
 +
  contents="R a:a3 R c3 R z:d1"
 +
/> OR <hexboard size="3x4"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 b2 c1 d1"
 +
  contents="R a:a3 R c1 R z:d1"
 +
/> = <hexboard size="3x4"
 +
  coords="none"
 +
  edges="none"
 +
  float="inline"
 +
  visible="a3 b2 c1 b3 c3 c2 d2 d1"
 +
  contents="R a:a3 R c1 R c3 R z:d1"
 +
/>
 +
Continuing in this manner, very large virtual connections can be constructed.
 +
 
 +
== Incompleteness ==
 +
 
 +
The AND and OR rules are not complete. Specifically, there are some virtual (or semi-) connections that cannot be proven to be virtual (or semi-) connections by the AND and OR rules from smaller connections. Perhaps the simplest example is the following:
 +
<hexboard size="5x5"
 +
  coords="none"
 +
  edges="none"
 +
  visible="area(a3,a4,b5,c5,e3,e2,d1,c1)"
 +
  contents="R a4--a3--c1 e2--e3--c5 B b3 c2 c4 d3 R x:a3 y:e3 E a:b4 b:d2"
 +
/>
 +
It is a semi-connection (Red makes the connection by playing at ''a'' and ''b'', in either order). However, it cannot be proven to be a semi-connection by the AND and OR rules.
 +
 
 +
Anshelevich gave a generalization of the AND and OR rules that is complete. However, that generalization requires the computation of handicap sets (sets of cells) and is computationally harder.
 +
 
 +
== Use in computer Hex ==
 +
 
 +
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 ==
  
−
*[[HSearch]]
 
 
*[[Six]]
 
*[[Six]]
  
−
==External link==
+
== References ==
 +
 
 +
* Anshelevich, Vadim V. [https://www.aaai.org/Papers/AAAI/2000/AAAI00-029.pdf The Game of Hex: An Automatic Theorem Proving Approach to Game Programming]. In Proceedings of the 17th National Conference on Artificial Intelligence, Austin Texas, 2000.
 +
* Anshelevich, Vadim V. [http://home.earthlink.net/~vanshel/VAnshelevich-ARTINT.pdf  A hierarichical approach to computer Hex]. See section 3.
 +
* [[Jack van Rijswijck]].[http://hex.kosmanor.com/theory/y-hex.pdf Search and evaluation in Hex]. See section 2.1.
 +
 
 +
== External links ==
  
−
* [[Jack van Rijswijck]].[http://home.fuse.net/swmeyers/y-hex.pdf Search and evaluation in Hex]. See paragraph 2.1.
+
* Vadim Anshelevich's [http://home.earthlink.net/~vanshel/Publications.html publications page]. Some publications dealing with virtual connections and the And and Or rules.
−
* 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]]
 
[[category:Theory]]
−
{{stub}}
 

Revision as of 02:38, 17 December 2021

The AND and OR rules are deduction rules that can be used to build virtual connections and semi-connections. They often make it possible to compute whether two distant groups are connected. These rules were published by Vadim Anshelevich in 2000 and 2002, see the references below. Anshelevich used these rules in his program Hexy.

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.

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.

Here are some examples of virtual connections between x and y:

xy
xy
yx

And here are some examples of semi-connections:

xy
xy
yx

Schematically, we will represent a virtual connection by a red box, and a semi-connection by a white box, like this: Connections.png

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 states that the connection from x to z is:

  • A virtual connection if E₁ and E₂ are virtual connections and y is occupied by Red.
  • A semi-connection if E₁ and E₂ are virtual connections and y is empty.
  • A semi-connection if one of E₁ and E₂ is a virtual connection, the other a semi-connection, and y is red.

In pictures:

And-rule.png


OR rule

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.

In pictures:

Or-rule.png

Application of the rules

The rules can be applied repeatedly. The simplest kind of virtual connection is when two cells are directly next to each other.

yx

By the AND rule, we get a semi-connection from x to z:

yx
AND
zy
=
zyx

Combining this with another semi-connection, we get a virtual connection from x to z by the OR rule:

zx
OR
zx
=
zx

By the AND rule, we get a semi-connection from a to z:

ax
AND
zx
=
zax

Combining this with another semi-connection by the OR rule, we get a virtual connection from a to z:

za
OR
za
=
za

Continuing in this manner, very large virtual connections can be constructed.

Incompleteness

The AND and OR rules are not complete. Specifically, there are some virtual (or semi-) connections that cannot be proven to be virtual (or semi-) connections by the AND and OR rules from smaller connections. Perhaps the simplest example is the following:

bxya

It is a semi-connection (Red makes the connection by playing at a and b, in either order). However, it cannot be proven to be a semi-connection by the AND and OR rules.

Anshelevich gave a generalization of the AND and OR rules that is complete. However, that generalization requires the computation of handicap sets (sets of cells) and is computationally harder.

Use in computer Hex

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

References

External links

  • Vadim Anshelevich's publications page. Some publications dealing with virtual connections and the And and Or rules.
Retrieved from "https://www.hexwiki.net/index.php?title=AND_and_OR_rules&oldid=7597"