I am forwarding here a post I made to comp.ai.games.
You are welcome to read it and comment.
Regards,
Shlomi Fish
--
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page: http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_techie.com
If:
1. A is A
2. A is not not-A
does it imply that
1. B is B
2. B is not not-B
---------- Forwarded message ----------
Date: Mon, 3 Dec 2001 00:27:25 -0800
From: posting-system_at_google.com
To: shlomif_at_vipe.technion.ac.il
Subject: Parallilization of A* and DFS scans for solving a solitaire game
From: shlomif_at_vipe.technion.ac.il (Shlomi Fish)
Newsgroups: comp.ai.games
Subject: Parallilization of A* and DFS scans for solving a solitaire game
NNTP-Posting-Host: 128.139.197.27
Message-ID: <deca99a9.0112030027.35dc01f1_at_posting.google.com>
Hi!
My name is Shlomi Fish and I am the author of Freecell Solver, which is
an ANSI C library for automatically solving games of Freecell and related
solitaires. At present, Freecell Solver supports A* scans and two
types of DFS scans - one with procedural recursion, and one that uses
a dedicated stack. Every one of these scans acceptsvarious options that
control its strategy.
I noticed that usually one can find a scan that will solve a board really
quickly, but no scan is good for every board one tries it with. So, I thought
about running several scans in parallel on the same state collection. This can
be done either using several threads or by pre-empting and resuming each scan.
I intend to support both by distinguishing between soft threads (pre-empted
and resumed scans) and hard threads (i.e: what the system gives me).
Now, I came up with a model for making sure that the parallel scans do not
interfere with each other, and that a state would not be reported as
unsolveable due to the parallelization. I am not a formal AI expert, so I
can't tell whether this model ensures such things, so I'd like to bring it
here for your input.
I'll start with a few definitions:
Derived States - States that are directly reachable from a given state.
Tests - Tests are functions that can generate a list of derived states.
Freecell Solver has several such tests, and for each scan one can specify
a given test order which may include only a subset of those tests.
Newly Derived States - Newly derived states are states that a test found
that did not previously exist in the state collection.
Parent State - the state which the relevant state is a newly derived state
of.
Visited - Each state has a separate visited flag for each scan. This flag
indicates that the function has already run one or more tests on this state.
Dead End - Each state has a scan-wise global "Dead End" flag, that indicates
that one cannot reach the solution from this state, either directly or
indirectly.
Liveness - This is a counter that specifies how many newly derived states of
the state were not yet designated as dead ends.
Complete Scan - This is a scan whose tests' set include all the tests in all
the other scans in the systems.
Now, the model I propose will do the following:
1. When a new state is encountered that was not previously in the collection,
its liveness will be set to 0 and the liveness of the state from which it
was derived will be incremented by 1.
2. When a complete DFS scan leaves a state (and return to the state of
the previous depth), it will designate this state as a dead end, and decrement
the liveness of its parent.
3. When a complete A* scan finds out that no states are reachable from a
given state, it will mark this state as a dead end, and decrement the
liveness of its parent.
4. When a state's liveness has been decremented to zero, it too will be marked
as a dead end and the liveness of its parent will be decremented (and so
forth).
Do you believe this model allows for a safe evaluation of a state, which will
be give the same end result (i.e: solveable or unsolveable) as a single scan?
Regards,
Shlomi Fish
Received on Mon Dec 03 2001 - 04:19:54 IST