Check out Symmetric Chess, our featured variant for March, 2024.


[ Help | Earliest Comments | Latest Comments ]
[ List All Subjects of Discussion | Create New Subject of Discussion ]
[ List Earliest Comments Only For Pages | Games | Rated Pages | Rated Games | Subjects of Discussion ]

Comments/Ratings for a Single Item

Earlier Reverse Order Later
[Subject Thread] [Add Response]
Joe Joyce wrote on Sun, May 10, 2009 01:20 PM UTC:
There have been several discussions on whether a particular game, or
particular style of game, is easy or hard to write a decent game-playing
program for. There have also been several challenges to design a game
computers would have difficulty playing. Ideally, people would have an easy
time playing this game. 

Might as well throw my hat into the ring, even though I don't know
anything about computers or programming. I suspect the Chieftain series of
games would get progressively more difficult for programmers as the games
get larger. And, if not now, certainly at a later stage of development, I
think the chesimals games would be rather difficult to program. These are
large, multi-move games, where the exact sequence of piece moves in each
turn makes a difference, and all moving pieces must start their move within
a certain small number of squares from one of the multiple king pieces in
the game [a 'command control' rule, as in wargames]. These are the key
features of the games. 

http://www.chessvariants.org/index/msdisplay.php?itemid=MSchieftainchess
http://www.chessvariants.org/index/msdisplay.php?itemid=MSchesimals:auto

If the preceding is not enough, I have been looking at a hierarchy of
leaders for chieftain variants; and at 'open chesimals', multi-unit
'pieces' that may maintain a separation of 1 square between any 2 units
of the 'piece'. 

Do these design features make for a difficult-to-program game?

George Duke wrote on Mon, May 18, 2009 06:23 PM UTC:
''Oh, let us never, never doubt/ What nobody is sure about.'' --Hilaire
Belloc    Good topic and question that has no direct takers here yet [Arimaa being directly related].
Speculate that any ''CV'' can be tweaked toward complications for
computers to the extent needed for the period of time, be it 1990s, 2020s
or 2040s. Chess is, or ought to be, so much more than programming strong
play. Instead of 50% input from information technologists, how much better
it would be for input of 10% each from real ''artists'' of painting or
sculpture chess-playing Marcel Duchamp, 10% literature of which Chess is
extensive, 10% players of specific next-chesses, 10% prolificists content
to talk abstractly instead of concretely, 10% mathematicians, 10% sports
enthusiasts, 10% moralists on how to reach the wavering millions etc. (Any one of the foregoing specialists could try another mask for a while too: it's not as if one person is one thing only.) But Joe's topic is important, to put in everyday language
what the holes, perceived by experts, are in AI for human-human and
human-computer competitive purposes; because the holes then becoming associated with mere rules have to be interpretable by players regardless the underlying theory pointing one direction or another.

Larry Smith wrote on Mon, May 18, 2009 11:02 PM UTC:
Games with multiple moves per turn will seriously bog down most search
algorithms. The increased potential of field positions does tend to
exponentiate.

What can 'assist' these plodders is some form of 'intuitive' step in
the depth search? Intuition being the ability to reach conclusions with
incomplete information.

[Somebody has probably already done all the following, but I merely give
them as an example.]

Humans(most anyway) look beyond their current move toward a position which
often there may not be a clear path. Sometimes this is simply a desire
which motivates the play and may actually never be achieved. A programmer
might accumulate enough data to create a database of 'favored' field
positions which the 'AI' could then use to influence its overall play.

Another 'intuitive' leap could be the assumption that a series of turns
would involve a specific number of pieces. Focusing the search on a
specific series of moves and exchanges involving only these pieces. As the
ply depth increase, those pieces of this group which were removed from play
would not be replace by others which were earlier discarded(new pieces
introduced during the search, whether by promotion or changing sides, might
be considered part of this evaluated group). Of course, these groups could
not simply be made up of the 'best' pieces on the field.

There are many possibilities to these 'intuitive' leaps. Games can be
evaluated in a variety of ways. A programmer needs to think beyond the
linear progression of turns. Maybe a search engine which works
backward('seeing' a future position and attempting to un-create it to the
current position).

H. G. Muller wrote on Tue, May 19, 2009 10:55 AM UTC:
The techniques you discuss have been tried, but never met with much success
in Chess. Part of the reason is hat it woud require a lot of knowledge to
com up with positions to strive for, which could be realistically
obtained.

The only exception is end-game tablebases. There retrograde analysis is
used to work back from checkmate positions or winning conversions
9promotions, or the capture of a piece) to create the end-game table. But
this is only feasible because the checkmates and conversion are a
well-defined goal, so that positions fitting the requirements can easily be
exhaustively generated.

The search algorithm that currently works best in Chess is recursive
nul-move pruning. There you basicaly explore for what one side can do in 1,
2 3, ... moves when you freeze the pieces of the opponent. (Making him do
only null moves.) This is a dumb but thourough way to generate 'ideas',
i.e. positions that might be reachable from the current position and
achieve some favorable objective according to the evaluation function.

If this is not possible (to the specified depth) there is no reason to
look any further at this branch, but usualy there are som sequences of
moves that cannot be ignored by the opponent. Then it wil search for
alternatives for the null moves (starting with the last one, in
back-tracking version), while at the same time increasing the search depth.
Usually a single null move is replaced by 3 normal ply, to make it less
likely that any countermeasure the opponent finds to our 'plan' is merely
a delaying tactic. (E.g. if on our third ply we could capture his Rook with
a Knight that we manouevred in position with our first two ply, we want to
be sure that he will not push taking the Rook over the horizon by a counter
threat against our Queen that coud be trivially resolved, while his Rook is
trapped).

Selective search in Chess has always overlooked too many things to be
competative. A more sound alternative that does work is reducing the search
depth of moves that seem unlikely to be good (so called 'late moves')
based on some static creterion, rather than completely pruning their
branches. With a fixed reduction the depth to which these branches are
searched will continue to improve with deepening at the root, so that if
there is a surprise there, you will eventually see it. (While with hard
pruning you would be blind to it forever.) Then, if you discover such a
reduced move happens to be good after all, you undo the reduction, and
search it to full depth. If it is still good at that depth, in becomes the
new principal variation. This algorithm can produce significant extra
strength if the static criterion for reducing moves is chosen well.
(Reducng all non-captures except passer puses seems to be already
helpful.)

Of course not every game will behave as Chess. But 'late-move reduction'
seems a sensible way to reduce the effective branching ratio in games that
suffer from a very high branching ration. (Like multiple-move games or
games with piece drops.) E.g. in Arimaa moves that move a piece to a
position where it could have gone through a shorter path would be good
candidates for reduction, or perhaps any move containing backward steps. In
drop games you generally reduce drops (as pieces in hand have higher
mobility than on the board.) Part of the Arimaa branching factor is of
course taken care of by transposition hashing.

Joe Joyce wrote on Wed, May 20, 2009 01:24 PM UTC:
It seems to me that you would need something more than a chess engine to
play a very large Chieftain-type game. As Chieftain is a step toward a
chess simulation of a wargame, I would think that a wargame AI of some sort
might need to be part of the software package. Or is it possible that, by
making what is 'combat' in a wargame 'capture by replacement' in the
CV, you can actually calculate the moves? For reference, here's the
current largest:
http://play.chessvariants.org/pbm/play.php?game%3DOverlord%26settings%3DOverlord+Chess+1.0

Because each side moves 8 pieces/turn [of 64 at start], I think the
decision tree is so great that one cannot go very deep. Surely you can
truncate the search in various ways, but why wouldn't these ways expose
the AI to superior human visual/pattern recognition? There are spots in the
game where you can make such in-depth calculations for a number of turns,
say 4ish complete turns, in a limited area. You cannot make such
calculations for the entire board or game, because there are far too many
moves of approximately equivalent value to project the gameboard even 2
turns into the future with high accuracy. Until the end, probably, when the
pieces are mostly gone.

Larry Smith wrote on Fri, May 22, 2009 02:27 PM UTC:
That's one of the primary hurdles in developing an algorithm,
foreknowledge of the dynamics of the game.

A generic algorithm could prove impossible to apply to all games. Unless
such was written so that sub-functions could be added and manipulated.
These sub-functions could either increase the amount of data that the
algorithm considers, or even truncate it.

The programming language for such sub-functions would need to be extremely
flexible.

Right now I am studying Axiomatic to determine its strength and how(or if)
it can be used in creating strong adjustable algorithms.

6 comments displayed

Earlier Reverse Order Later

Permalink to the exact comments currently displayed.