ICCAJ v.19 n.2 now in North America
Steven J. Edwards
For my fellow ICCA members, the June 1996 issue of the _ICCA Journal_
has arrived in North America. At least I got my copy today.
One of the items of interest is the advance program for "Advances in
Computer Chess 8_. Well, it's not really advance because it took
place last week. Anyway, even if I had a time machine, I don't have
the budget for airfare to Maastrict.
Two of the presentations dealt with chess endgames. Ken Thompson was
scheduled to speak on six piece endgame classes. Eventually I will
get a copy of the proceedings, but in the interim I would appreciate
it if anyone in attendance might post an abstract, as I assume that he
was discussing database approaches. The second endgame topic was by
Milner and Walker and it was about "Heuristics and Loops in KQKR". It
would be interesting to see what role, if any, databases played in
their work.
A feature article discussed shogi (Japanese chess-like game) and was
worthwhile reading. I agree with the editors' decision to include
this non-chess paper as it does help further the computer chess
effort. However, I disagree with the authors' opinion that "the path
chess -> shogi -> go is a natural development in game research".
Chess and shogi are far more closely related to each other than either
is related to go. I disagree with the use of state space enumerations
to measure the complexities of games, as this leads the unwary into
thinking that somehow chess is "better" than checkers or that go is
"better" than chess.
And here's a request for the organizers of the ACC8 conference: please
help the ICCA readership to be able to purchase copies of the _ACC8_
hardcover when it appears. It can be surprisingly difficult to order
one of these though the publisher or though many bookstores. An order
form insert in the next issue of the _ICCAJ_ would be much appreciated.
For those in North America, an annual membership in the ICCA can be
had for $US40 and includes the quarterly _ICCA Journal_. Send a check
to:
ICCA
c/o Don Beal
Dept. of Computer Science
Queen Mary and Westfield College
Mile End Road
London E1 4NS
ENGLAND
-- Steven (s...@mv.mv.com)
Jos Uiterwijk
Steven J. Edwards wrote:
>
> For my fellow ICCA members, the June 1996 issue of the _ICCA Journal_
> has arrived in North America. At least I got my copy today.
>
> One of the items of interest is the advance program for "Advances in
> Computer Chess 8_. Well, it's not really advance because it took
> place last week. Anyway, even if I had a time machine, I don't have
> the budget for airfare to Maastrict.
It is not otherwise. At least some members received the programme "in advance",
since in the Netherlands (and maybe some other European countries) the issue
was delivered 1 day (!) before the conference.
>
> Two of the presentations dealt with chess endgames. Ken Thompson was
> scheduled to speak on six piece endgame classes. Eventually I will
> get a copy of the proceedings, but in the interim I would appreciate
> it if anyone in attendance might post an abstract, as I assume that he
> was discussing database approaches. The second endgame topic was by
> Milner and Walker and it was about "Heuristics and Loops in KQKR". It
> would be interesting to see what role, if any, databases played in
> their work.
>
> A feature article discussed shogi (Japanese chess-like game) and was
> worthwhile reading. I agree with the editors' decision to include
> this non-chess paper as it does help further the computer chess
> effort. However, I disagree with the authors' opinion that "the path
> chess -> shogi -> go is a natural development in game research".
> Chess and shogi are far more closely related to each other than either
> is related to go. I disagree with the use of state space enumerations
> to measure the complexities of games, as this leads the unwary into
> thinking that somehow chess is "better" than checkers or that go is
> "better" than chess.
>
> And here's a request for the organizers of the ACC8 conference: please
> help the ICCA readership to be able to purchase copies of the _ACC8_
> hardcover when it appears. It can be surprisingly difficult to order
> one of these though the publisher or though many bookstores. An order
> form insert in the next issue of the _ICCAJ_ would be much appreciated.
>
A good idea. However, note that the ACC7 book is distributed from the
same department as the ICCA Journal, i.e., the Computer Science Dept.,
University of Limburg, P.O. Box 616, 6200 MD Maastricht, The Netherlands.;
phone: +31-43-3883477; fax: +31-43-3252392; email: ic...@cs.rulimburg.nl
The ACC8 book, due to appear end of this year, will also distributed
by our site. More information will also be available (in due course)
at some of my WEB pages, like
http://www.cs.rulimburg.nl/icca/ (the ICCA home page)
or
http://www.cs.rulimburg.nl/~uiterwyk/acc8.htm (the ACC8 page)
or
http://www.cs.rulimburg.nl/~uiterwyk/cg.htm (our computer-games-group
home page)
> For those in North America, an annual membership in the ICCA can be
> had for $US40 and includes the quarterly _ICCA Journal_. Send a check
> to:
>
> ICCA
> c/o Don Beal
> Dept. of Computer Science
> Queen Mary and Westfield College
> Mile End Road
> London E1 4NS
> ENGLAND
>
> -- Steven (s...@mv.mv.com)
--
-----------------------------------------------------
__ __ _ Jos W.H.M. Uiterwijk
/ / / \ / \ Department of Computer Science
/ / / \ University of Limburg
\_/ \__/ \_/ Maastricht, The Netherlands
uite...@cs.rulimburg.nl
http://www.cs.rulimburg.nl/~uiterwyk/
-----------------------------------------------------
Dr A. N. Walker
Steven J. Edwards wrote:
> Two of the presentations dealt with chess endgames. Ken Thompson was
> scheduled to speak on six piece endgame classes. Eventually I will
> get a copy of the proceedings, but in the interim I would appreciate
> it if anyone in attendance might post an abstract, as I assume that he
> was discussing database approaches.
Ken's primary thesis was that the time is now as ripe for "us" to
construct the 6-piece endings as it was a decade ago for 5 pieces. The
main bottleneck now is the bandwidth between disc and processor, so we
need to organise the calculations carefully to minimise random access to
files. He is starting on some of the calculations, results awaited. Oh,
and the very last few of Ken's CDs disappeared like hot cakes in front of
my hungry eyes ....
> The second endgame topic was by
> Milner and Walker and it was about "Heuristics and Loops in KQKR". It
> would be interesting to see what role, if any, databases played in
> their work.
Essentially none. [Nothing personal, but] I would like endgame
research to get away from database construction [and also from the "toy"
AI stuff]. KQKR can be completely solved by a combination of shallow
search, *very* simple heuristics and a *small* database [few hundred entries]
to deal with the exceptional cases. I would like to make the database even
smaller, with better heuristics. There is, IMHO, as-yet-undiscovered
structure in the game tree for KQKR [and, I expect, many other endgame
classes] that could be exploited. I have no idea whether the KQKR results
extend to [for example] KRKN, KRBKR, KQKBB, etc., but it would be nice [and
would open up some new areas for research] if they did.
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk
Steven J. Edwards
>> Two of the presentations dealt with chess endgames. Ken Thompson was
>> scheduled to speak on six piece endgame classes. Eventually I will
>> get a copy of the proceedings, but in the interim I would appreciate
>> it if anyone in attendance might post an abstract, as I assume that he
>> was discussing database approaches.
> Ken's primary thesis was that the time is now as ripe for "us" to
>construct the 6-piece endings as it was a decade ago for 5 pieces. The
>main bottleneck now is the bandwidth between disc and processor, so we
>need to organise the calculations carefully to minimise random access to
>files. He is starting on some of the calculations, results awaited.
While the data transfer bandwidth is a bottleneck, it is not the only
one. My earlier generator used random access files along with
relatively small memory buffering and the disk seek latency for random
I/O is mostly why took so long to build some of the five man classes.
I got tired of waiting, so I built the new generator with absolutely
zero random file access; everything is sequential. It helps to have
memory buffering, but it is not essential. A good read-ahead,
write-behind disk driver is helpful. Tapes can be used as well and
only forward motion reads/writes are needed. Indeed, unless one has a
big budget, tapes will be required for the six man classes as it takes
about 10 Gbyte to hold one side of a pawnless class like KQNKRR and
about 32 Gbyte to hold one side of a has-pawn class like KPPKPP (en
passant support included).
Hello Ken! If you're reading this and are interested, let me know and
I'll send you a copy of the source for the new generator.
-- Steven (s...@mv.mv.com)
Dennis Breuker
> Hello Ken! If you're reading this and are interested, let me know and
> I'll send you a copy of the source for the new generator.
>
> -- Steven (s...@mv.mv.com)
Just email him: k...@plan9.bell-labs.com
Here are all (I think) abstracts of the ACC8 conference.
A Rational Approach to Kriegspiel
P. Ciancarini(1), F. Dalla Libera(2) and F. Maran(3)
Bologna, Venezia, Italy
ABSTRACT
Kriegspiel is an heterodox Chess variation in which the players have
incomplete information because they are not informed on their
opponent's position and moves. In fact, each player knows the
position of his own pieces, but can only guess the position of the
opponent's pieces. Each player tries to guess the position of the
opponent's pieces as the game progresses by trying moves that can be
either legal or illegal with respect to the real position: a referee
accepts legal moves and rejects illegal ones; the latter are useful to
gain insight into the position. This means that players have to play in
a context of uncertainty and partial information.
We know of no past attempts to build Kriegspiel-playing programs.
This paper describes the design of a program, playing a class of
Kriegspiel positions using a knowledge base which implements a
`rational approach'. The program we have developed integrates two
different notions of rationality introduced by Simon: the substantive
and the procedural rationality (Simon, 1976; Simon, 1978). The
interesting part of such an experience is how the procedural rational
approach can incorporate results obtained with substantive rationality,
whereas the two approaches are usually considered alternative.
1 Department of Computer Science, University of Bologna.
2 Department of Economics, University of Venezia.
3 School of Economics, University of Venezia.
Programme
Information in Transposition Tables
D.M. Breuker, J.W.H.M. Uiterwijk and
H.J. van den Herik(1)
Maastricht, The Netherlands
ABSTRACT
Due to transpositions a search tree can be considered as a search
graph. The transpositions are stored with information about previous
searches in a transposition table. Although the use of transposition
tables is standard practice, it is still an open question how large the
overall reduction is and especially which information has the largest
impact on the reduction.
The paper describes an experiment to distinguish between the
reduction given the best move is stored or the value of the best move
is stored. A second experiment compares storing the bound values for
minimal-window search with storing the true values. It transpires that
the highest reduction comes from re-using bounds because they
adequately generate cutoffs.
Since we know that from a certain transposition-table size not much is
to be gained from doubling the number of entries, it might be useful
to store additional information to see whether this leads to a better
result. Our first experiments on the use of more information per entry
versus more entries indicate that additional memory can better be used
for storing additional information than for doubling the size of the
transposition table.
1 University of Limburg, Department of Computer Science, P.O. Box 616, 6200
MD Maastricht, The Netherlands.
Email: {breuker, uiterwijk, herik}@cs.rulimburg.nl.
Searching with Uncertainty Cut-offs
Y. Bjornsson, T. Marsland,
J. Schaeffer and A. Junghanns1
Edmonton, Alberta, Canada
ABSTRACT
A new domain-independent pruning method is described that
guarantees returning a correct game value. Even though alpha-beta-
based chess programs are already searching close to the minimal tree,
there is still scope for improvement. Our idea hinges on the
recognition that the game tree has two types of node, those were cut-
offs occur and those that must be fully explored. In the latter case one
of the moves is best and yields the subtree value, thus for the
remaining alternatives one is simply proving their inferiority. This
offers and opportunity for pruning, while introducing some potential
for uncertainty in the search process. There are two cases of interest.
One considers the immediate alternatives to the Principal Variation
itself, and here a safe uncertainty cut-off is presented, the second is a
proposal for an unsafe generalization, one which offers substantial
search reduction but with the potential for control of the error
probability. Experiments with the new pruning method show some
potential for savings in the search.
1 University of Alberta, Department of Computing Science, Edmonton,
Alberta
T6G 2H1, Canada.
Email: {yngvi, tony, jonathan, andreas}@cs.ualberta.ca.
Gains and Risks of OM Search
H. Iida(1), I. Kotani(2), J.W.H.M. Uiterwijk
and H.J. van den Herik(3)
Hamamatsu/Tokyo, Japan / Maastricht, The Netherlands
ABSTRACT
A publicly-available computer-chess program provides an excellent
means of an opponent model. Its evaluation function is known
together with its use (in the search and in the search enhancements).
OM search, assuming complete knowledge of the opponent, may
exploit such a model to all its extremes. However, with human
opponents such a precise model is never available.
To investigate the performance of OM search even when the opponent
model is uncertain, we performed some simulation experiments using
a generalization of OM search called OM* search. OM* search uses a
predicted and a real model of the opponent, where real must be read
as assumed in the case of human beings.
We report on experiments determining so-called H-values of OM*,
being heuristically-guided performance measures of the OM*-search
algorithm. The experiments use a game-tree model including an
opponent model as introduced in Iida (1994). The gains and risks of
OM search are analyzed. The main conclusion is that OM search is an
appropriate search algorithm for playing weaker opponents, even if
one has no reliable model of the opponent.
1 Department of Computer Science, University of Shizuoka, Hamamatsu, Japan.
Email: ii...@cs.inf.shizuoka.ca.jp.
2 Department of Computer Science, Tokyo University of Agriculture and
Technology, Tokyo, Japan. Email: kot...@cc.tuat.ac.jp.
3 Department of Computer Science, University of Limburg, P.O. Box 616, 6200
MD Maastricht, The Netherlands. Email: {herik, uiterwijk}@cs.rulimburg.nl
My Experiences with Computers
IGM D. Bronstein(1)
Minsk, White Russia
ABSTRACT
In my lecture I will tell you about my experiences with computers.
The view of a Grandmaster on the game of chess differs radically
from the computers' approach. In my opinion computers play a game
which is no chess, nevertheless I have a deep respect for computer-
chess scientists. I like to play against computers, and in retrospect I
may be the first Grandmaster who did so .... it was in 1963. In my
first game against the Russian program Kaissa I gave it the odds of a
Queen, but even then, that proved to be too optimistic. I will show
some games played with computers, especially two which I played
against IBM's Deep Blue program, in May 1996.
I would like to add that I love creative play against computers,
especially in experimental settings. Although losing a game now and
then, I am always curious why a program rejects some moves and
why it plays another one. Understanding its mathematical ground for
playing a move or rejecting one makes me happy, although the
understanding is only marginal. As a chess Grandmaster I know how
difficult the game is, even for computers and especially for their
programmers.
1 c/o Rue des Tiennes 51, B-1380 Lasne, Belgium.
Fail-High Reductions
R. Feldmann(1)
Paderborn, Germany
ABSTRACT
Fail-High Reductions (fhr) is a new method to guide the search in
game trees in a selective manner. The main idea is that the search
algorithm should not spend too much effort into searches of subtrees,
which look good even at their roots but are not. More precisely, a fail-
high node is a node v with a search window [à, þ] at which a static
evaluation function e produces a cutoff. The fhr algorithm reduces
the search depths at these fail-high nodes, thus searching their subtrees
with less effort. Fhr is domain independent except for the use of a
static domain-dependent evaluation function.
In this paper we describe the implementation of fhr in our chess
program Zugzwang. Three different tests have been conducted to
compare Zugzwang's performance with and without fhr. First, we
compare the results obtained from running the positions of the
WinAtChess test suite. Second, we look at the results obtained from a
match of 150 games under tournament conditions between both
versions. Third, we compare both versions by looking at the results of
100 games played against a chess program developed independently
from Zugzwang. All three tests indicate that the fhr version is about
120 - 150 Elo points stronger than the version without fhr. Moreover,
from the second test we obtain the result that with statistical
significance the fhr version is stronger than the version without fhr.
1 Department of Mathematics and Computer Science, Fuerstenallee 11,
University of Paderborn, 33102 Paderborn, Germany.
Email: obe...@uni-paderborn.de.
Parallel Controlled
Conspiracy-Number Search
U. Lorenz and V. Rottmann(1)
Paderborn, Germany
ABSTRACT
This paper presents a parallel implementation of Controlled
Conspiracy-Number Search (CCNS). In CCNS two pieces of
information are used: values and targets. The values represent
information on nodes, updated bottom up by minimax rules. The
targets contain pieces of information on the reliability of the value;
they control the selective search top down.
CCNS is a best-first search procedure with all nodes kept in memory.
We present a method, that assigns a set of nodes, determined by their
targets and values, to processors. The algorithm has load-balancing
and space problems. They are solved using a combination of dynamic
and static methods. Our solution leads to good speed-up results.
1 Department of Mathematics and Computer Science, Fuerstenallee 11,
University of Paderborn, 33102 Paderborn, Germany.
Email:fl...@uni-paderborn.de.
Topics on 6 Piece Endgames
K. Thompson(1)
New Jersey, USA
ABSTRACT
The time has come to systematically solve all of the six-piece endings.
Currently I feel that it is well within modest means to solve endings
with two Kings and four `pure' pieces. Pawn endings are still a little
out of reach.
In this talk I will outline an approach and current status. I will share
code and also describe some traps to be avoided.
1 Bell Laboratories, 700 Mountain Ave., Room 2C-519, Murray Hill, New
Jersey 07974-0636, USA.
Email: k...@plan9.bell-labs.com
Heuristics and Loops in KQKR
S.D. Milner and A.N. Walker(1)
Nottingham, UK
ABSTRACT
The complex ending King and Queen versus King and Rook turns out
to be amenable to simple heuristics, combined with shallow search and
some simple loop-breaking techniques. Although this method is not
optimal, it does find practical winning paths suitable for use by
humans or computers.
1 Department of Mathematics, The University of Nottingham, Nottingham NG7
2RD, UK.
Email: {sdm, anw}@maths.nott.ac.uk.
SSS+ (+ should be a dagger)
A. de Bruin and W. Pijls(1)
Rotterdam, The Netherlands
ABSTRACT
The paper deals with the history of the SSS* algorithm. The minimax
value of a game tree is equal to the value of an optimal min solution
tree, or equivalently, equal to the value of an optimal max solution
tree. SSS* is a game-tree algorithm, introduced in 1979, which looks
for the optimal min solution tree. Two variants of SSS*, SSS-2 and
RecSSS*, with analogous formulations, look for the max solution tree.
Recently, it was discovered that all three formulations are equivalent
to a sequence of null-window alpha-beta calls. Experiments with this
call sequence have shown, in contrast with simulation experiments in
the past, that SSS* is a practical and realistic algorithm. However, the
assumed theoretical superiority of SSS* over alpha-beta in the set of
visited nodes, does not hold in practice. Therefore, SSS* should not be
considered alive any longer. Fortunately, a related algorithm is very
healthy: a slightly modified sequence of null-window alpha-beta calls
turns out to be a very efficient and competitive.
1 Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The
Netherlands.
Email: {arie, whlmp}@cs.few.eur.nl.
New Advances in Adaptive
Pattern-Oriented Chess
J. Allen, E. Hamilton and R. Levinson(1)
Santa Cruz, USA
ABSTRACT
The paper describes the new developments of our efforts to explore
non-traditional, adaptive, pattern-oriented models for computer chess.
Recently, we have developed Morph III, an adaptive program that
makes use of 4 knowledge sources. The knowledge sources include 2
traditional ones: material and mobility, and 2 new ones: distance
analysis and nearest-neighbour classification. Morph III learns the
credibility of these knowledge sources and how to combine their
recommendations to evaluate a chess position. The nearest-neighbour
classifier embodies an efficient hashing mechanism for matching a
chess position by its similarity to those positions occurring in previous
games played by the system or others. So the system obtains a
recommended evaluation based on previous experience. Distance
analysis is a graph-theoretic method for evaluating chess positions
based on "shortest safe paths" between the pieces. Previous
implementations of the notion Distance have been computationally
expensive. The paper shows how to calculate Distance efficiently. It
does directly in analog fashion using the computer circuitry. The
results in the paper are preliminary but encouraging, showing
improvement over time and performance, significantly above previous
Morph systems.
1 Computer and Information Sciences, Applied Sciences Building, University
of
California at Santa Cruz, Santa Cruz, CA 95064, USA.
Email: levi...@csc.ucsc.edu.
Diminishing Returns for
Additional Search in Chess
A. Junghanns, J. Schaeffer,
M. Brockington, Y. Bjornsson and
T. Marsland(1)
Edmonton, Alberta, Canada
ABSTRACT
Advances in technology allow for increasingly deeper searches in
competitive chess programs. Several experiments with chess indicate a
constant improvement in a program's performance for deeper
searches; a program searching to depth d + 1 scores roughly 80% of
the possible points in a match with a program searching to depth d. In
other board games, such as Othello and Checkers, additional plies of
search translated into decreasing benefits, giving rise to diminishing
returns for deeper searching. This paper demonstrates that there are
diminishing returns in chess. However, the high percentage of errors
made by chess programs for search depths through 9 ply hides the
effect.
1 University of Alberta, Department of Computing Science, Edmonton, Alberta
T6G 2H1, Canada.
Email: {andreas, jonathan, brock, yngvi, tony}@cs.ualberta.ca.
APHID Game-Tree Search
M.G. Brockington and J. Schaeffer(1)
Edmonton, Alberta, Canada
ABSTRACT
This paper introduces the APHID (Asynchronous Parallel Hierarchical
Iterative Deepening) game-tree search algorithm. APHID is not based
on the popular tree-splitting paradigm. Instead, APHID uses repeated
depth-limited searches of the top of the game tree to instantiate,
update and load balance work lists for other processors. APHID has
been programmed as an easy-to-implement, game-independent àþ
library, and was implemented into a chess program with one day of
programming effort. APHID yields reasonable performance on a
network of workstations, an architecture where it is extremely difficult
to use a shared transposition table effectively.
1 Department of Computing Science, University of Alberta, Edmonton, Alberta T6G
2H1, Canada.
Email: {brock, jonathan}@cs.ualberta.ca.
Constraints for Solving Helpmates
R. Staudte(1)
Chemnitz, Germany
ABSTRACT
Chess can be considered as a complex system of arithmetic
constraints. Both geometric constraints (relationships of pieces on the
board) and time constraints (number and order of moves within
several variants) exist in chess.
This paper describes a new search strategy that uses arithmetic
constraints to solve a special class of chess problems þ helpmates with
a limited number of pieces. The algorithm introduced has been
developed in a Constraint Logic Programming language CLP(R) and
tested on helpmates of the type `King and piece against King and
piece'.
1 Technische Universit„t Chemnitz-Zwickau, Fakult„t f r Informatik, D-09107
Chemnitz.
Email: r...@informatik.tu-chemnitz.de.
Application of Fuzzy Logic and
Case-Based Reasoning
to the Generation of
High-level Advice in Chess
S.G. Lazzeri and R. Heller(1)
Washington, USA
ABSTRACT
The success obtained by deep-searching chess programs has resulted
in little effort being spent on developing chess programs with high-
level strategies. For human chess-players such strategies are essential.
This lack of strategical foundations makes most chess-playing
programs inadequate as chess tutors. This paper presents a new
approach for computer chess in general and for a learning environment
for chess in particular as employed in Iconchess (Intelligent
Consultant system for Chess middle games). This approach combines
the techniques of fuzzy logic and case-based reasoning to produce
high-level advice for specific chess positions.
1 Department of Electrical Engineering and Computer Science, The George
Washington University, Washington, D.C. 20052, USA.
Email: {lazzeri, sheller}@seas.gwu.edu.
A Metric for Evaluation Functions
P. Mysliwietz(1)
Paderborn, Germany
ABSTRACT
The process of developing and improving heuristic evaluation
functions is tedious. There are three main reasons: the identification of
a feature, the combination of features and the absence of a good
metric for comparing the quality of evaluation. The identification of
new features is a hard task. Although many features turned out to be
useful to evaluate some aspects of chess positions, only a few
guidelines exist for combining these features or for integrating them
into one evaluation function.
The third reason, the absence of a meaningful metric to evaluate the
quality of an evaluation function, is discussed. The metric must be fast
enough to guide the construction and optimization process.
The paper describes a new way of addressing the metric problem. We
introduce a metric, the decisions of which are compared with human
decisions. Although the idea to guide machine decisions by human
decisions is not new, its usefulness for an optimization process is a
topic of research. We show that our metric has suitable properties for
the construction and optimization of evaluation functions.
1 Department of Mathematics and Computer Science, Fuerstenallee 11, University
of
Paderborn, 33102 Paderborn, Germany.
Email: ast...@uni-paderborn.de.
On Learning How to Play
E.F. Morales(1)
Cuernavaca, Morelos, M‚xico
ABSTRACT
It is believed that chess masters use a pattern-based knowledge to
analyse a position, followed by a pattern-based controlled search to
verify or correct the analysis. So far, little attention has been spent on
how to learn patterns and pattern-based strategies to play a game on
expert level. This paper describes Pal-2, a system that can
incrementally learn patterns and pattern-based strategy rules from
traces of games. Pal-2 starts with general purpose chess knowledge
and no strategies or pattern-based rules. After a few games, it has
stored several patterns and pattern-based rules, from which it is able to
play a simple endgame. Pal-2 learns the patterns and pattern-based
strategies from the moves of the winning side. Experiments with Pal-
2 in the KRK endgame show that Pal-2 can learn how to checkmate
the opponent.
1 Instituto Tecnol¢gico y de Estudios Superiores de Monterrey - Campus Morelos,
Apto. Postal C-99, Cuernavaca, Morelos, 62050, M‚xico.
Email: emor...@campus.mor.itesm.mx.
The Creation of
Tsume-Shogi Problems by a
Retrograde Method
M. Hirose(1), H. Matsubara(2) and T. Itoh(3)
Tokyo, Ibaraki, Japan
ABSTRACT
A program, automatically creating Tsume-Shogi (Japanese chess
mating) problems by a retrograde method is described. Tsume-Shogi is
a popular one-person puzzle among Japanese people. A noticeable
difference between Shogi and western chess is that in Shogi a player
can reuse pieces which have been captured from his opponent. Owing
to this particular rule, Shogi has different informational properties
from chess. The average branching of Shogi is about 80. Rules of
Tsume-Shogi are different from those of western mating problems.
There are two methods to create Tsume-Shogi problems: a straight
forward method and a retrograde method. This paper describes the
retrograde method which is comparatively easy to implement on a
computer.
Our program consists of four stages: the selection of mate positions,
the search for retrograde moves, the optimization of the positions, and
the evaluation of the problems. First, many mate positions fit for
Tsume-Shogi problems are generated by a computer. One of them is
selected as a candidate. Some pieces are added at random on the mate
position. Second, the moves of the attacking side and the defending
side are in turn searched backward by the retrograde method. A
Tsume-Shogi solver usually investigates whether a created problem is
complete or not. Created complete problems may have some useless
pieces. Third, the useless pieces are eliminated from the board. Fourth,
the created problems are evaluated. It is possible that similar problems
are created. The best problem is selected.
1 Tokyo Institute of Technology.
2 Electrotechnical Laboratory, 1-1-4 Umezono, Tsukuba, Ibaraki, Japan 305.
Email: mats...@etl.go.jp.
3 NNT Software Laboratories.
Dennis.
Simon Read
s...@mv.mv.com (Steven J. Edwards) wrote:
>And here's a request for the organizers of the ACC8 conference: please
>help the ICCA readership to be able to purchase copies of the _ACC8_
>hardcover when it appears. It can be surprisingly difficult to order
>one of these though the publisher or though many bookstores. An order
>form insert in the next issue of the _ICCAJ_ would be much appreciated.
For those of us who only want one paper from ACC8, is it possible to
download a version from someone's home page?
Thanks
Simon
Alan Tomalty
"Dr A. N. Walker" (a...@maths.nott.ac.uk) writes:
> Steven J. Edwards wrote:
>> Two of the presentations dealt with chess endgames. Ken Thompson was
>> scheduled to speak on six piece endgame classes. Eventually I will
>> get a copy of the proceedings, but in the interim I would appreciate
>> it if anyone in attendance might post an abstract, as I assume that he
>> was discussing database approaches.
>
> Ken's primary thesis was that the time is now as ripe for "us" to
> construct the 6-piece endings as it was a decade ago for 5 pieces. The
> main bottleneck now is the bandwidth between disc and processor, so we
> need to organise the calculations carefully to minimise random access to
> files. He is starting on some of the calculations, results awaited. Oh,
> and the very last few of Ken's CDs disappeared like hot cakes in front of
> my hungry eyes ....
>
>> The second endgame topic was by
>> Milner and Walker and it was about "Heuristics and Loops in KQKR". It
>> would be interesting to see what role, if any, databases played in
>> their work.
>
> Essentially none. [Nothing personal, but] I would like endgame
> research to get away from database construction [and also from the "toy"
> AI stuff]. KQKR can be completely solved by a combination of shallow
> search, *very* simple heuristics and a *small* database [few hundred entries]
> to deal with the exceptional cases. I would like to make the database even
> smaller, with better heuristics. There is, IMHO, as-yet-undiscovered
> structure in the game tree for KQKR [and, I expect, many other endgame
> classes] that could be exploited. I have no idea whether the KQKR results
> extend to [for example] KRKN, KRBKR, KQKBB, etc., but it would be nice [and
> would open up some new areas for research] if they did.
>
> --
> Andy Walker, Maths Dept., Nott'm Univ., UK.
> a...@maths.nott.ac.uk
lewis Stiller 3 years ago, did a tablebase of R&B vs 2N and 2 other 6 man
eg's. Were these the only ones that he did?
Komputer Korner
--
Komputer Korner