To Our Fellows,
Why does the search in game-playing programs always proceed forward from the
current position rather than backward from a goal state?
My sincere thanks in advance for your help.
H�ctor M. Mu�oz
"Hector Munoz" <···········@home.com> writes:
> Why does the search in game-playing programs always proceed forward from the
> current position rather than backward from a goal state?
I hope this is not homework. If it is, you should have said so.
I also am not sure this is the best newsgroup to ask this question.
And I also don't know that your premise is valid. Quantifying across
all existing (and perhaps future) programs, sight unseen, seems dubious.
There have always been a wide variety of problem solving strategies used
in game playing. It seems to me it really depends on the game which is
most appropriate. Not all of them even require search.
But I will observe that there is only one present state and it can get to
probably only a subset of the goal states, so every path from the present
state to a goal state is "relevant". There may be many goal states, and
some of them that are not relevant; working back from a goal state you may
find that some paths you explore were utterly uninteresting because they
do not extend backward to the present state, hence all work on that path
was wasted.
Kent M Pitman ······@world.std.com writes:
>"Hector Munoz" <···········@home.com> writes:
>
>> Why does the search in game-playing programs always proceed forward from
>the
>> current position rather than backward from a goal state?
>
> ...
>
>And I also don't know that your premise is valid. Quantifying across
>all existing (and perhaps future) programs, sight unseen, seems dubious.
>There have always been a wide variety of problem solving strategies used
>in game playing. It seems to me it really depends on the game which is
>most appropriate. Not all of them even require search.
>
>But I will observe that there is only one present state and it can get to
>probably only a subset of the goal states, so every path from the present
>state to a goal state is "relevant". There may be many goal states, and
>some of them that are not relevant; working back from a goal state you may
>find that some paths you explore were utterly uninteresting because they
>do not extend backward to the present state, hence all work on that path
>was wasted.
>
Chess programs do start with the current position, but there are also large
endgame databases that have been developed working from the other direction.
One of them has solved every position containing 5 or fewer pieces. I'm sure at
least some of the versions of the chess-playing programs now being developed
will use the entire table of positions in the endgame database as goal
positions.
"Hector Munoz" <···········@home.com> writes:
> To Our Fellows,
>
> Why does the search in game-playing programs always proceed forward from the
> current position rather than backward from a goal state?
This is not always the case. Many modern chess programs are able to
play perfectly when there are only five or fewer pieces left on the
board, using a pre-generated database of all such positions. Such
databases are generated by working backwards from a smaller set of
positions for which the game-theoretical result is already known. If
you want to generate a database of all endgames with king and queen
versus king, for instance, you start with all positions where the
black king is checkmated or stalemated, and search backwards from
these final positions until all KQK positions are examined.
--
Tord Romstad