25,161
edits
Changes
Created page with "'''Home * Search * Type B Strategy''' The '''Type B Strategy''', proposed in 1949 by Claude Shannon in his groundbreaking publication ''Programming a Co..."
'''[[Main Page|Home]] * [[Search]] * Type B Strategy'''
The '''Type B Strategy''', proposed in 1949 by [[Claude Shannon]] in his groundbreaking publication ''Programming a Computer for Playing Chess'' <ref>[[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf]</ref>, is a [[Selectivity|selective]] approach to search [[Minimax|minimax]] [[Search Tree|trees]] considering only a subset of plausible moves in contrast to the [[Brute-Force|brute-force]] [[Type A Strategy|Type A strategy]].
=Quotes=
from Shannon's ''Programming a Computer for Playing Chess'':
From these remarks it appears that to improve the speed and strength of play the machine must:
# <code>Examine forceful variations out as far as possible and evaluate only at reasonable positions, where some quasi-stability has been established.</code>
# <code>Select the variations to be explored by some process so that the machine does not waste its time in totally pointless variations.</code>
A strategy with these two improvements will be called a type B strategy. It is not difficult to construct programs incorporating these features. For the first we define a function g(P) of a position which determines whether approximate stability exists (no pieces en prise, etc.). A crude definition might be:
<pre>
| 1 if any piece is attacked by a piece of lower value,
g(P) = / or by more pieces then defences of if any check exists
\ on a square controlled by opponent.
| 0 otherwise.
</pre>
Using this function, variations could be explored until g(P)=0, always, however, going at least two moves and never more say, 10.
=Type B programs=
Most early chess programs were Type B and used a selective '''width''' for a maximum amount of plausible moves to be tried. [[Alex Bernstein|Bernstein]] used {7, 7, 7, 7}, later programs chose width dependent from [[Depth|depth]], [[Kotok-McCarthy-Program|Kotok-McCarthy]] had {4, 3, 2, 2, 1, 1, 1, 1, 0, 0}, while [[Richard Greenblatt|Greenblatt's]] [[Mac Hack]] used {15, 15, 9, 9, 7, ...}, and [[CHAOS]] carried out a selective search with iterative widening. With the advent of brute-force [[Alpha-Beta|alpha-beta]], and programs like [[Tech]], [[Kaissa]] and [[Chess (Program)|Chess 4.5]] in the early 70s, the era of the former dominating Type B programs drew to a close. Today most programs are closer to Type A, but have some characteristics of a Type B due to [[Selectivity|selectivity]].
* [[Awit]]
* [[Black Knight]]
* [[Blitz]]
* [[CHAOS]]
* [[Chess Simulator]]
* [[Coko]]
* [[Genie]]
* [[Kotok-McCarthy-Program]]
* [[Mac Hack]]
* [[MAX (Gillogly)]]
* [[NSS]]
* [[Schach (US)]]
* [[The Bernstein Chess Program]]
and
* [[Chess (Program)|Chess < 4.0]]
=See also=
* [[Alpha-Beta]]
* [[Brute-Force]]
* [[Minimax]]
* [[Selectivity]]
* [[Type A Strategy|Shannon's Type A Strategy]]
=External Links=
* [http://www.mathematik.uni-bielefeld.de/%7Esillke/NEWS/brute-force Subject: brute-force vs. intuition in math & chess] by [https://en.wikipedia.org/wiki/Macsyma Bill Dubuque], August 1996
* [https://en.wikipedia.org/wiki/Brute-force_search Brute-force search from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
The '''Type B Strategy''', proposed in 1949 by [[Claude Shannon]] in his groundbreaking publication ''Programming a Computer for Playing Chess'' <ref>[[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf]</ref>, is a [[Selectivity|selective]] approach to search [[Minimax|minimax]] [[Search Tree|trees]] considering only a subset of plausible moves in contrast to the [[Brute-Force|brute-force]] [[Type A Strategy|Type A strategy]].
=Quotes=
from Shannon's ''Programming a Computer for Playing Chess'':
From these remarks it appears that to improve the speed and strength of play the machine must:
# <code>Examine forceful variations out as far as possible and evaluate only at reasonable positions, where some quasi-stability has been established.</code>
# <code>Select the variations to be explored by some process so that the machine does not waste its time in totally pointless variations.</code>
A strategy with these two improvements will be called a type B strategy. It is not difficult to construct programs incorporating these features. For the first we define a function g(P) of a position which determines whether approximate stability exists (no pieces en prise, etc.). A crude definition might be:
<pre>
| 1 if any piece is attacked by a piece of lower value,
g(P) = / or by more pieces then defences of if any check exists
\ on a square controlled by opponent.
| 0 otherwise.
</pre>
Using this function, variations could be explored until g(P)=0, always, however, going at least two moves and never more say, 10.
=Type B programs=
Most early chess programs were Type B and used a selective '''width''' for a maximum amount of plausible moves to be tried. [[Alex Bernstein|Bernstein]] used {7, 7, 7, 7}, later programs chose width dependent from [[Depth|depth]], [[Kotok-McCarthy-Program|Kotok-McCarthy]] had {4, 3, 2, 2, 1, 1, 1, 1, 0, 0}, while [[Richard Greenblatt|Greenblatt's]] [[Mac Hack]] used {15, 15, 9, 9, 7, ...}, and [[CHAOS]] carried out a selective search with iterative widening. With the advent of brute-force [[Alpha-Beta|alpha-beta]], and programs like [[Tech]], [[Kaissa]] and [[Chess (Program)|Chess 4.5]] in the early 70s, the era of the former dominating Type B programs drew to a close. Today most programs are closer to Type A, but have some characteristics of a Type B due to [[Selectivity|selectivity]].
* [[Awit]]
* [[Black Knight]]
* [[Blitz]]
* [[CHAOS]]
* [[Chess Simulator]]
* [[Coko]]
* [[Genie]]
* [[Kotok-McCarthy-Program]]
* [[Mac Hack]]
* [[MAX (Gillogly)]]
* [[NSS]]
* [[Schach (US)]]
* [[The Bernstein Chess Program]]
and
* [[Chess (Program)|Chess < 4.0]]
=See also=
* [[Alpha-Beta]]
* [[Brute-Force]]
* [[Minimax]]
* [[Selectivity]]
* [[Type A Strategy|Shannon's Type A Strategy]]
=External Links=
* [http://www.mathematik.uni-bielefeld.de/%7Esillke/NEWS/brute-force Subject: brute-force vs. intuition in math & chess] by [https://en.wikipedia.org/wiki/Macsyma Bill Dubuque], August 1996
* [https://en.wikipedia.org/wiki/Brute-force_search Brute-force search from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
