25,161
edits
Changes
Created page with "'''Home * Engines * Huberman''' '''Huberman''', (Huberman's program)<br/> the Ph.D. thesis program by Barbara Liskov (née Huberman) written in Timeli..."
'''[[Main Page|Home]] * [[Engines]] * Huberman'''
'''Huberman''', (Huberman's program)<br/>
the Ph.D. thesis program by [[Barbara Liskov]] (née Huberman) written in [[Timeline#1968|1968]] at [[Stanford University]], under supervision of [[John McCarthy]], to play certain chess [[Endgame|endgames]] with pieces versus the lonesome king. Barbara Huberman used heuristics to drive the lonesome king away from the [[Center|center]] and for [[KBNK Endgame|K,B,N]] into the right corner, and most notably already proposed the [[Killer Heuristic]] for early refutations of the [[Alpha-Beta|alpha-beta]] search <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal|ICCA Journal]], Vol. 15, No. 1, pp. 8, The killer heuristic</ref>. She further elaborated on the implications of these endings with different board sizes, even an [[Infinite Board|infinite board]].
=Quotes=
[[Alex Bell]] in ''Games Playing with Computers'' on Huberman's program <ref>[[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p005.htm#index19 Chess programs: Huberman]</ref>:
A philosophic program was written by Barbara Huberman to specifically play end games. It was a research project on translating book descriptions of problem solving methods into program heuristics. It is well known that the following minimum combinations of pieces have a certain win against a lone king:
* K,Q
* [[KRK|K,R]]
* K,B,B
* [[KBNK Endgame|K,B,N]]
* K,N,N,N
The K,Q can be considered equivalent to the K,R.
Huberman followed descriptions (by [https://en.wikipedia.org/wiki/Jos%C3%A9_Ra%C3%BAl_Capablanca Capablanca] and [https://en.wikipedia.org/wiki/Reuben_Fine Fine]) of how to execute all but the case of K,N,N,N. The cases of K,R and K,B,B are feasible using the [[Minimax|minimax]] technique. This is not true for the [[KBNK Endgame|K,B,N]]. The difficulty here is that bishops and rooks can force mate on any size of board but the knight has a limited mobility (from a centre square there are five squares which each require four moves to be reached by the knight).
Consequently the K,B,N mate is not possible on a board of side > 8. Even allowing for the black king being against a side there is no way in which the K,B,N can be arranged and played that will systematically force the black king along the edge of an infinite board. Because of this weakness the actual mating can take up to forty moves. Huberman's model for the problem was a forcing tree co-ordinated with two functions (better and worse) which were able to compare positions. Roughly speaking the program had two sub-goals (apart from not losing a piece, giving [[Stalemate|stalemate]] , etc). First drive the king away from the centre and second, when the king is at the edge, drive him towards a corner of the bishop's colour.
Huberman's program is the only one which can perform this mating sequence for any starting position. It would be a useful addition to [[Mac Hack|Greenblatt's program]], being easily extended to solve other end games and hence giving the more general program a selection of sub-goals equivalent to winning the game. The problem of K,N,N,N is unlikely to occur; nevertheless it is of interest to the theorists. One surprising fact is that the combination can systematically drive the black king along the edge of an infinite board, and therefore the mating sequence is much easier to program.
=Publications=
* [[Barbara Liskov|Barbara J. Huberman]] ('''1968'''). ''A Program to Play Chess End Games''. Technical Report no. CS-106, Ph.D. thesis. [[Stanford University]], Computer Science Department
* [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p005.htm#index19 Chess programs: Huberman]
* [[John McCarthy]] ('''1990'''). ''Chess as the Drosophila of AI.'' [[Computers, Chess, and Cognition]], pp. 227-237 <ref>[[John McCarthy]] ('''1997'''). ''Chess as the Drosophila of AI''. Computer Science Department, [[Stanford University]], condensed version of the 1990 paper, [http://innovation.it.uts.edu.au/projectjmc/articles/drosophila/drosophila.pdf pdf]</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=197935 evaluating KNNN-K] by [[Rafael B. Andrist]], [[CCC]], November 18, 2001
=References=
<references />
'''[[Engines|Up one Level]]'''
'''Huberman''', (Huberman's program)<br/>
the Ph.D. thesis program by [[Barbara Liskov]] (née Huberman) written in [[Timeline#1968|1968]] at [[Stanford University]], under supervision of [[John McCarthy]], to play certain chess [[Endgame|endgames]] with pieces versus the lonesome king. Barbara Huberman used heuristics to drive the lonesome king away from the [[Center|center]] and for [[KBNK Endgame|K,B,N]] into the right corner, and most notably already proposed the [[Killer Heuristic]] for early refutations of the [[Alpha-Beta|alpha-beta]] search <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal|ICCA Journal]], Vol. 15, No. 1, pp. 8, The killer heuristic</ref>. She further elaborated on the implications of these endings with different board sizes, even an [[Infinite Board|infinite board]].
=Quotes=
[[Alex Bell]] in ''Games Playing with Computers'' on Huberman's program <ref>[[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p005.htm#index19 Chess programs: Huberman]</ref>:
A philosophic program was written by Barbara Huberman to specifically play end games. It was a research project on translating book descriptions of problem solving methods into program heuristics. It is well known that the following minimum combinations of pieces have a certain win against a lone king:
* K,Q
* [[KRK|K,R]]
* K,B,B
* [[KBNK Endgame|K,B,N]]
* K,N,N,N
The K,Q can be considered equivalent to the K,R.
Huberman followed descriptions (by [https://en.wikipedia.org/wiki/Jos%C3%A9_Ra%C3%BAl_Capablanca Capablanca] and [https://en.wikipedia.org/wiki/Reuben_Fine Fine]) of how to execute all but the case of K,N,N,N. The cases of K,R and K,B,B are feasible using the [[Minimax|minimax]] technique. This is not true for the [[KBNK Endgame|K,B,N]]. The difficulty here is that bishops and rooks can force mate on any size of board but the knight has a limited mobility (from a centre square there are five squares which each require four moves to be reached by the knight).
Consequently the K,B,N mate is not possible on a board of side > 8. Even allowing for the black king being against a side there is no way in which the K,B,N can be arranged and played that will systematically force the black king along the edge of an infinite board. Because of this weakness the actual mating can take up to forty moves. Huberman's model for the problem was a forcing tree co-ordinated with two functions (better and worse) which were able to compare positions. Roughly speaking the program had two sub-goals (apart from not losing a piece, giving [[Stalemate|stalemate]] , etc). First drive the king away from the centre and second, when the king is at the edge, drive him towards a corner of the bishop's colour.
Huberman's program is the only one which can perform this mating sequence for any starting position. It would be a useful addition to [[Mac Hack|Greenblatt's program]], being easily extended to solve other end games and hence giving the more general program a selection of sub-goals equivalent to winning the game. The problem of K,N,N,N is unlikely to occur; nevertheless it is of interest to the theorists. One surprising fact is that the combination can systematically drive the black king along the edge of an infinite board, and therefore the mating sequence is much easier to program.
=Publications=
* [[Barbara Liskov|Barbara J. Huberman]] ('''1968'''). ''A Program to Play Chess End Games''. Technical Report no. CS-106, Ph.D. thesis. [[Stanford University]], Computer Science Department
* [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p005.htm#index19 Chess programs: Huberman]
* [[John McCarthy]] ('''1990'''). ''Chess as the Drosophila of AI.'' [[Computers, Chess, and Cognition]], pp. 227-237 <ref>[[John McCarthy]] ('''1997'''). ''Chess as the Drosophila of AI''. Computer Science Department, [[Stanford University]], condensed version of the 1990 paper, [http://innovation.it.uts.edu.au/projectjmc/articles/drosophila/drosophila.pdf pdf]</ref>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=197935 evaluating KNNN-K] by [[Rafael B. Andrist]], [[CCC]], November 18, 2001
=References=
<references />
'''[[Engines|Up one Level]]'''
