25,161
edits
Changes
Created page with "'''Home * People * Walter Faxon''' '''Walter G. Faxon''', and American chess player, computer scientist and one of the pioneers in scanning bits..."
'''[[Main Page|Home]] * [[People]] * Walter Faxon'''
'''Walter G. Faxon''',
and American chess player, computer scientist and one of the pioneers in [[BitScan|scanning bits]]. His [[BitScan#WalterFaxonsmagicBitscan|magic bitscan]], invented in the 80s is still one of the most competitive on 32-bit architectures . On June 09, 2003 Walter made a thought-provoking appeal in [[CCC]].
=Selected Games=
During the 1970 [https://en.wikipedia.org/wiki/Scholastic_chess_in_the_United_States U.S. High School Championship] at the [https://en.wikipedia.org/wiki/Hotel_McAlpin Hotel McAlpin], [https://en.wikipedia.org/wiki/New_York_City New York City],
Walter Faxon of the winning team from [https://en.wikipedia.org/wiki/Brookline,_Massachusetts Brookline, Massachusetts] scored 6-2.
His game versus [[Danny Kopec]] representing [https://en.wikipedia.org/wiki/Jamaica_High_School Jamaica High, N. Y.] was published in [https://en.wikipedia.org/wiki/Israel_Albert_Horowitz Al Horowitz'] chess colums of the [https://en.wikipedia.org/wiki/The_New_York_Times The New York Times] <ref>[https://www.nytimes.com/1970/06/07/archives/chess-brookline-wins-high-school-event.html Chess] by [https://en.wikipedia.org/wiki/Israel_Albert_Horowitz Al Horowitz], [https://en.wikipedia.org/wiki/The_New_York_Times The New York Times], June 7, 1970</ref>:
<pre>
[Event "U.S. High School championship"]
[Site "New York City, NY"]
[Date "1970.05.??"]
[Round "?"]
[White "Danny Kopec"]
[Black "Walter Faxon"]
[Result "1/2 - 1/2"]
1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.c3 Nf6 5.Bb5+ Bd7 6.Bxd7+ Nbxd7 7.Qxd4 g6
8.O-O Bg7 9.Bg5 O-O 10.Qe3 h6 11.Bf4 Qb6 12.Qxb6 Nxb6 13.Nbd2 Rac8 14.Rfd1
Nc4 15.Nxc4 Rxc4 16.Nd2 Rcc8 17.f3 d5 18.Be3 b6 19.e5 Nd7 20.f4 e6 21.a4 f6
22.exf6 Nxf6 23.h3 Nh5 24.Rf1 Ng3 25.Rfe1 Nf5 26.Bf2 d4 27.Ne4 dxc3 28.Nxc3
Rxc3 29.bxc3 Bxc3 30.Rac1 Bxe1 31.Bxe1 Ne3 32.Rc7 Rf7 33.Rc8+ Rf8 34.Rc7 Rf7
35.Rc8+ Rf8 36.Rc6 Rxf4 37.Bd2 Re4 38.Rc8+ Kf7 39.Rc7+ Kf6 40.Rxa7 g5 41.Bc3+
e5 42.Rd7 Rxa4 43.Rd6+ Kf5 1/2-1/2
</pre>
=Magic BitScan=
Walter Faxon's 32-bit friendly [[BitScan#WalterFaxonsmagicBitscan|magic bitscan]] <ref>[https://www.stmintz.com/ccc/index.php?id=265635 Another hacky method for bitboard bit extraction] by [[Walter Faxon]], [[CCC]], November 17, 2002</ref> uses a fast none minimal [[Hash Table#PerfectHashing|perfect hashing]] function:
<pre>
const char LSB_64_table[154] =
{
#define __ 0
22,__,__,__,30,__,__,38,18,__, 16,15,17,__,46, 9,19, 8, 7,10,
0, 63, 1,56,55,57, 2,11,__,58, __,__,20,__, 3,__,__,59,__,__,
__,__,__,12,__,__,__,__,__,__, 4,__,__,60,__,__,__,__,__,__,
__,__,__,__,21,__,__,__,29,__, __,37,__,__,__,13,__,__,45,__,
__,__, 5,__,__,61,__,__,__,53, __,__,__,__,__,__,__,__,__,__,
28,__,__,36,__,__,__,__,__,__, 44,__,__,__,__,__,27,__,__,35,
__,52,__,__,26,__,43,34,25,23, 24,33,31,32,42,39,40,51,41,14,
__,49,47,48,__,50, 6,__,__,62, __,__,__,54
#undef __
};
/**
* bitScanForward
* @author Walter Faxon, slightly modified
* @param bb bitboard to scan
* @precondition bb != 0
* @return index (0..63) of least significant one bit
*/
int bitScanForward(U64 bb)
{
unsigned int t32;
assert(bb);
bb ^= bb - 1;
t32 = (int)bb ^ (int)(bb >> 32);
t32 ^= 0x01C5FC81;
t32 += t32 >> 16;
t32 -= (t32 >> 8) + 51;
return LSB_64_table [t32 & 255]; // 0..63
}
</pre>
=Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner=
<ref>[https://www.stmintz.com/ccc/index.php?id=299987 Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner] by [[Walter Faxon]], [[CCC]], June 09, 2003</ref>
Musings on nonstandard computer chess techniques.
What's new on the computer chess front? I note that [[Sergei Markoff|Sergei S. Markoff's]] new program [[SmarThink]] (http:''www.aigroup.narod.ru/detailse.htm) is supposed to use (among many other things) some of former world chess champion [[Mikhail Botvinnik|M.M. Botvinnik's]] ideas. Botvinnik's "Computers, Chess and Long-Range Planning" (Springer, 1970) and "Chess: Solving Inexact Search Problems" (Springer, 1983) described a method that apparently only Botvinnik's programmer/protege [[Boris Stilman]] believed would work, which Stilman later generalized in his own book "Linguistic Geometry: From Search to Construction" (Kluwer, 2000). Markoff's own on-line writings on chess algorithms (http:''www.aigroup.narod.ru/indexe.htm) are only in Russian, so far. (I am assuming that the SmarThink download doesn't include source.)
Markoff also writes that his first program included ideas from the authors of [[Kaissa]]. Those authors published papers in the 1970's on "the method of analogies" to reduce search work, but they did not use it in their competitive program. If you recall, [[Feng-hsiung Hsu|Hsu]] wrote in "Behind Deep Blue" (Princeton Univ. Pr., 2002) that he had implemented a stripped-down version of the analogies method for [[Deep Blue]]. It is the unpublished intellectual property of IBM.
Sometimes I wonder if chess program authors mention intriguing nonsense just to throw their competitors off the track. I recall someone once letting slip that he had used Botvinnik's method for an early hardware-limited microcomputer program. That seems unlikely. Nearly 15 years ago an author ([[David Kittinger|Kittinger]]?) dropped hints that he had adopted [[David McAllester|McAllester's]] 1988 method [[Conspiracy Number Search|conspiracy numbersearch]] (aka conspiracy search) for his program, using the term "nodulation". Published results indicate that plain conspiracy numbers don't work very well for chess. As far as I know, today only experiments on multiprocessor machines are being conducted; no competitive microcomputer program uses it at all. So was it a mirage -- or a trick? David McAllester and [[Deniz Yuret]] did finally publish their revised work ([[Alpha-Beta Conspiracy Search]]. [[ICGA Journal]], Vol. 25, No. 1 (March 2002), pp. 16-35), nearly ten years after their initial experiments with the multiprocessor program [[Star Socrates|Star-Socrates]]. And ten years from now?...
And what about [[Hans Berliner|Berliner's]] [[B*]] algorithm? (Actually [[Andrew James Palay|Palay's]] probabilistic B* using a probability distribution for evaluation instead of a simple range, today suggestive that techniques from fuzzy logic might be applied.) The chess machine [[HiTech|Hitech]] was originally built for it in the early 1980's (equal first on points but second on tiebreak, [[WCCC 1986]]) -- and finally began using it. As of mid-1993 it was "almost as good as regular Hitech". In mid-1995 it was still "not quite as good as brute force searching." In the abstract of his last word on the subject (Hans J. Berliner and [[Chris McConnell]]. B* probability based search. Artificial Intelligence, Volume 86, Issue 1, September 1996, Pages 97-156) Berliner writes, "Analysis of the data indicates that should additional power become available, the B* technique will scale up considerably better than brute-force techniques." Berliner is now retired. More power is available. Where are the later papers? Where is B* today?
My suggestion: you are writing a chess program. Go ahead, put in [[negascout]], [[Null Move Pruning|null-move pruning]], [[Internal Iterative Deepening|IID]], everything everybody is already doing. Then, look to the literature and find some method that everybody is _not_ doing. Implement it, experiment with it, and _publish_ your results. Please.
- Walter
=No Go=
(was Re: Markoff -- Botvinnik -- Kaissa -- Hsu -- ABC -- Berliner) <ref>[https://www.stmintz.com/ccc/index.php?id=300412 No Go (was Re: Markoff -- Botvinnik -- Kaissa -- Hsu -- ABC -- Berliner)] by [[Walter Faxon]], [[CCC]], June 11, 2003</ref>
... I have been from time-to-time disappointed that there is not more AI content on CCC. It very much seems to be a hobbyist board, playing with the current programs and building duplicates of them, albeit with minor differences in emphasis and implementation. I've been guilty of this myself in the bitscan threads. But the few times I have tried to raise the level of discussion have been met with, mostly, silence. My last post was to an extent, a "last gasp".
=Forum Posts=
==2002 ...==
* [https://www.stmintz.com/ccc/index.php?id=265635 Another hacky method for bitboard bit extraction] by [[Walter Faxon]], [[CCC]], November 17, 2002
* [https://www.stmintz.com/ccc/index.php?id=272454 Re: Bit Scan Timings -- possible artifact?] by [[Walter Faxon]], [[CCC]], December 22, 2002
* [https://www.stmintz.com/ccc/index.php?id=273932 Re: Beating Bitscan to Death -- yet again] by [[Walter Faxon]], [[CCC]], December 30, 2002
* [https://www.stmintz.com/ccc/index.php?id=275418 Re: Computer Chess Went The Wrong Way...] by [[Walter Faxon]], [[CCC]], January 07, 2003
* [https://www.stmintz.com/ccc/index.php?id=299987 Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner] by [[Walter Faxon]], [[CCC]], June 09, 2003
* [https://www.stmintz.com/ccc/index.php?id=322847 65 bits!] by [[Walter Faxon]], [[CCC]], October 21, 2003
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=407324 Steven Edwards & Symbolic] by [[Walter Faxon]], [[CCC]], January 24, 2005 » [[Symbolic]]
* [https://www.stmintz.com/ccc/index.php?id=417664 Old chess program in BASIC (long post)] by [[Walter Faxon]], [[CCC]], March 20, 2005 » [[Basic]]
* [https://www.stmintz.com/ccc/index.php?id=419898 What do you do in "hard" positions?] by [[Walter Faxon]], [[CCC]], April 06, 2005
* [https://www.stmintz.com/ccc/index.php?id=420763 Quantum computing and chess] by [[Walter Faxon]], [[CCC]], April 13, 2005
* [https://www.stmintz.com/ccc/index.php?id=424608 (Obvious troll) Kasparov vs DB-I was a disaster for human chess] by [[Walter Faxon]], [[CCC]], May 06, 2005 » [[Deep Blue]]
=External Links=
* [http://www.chessgames.com/perl/chessplayer?pid=153699 The chess games of Walter G Faxon] from [http://www.chessgames.com/index.html chessgames.com]
* [http://www.chessgames.com/perl/chesscollection?cid=1020934 US Open 1970, Boston], [http://www.chessgames.com/index.html chessgames.com]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Chess Player|Faxon]]
[[Category:Programmer|Faxon]]
'''Walter G. Faxon''',
and American chess player, computer scientist and one of the pioneers in [[BitScan|scanning bits]]. His [[BitScan#WalterFaxonsmagicBitscan|magic bitscan]], invented in the 80s is still one of the most competitive on 32-bit architectures . On June 09, 2003 Walter made a thought-provoking appeal in [[CCC]].
=Selected Games=
During the 1970 [https://en.wikipedia.org/wiki/Scholastic_chess_in_the_United_States U.S. High School Championship] at the [https://en.wikipedia.org/wiki/Hotel_McAlpin Hotel McAlpin], [https://en.wikipedia.org/wiki/New_York_City New York City],
Walter Faxon of the winning team from [https://en.wikipedia.org/wiki/Brookline,_Massachusetts Brookline, Massachusetts] scored 6-2.
His game versus [[Danny Kopec]] representing [https://en.wikipedia.org/wiki/Jamaica_High_School Jamaica High, N. Y.] was published in [https://en.wikipedia.org/wiki/Israel_Albert_Horowitz Al Horowitz'] chess colums of the [https://en.wikipedia.org/wiki/The_New_York_Times The New York Times] <ref>[https://www.nytimes.com/1970/06/07/archives/chess-brookline-wins-high-school-event.html Chess] by [https://en.wikipedia.org/wiki/Israel_Albert_Horowitz Al Horowitz], [https://en.wikipedia.org/wiki/The_New_York_Times The New York Times], June 7, 1970</ref>:
<pre>
[Event "U.S. High School championship"]
[Site "New York City, NY"]
[Date "1970.05.??"]
[Round "?"]
[White "Danny Kopec"]
[Black "Walter Faxon"]
[Result "1/2 - 1/2"]
1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.c3 Nf6 5.Bb5+ Bd7 6.Bxd7+ Nbxd7 7.Qxd4 g6
8.O-O Bg7 9.Bg5 O-O 10.Qe3 h6 11.Bf4 Qb6 12.Qxb6 Nxb6 13.Nbd2 Rac8 14.Rfd1
Nc4 15.Nxc4 Rxc4 16.Nd2 Rcc8 17.f3 d5 18.Be3 b6 19.e5 Nd7 20.f4 e6 21.a4 f6
22.exf6 Nxf6 23.h3 Nh5 24.Rf1 Ng3 25.Rfe1 Nf5 26.Bf2 d4 27.Ne4 dxc3 28.Nxc3
Rxc3 29.bxc3 Bxc3 30.Rac1 Bxe1 31.Bxe1 Ne3 32.Rc7 Rf7 33.Rc8+ Rf8 34.Rc7 Rf7
35.Rc8+ Rf8 36.Rc6 Rxf4 37.Bd2 Re4 38.Rc8+ Kf7 39.Rc7+ Kf6 40.Rxa7 g5 41.Bc3+
e5 42.Rd7 Rxa4 43.Rd6+ Kf5 1/2-1/2
</pre>
=Magic BitScan=
Walter Faxon's 32-bit friendly [[BitScan#WalterFaxonsmagicBitscan|magic bitscan]] <ref>[https://www.stmintz.com/ccc/index.php?id=265635 Another hacky method for bitboard bit extraction] by [[Walter Faxon]], [[CCC]], November 17, 2002</ref> uses a fast none minimal [[Hash Table#PerfectHashing|perfect hashing]] function:
<pre>
const char LSB_64_table[154] =
{
#define __ 0
22,__,__,__,30,__,__,38,18,__, 16,15,17,__,46, 9,19, 8, 7,10,
0, 63, 1,56,55,57, 2,11,__,58, __,__,20,__, 3,__,__,59,__,__,
__,__,__,12,__,__,__,__,__,__, 4,__,__,60,__,__,__,__,__,__,
__,__,__,__,21,__,__,__,29,__, __,37,__,__,__,13,__,__,45,__,
__,__, 5,__,__,61,__,__,__,53, __,__,__,__,__,__,__,__,__,__,
28,__,__,36,__,__,__,__,__,__, 44,__,__,__,__,__,27,__,__,35,
__,52,__,__,26,__,43,34,25,23, 24,33,31,32,42,39,40,51,41,14,
__,49,47,48,__,50, 6,__,__,62, __,__,__,54
#undef __
};
/**
* bitScanForward
* @author Walter Faxon, slightly modified
* @param bb bitboard to scan
* @precondition bb != 0
* @return index (0..63) of least significant one bit
*/
int bitScanForward(U64 bb)
{
unsigned int t32;
assert(bb);
bb ^= bb - 1;
t32 = (int)bb ^ (int)(bb >> 32);
t32 ^= 0x01C5FC81;
t32 += t32 >> 16;
t32 -= (t32 >> 8) + 51;
return LSB_64_table [t32 & 255]; // 0..63
}
</pre>
=Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner=
<ref>[https://www.stmintz.com/ccc/index.php?id=299987 Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner] by [[Walter Faxon]], [[CCC]], June 09, 2003</ref>
Musings on nonstandard computer chess techniques.
What's new on the computer chess front? I note that [[Sergei Markoff|Sergei S. Markoff's]] new program [[SmarThink]] (http:''www.aigroup.narod.ru/detailse.htm) is supposed to use (among many other things) some of former world chess champion [[Mikhail Botvinnik|M.M. Botvinnik's]] ideas. Botvinnik's "Computers, Chess and Long-Range Planning" (Springer, 1970) and "Chess: Solving Inexact Search Problems" (Springer, 1983) described a method that apparently only Botvinnik's programmer/protege [[Boris Stilman]] believed would work, which Stilman later generalized in his own book "Linguistic Geometry: From Search to Construction" (Kluwer, 2000). Markoff's own on-line writings on chess algorithms (http:''www.aigroup.narod.ru/indexe.htm) are only in Russian, so far. (I am assuming that the SmarThink download doesn't include source.)
Markoff also writes that his first program included ideas from the authors of [[Kaissa]]. Those authors published papers in the 1970's on "the method of analogies" to reduce search work, but they did not use it in their competitive program. If you recall, [[Feng-hsiung Hsu|Hsu]] wrote in "Behind Deep Blue" (Princeton Univ. Pr., 2002) that he had implemented a stripped-down version of the analogies method for [[Deep Blue]]. It is the unpublished intellectual property of IBM.
Sometimes I wonder if chess program authors mention intriguing nonsense just to throw their competitors off the track. I recall someone once letting slip that he had used Botvinnik's method for an early hardware-limited microcomputer program. That seems unlikely. Nearly 15 years ago an author ([[David Kittinger|Kittinger]]?) dropped hints that he had adopted [[David McAllester|McAllester's]] 1988 method [[Conspiracy Number Search|conspiracy numbersearch]] (aka conspiracy search) for his program, using the term "nodulation". Published results indicate that plain conspiracy numbers don't work very well for chess. As far as I know, today only experiments on multiprocessor machines are being conducted; no competitive microcomputer program uses it at all. So was it a mirage -- or a trick? David McAllester and [[Deniz Yuret]] did finally publish their revised work ([[Alpha-Beta Conspiracy Search]]. [[ICGA Journal]], Vol. 25, No. 1 (March 2002), pp. 16-35), nearly ten years after their initial experiments with the multiprocessor program [[Star Socrates|Star-Socrates]]. And ten years from now?...
And what about [[Hans Berliner|Berliner's]] [[B*]] algorithm? (Actually [[Andrew James Palay|Palay's]] probabilistic B* using a probability distribution for evaluation instead of a simple range, today suggestive that techniques from fuzzy logic might be applied.) The chess machine [[HiTech|Hitech]] was originally built for it in the early 1980's (equal first on points but second on tiebreak, [[WCCC 1986]]) -- and finally began using it. As of mid-1993 it was "almost as good as regular Hitech". In mid-1995 it was still "not quite as good as brute force searching." In the abstract of his last word on the subject (Hans J. Berliner and [[Chris McConnell]]. B* probability based search. Artificial Intelligence, Volume 86, Issue 1, September 1996, Pages 97-156) Berliner writes, "Analysis of the data indicates that should additional power become available, the B* technique will scale up considerably better than brute-force techniques." Berliner is now retired. More power is available. Where are the later papers? Where is B* today?
My suggestion: you are writing a chess program. Go ahead, put in [[negascout]], [[Null Move Pruning|null-move pruning]], [[Internal Iterative Deepening|IID]], everything everybody is already doing. Then, look to the literature and find some method that everybody is _not_ doing. Implement it, experiment with it, and _publish_ your results. Please.
- Walter
=No Go=
(was Re: Markoff -- Botvinnik -- Kaissa -- Hsu -- ABC -- Berliner) <ref>[https://www.stmintz.com/ccc/index.php?id=300412 No Go (was Re: Markoff -- Botvinnik -- Kaissa -- Hsu -- ABC -- Berliner)] by [[Walter Faxon]], [[CCC]], June 11, 2003</ref>
... I have been from time-to-time disappointed that there is not more AI content on CCC. It very much seems to be a hobbyist board, playing with the current programs and building duplicates of them, albeit with minor differences in emphasis and implementation. I've been guilty of this myself in the bitscan threads. But the few times I have tried to raise the level of discussion have been met with, mostly, silence. My last post was to an extent, a "last gasp".
=Forum Posts=
==2002 ...==
* [https://www.stmintz.com/ccc/index.php?id=265635 Another hacky method for bitboard bit extraction] by [[Walter Faxon]], [[CCC]], November 17, 2002
* [https://www.stmintz.com/ccc/index.php?id=272454 Re: Bit Scan Timings -- possible artifact?] by [[Walter Faxon]], [[CCC]], December 22, 2002
* [https://www.stmintz.com/ccc/index.php?id=273932 Re: Beating Bitscan to Death -- yet again] by [[Walter Faxon]], [[CCC]], December 30, 2002
* [https://www.stmintz.com/ccc/index.php?id=275418 Re: Computer Chess Went The Wrong Way...] by [[Walter Faxon]], [[CCC]], January 07, 2003
* [https://www.stmintz.com/ccc/index.php?id=299987 Markoff - Botvinnik - Kaissa - Hsu - ABC - Berliner] by [[Walter Faxon]], [[CCC]], June 09, 2003
* [https://www.stmintz.com/ccc/index.php?id=322847 65 bits!] by [[Walter Faxon]], [[CCC]], October 21, 2003
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=407324 Steven Edwards & Symbolic] by [[Walter Faxon]], [[CCC]], January 24, 2005 » [[Symbolic]]
* [https://www.stmintz.com/ccc/index.php?id=417664 Old chess program in BASIC (long post)] by [[Walter Faxon]], [[CCC]], March 20, 2005 » [[Basic]]
* [https://www.stmintz.com/ccc/index.php?id=419898 What do you do in "hard" positions?] by [[Walter Faxon]], [[CCC]], April 06, 2005
* [https://www.stmintz.com/ccc/index.php?id=420763 Quantum computing and chess] by [[Walter Faxon]], [[CCC]], April 13, 2005
* [https://www.stmintz.com/ccc/index.php?id=424608 (Obvious troll) Kasparov vs DB-I was a disaster for human chess] by [[Walter Faxon]], [[CCC]], May 06, 2005 » [[Deep Blue]]
=External Links=
* [http://www.chessgames.com/perl/chessplayer?pid=153699 The chess games of Walter G Faxon] from [http://www.chessgames.com/index.html chessgames.com]
* [http://www.chessgames.com/perl/chesscollection?cid=1020934 US Open 1970, Boston], [http://www.chessgames.com/index.html chessgames.com]
=References=
<references />
'''[[People|Up one level]]'''
[[Category:Chess Player|Faxon]]
[[Category:Programmer|Faxon]]
