Yes, and the idea isn't difficult, but can be computationally expensive. Generate a tree of possible moves and number them recursively, starting with 0 at the leaves of the tree (note the leaves are winning positions as there are no further moves). Then work back up the tree numbering each level with the lowest interger, which is not the number of the next lower level. This means winning positions are 0's, the level above is non-0, the level above that must be 0 again .... Once you have all the positions labeled, the winning strategy is simple. Move to a 0 position. Once on a 0 position you can leap frog through the game from 0 position to 0 position until you win. this is a class of games called Impersonal, 2 person games, or I2p. Mathematicians love these things. Since this recursive numbering grows by a power function, on the number of possible moves, it's often only feasible to run smaller, simplier cases, and then try to find winning strategies that can be extended to more general cases. The goal is of course a "proof" which may teach him something about graph theory.
On 5/13/06, Bernard Poulin <[EMAIL PROTECTED]> wrote:
oh my apologies, I really did not realize that you had to implement an actual "player" and thus do all the AI. Actually had no clue about what this game really looked like. I understand it a bit better now: The game plays with 2 players, lines are not straight, new dots can be placed anywhere on the line, one wins when its opponent cannot do a move. Interestingly enough, the outcome is somehow deterministic: from Wikipedia: http://en.wikipedia.org/wiki/Sprouts_(game) []"By enumerating all possible moves, one can show that the first player is guaranteed a win in games involving three, four, or five spots. The second player can always win a game started with one, two, or six spots. At Bell Labs <http://en.wikipedia.org/wiki/Bell_Labs> in 1990<http://en.wikipedia.org/wiki/1990>, David Applegate<http://en.wikipedia.org/w/index.php?title=David_Applegate&action=edit>, Guy Jacobson<http://en.wikipedia.org/w/index.php?title=Guy_Jacobson&action=edit>, and Daniel Sleator <http://en.wikipedia.org/wiki/Daniel_Sleator> used a lot of computer <http://en.wikipedia.org/wiki/Computer> power to push the analysis out to eleven spots. They found that the first player has a winning strategy when the number of spots divided by six leaves a remainder of three, four, or five, and conjectured that this pattern continues beyond eleven spots."[] Regards, B. 2006/5/12, Weldon MacDonald <[EMAIL PROTECTED]>: > > The reqiurement is that the software be able to play the game, so I > need a data structure to store the game position for analysis. The > intersection check is moot until I can store the current state of the > game, update it, and analyze the potential moves. > If moves are made that create a cycle, then the possibility of a > vertex, or even a subgraph, being contained by that cycle exists, > which removes the possibility of edges to a vertex outside the cycle, > but not to the vertexes in the cycle. That would have to be > incorperated into the data structure. > I think the adjacency list might store the position, but then the AI > for the game will be very tough to do. > As for the intersection check this will work to prevent an illegal > move, but the tougher part will be making the computer move if the > best move is a line that loops around other vertices. Or maybe I > should forget programming and try my hand at cartooning! > > On 5/12/06, Bernard Poulin <[EMAIL PROTECTED]> wrote: > > (I am re-sending this message - somehow, I got a "disk full error" > message > > from the flashcoders server) > > -------------- > > > > Not sure what you mean by: "How do you tell when a dot has been > encircled > > by a line?" I do not understand why we need to keep track of > cycles? What > > is the relation with your game constraints? I am assuming these are > > "straight lines", right? ...or can they be of any shape? > > > > Essentially what you (seem to) want is simply checking if any line > crosses > > when the user interacts with a dot or a line. In other words, block the > user > > from drawing a line that will cross another one. Just for that, you do > not > > need to keep track of "all the possibilities" in advance... > > > > A straight array of dots and lines should be enough for this. ...or I > must > > be missing something. > > > > I know that doing an intersection check on a complete graph can be a > lengthy > > task but: > > > > Since this an interactive, human-driven game - you can reduce the > > verification processing by just checking one move at a time. The > processing > > time will be at least linear (e.g. not exponential). So it should not be > too > > too bad - especially if the number of segments should fit on a screen in > a > > human-readable form (< 200 ?). > > > > my 0,02$ > > B. > > > > > > 2006/5/12, Weldon MacDonald <[EMAIL PROTECTED]>: > > > > > > My first thought was an adjacency list with something to indicate > > > forbidden edges (for a dot inside a cycle), so it might help. The > > > problem isn't that simple though, as more and more moves are made > > > whose in what cycle and can make waht move is a good deal less than > > > clear. > > > > > > On 5/12/06, André Goliath <[EMAIL PROTECTED]> wrote: > > > > FWIW if have written some AS2 classes some time ago that implement a > > > graph > > > > by using adjacenty lists. > > > > If it would help you let me know > > > > > > > > -----Original Message----- > > > > From: [EMAIL PROTECTED] > > > > [mailto:[EMAIL PROTECTED] On Behalf Of > Weldon > > > > MacDonald > > > > Sent: Thursday, May 11, 2006 2:49 PM > > > > To: Flashcoders mailing list > > > > Subject: [Flashcoders] sprouts data structure > > > > > > > > I have a request for a game called sprouts. The game starts with a > few > > > > randomly distributed dots. There is one move and 2 restrictions. > > > > Move: draw a line for a dot to itself (a loop) or to another dot. > > > > Any line drawn has a new dot on it. > > > > Restriction 1: no more than 3 lines from any dot. > > > > Restriction 2: no lines can cross. > > > > > > > > Simple game, but the data structure to keep track of the game and in > > > > particular to handle restriction 2 is a bear. How do you tell when a > > > > dot has been encircled by a line? > > > > > > > > The game is, of course based on graph theory, and you can represent > a > > > > graph in several ways, but how to determine that it remains planar? > > > > > > > > I haen't begun to think about the visual part of this, if I don't > have > > > > a reasonable data structure I can't teach a computer to play the > game. > > > > > > > > Any ideas? Hints? Wildly improbable ideas? > > > > > > > > -- > > > > Weldon MacDonald > > > > _______________________________________________ > > > > Flashcoders@chattyfig.figleaf.com > > > > To change your subscription options or search the archive: > > > > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > > > > > > > > Brought to you by Fig Leaf Software > > > > Premier Authorized Adobe Consulting and Training > > > > http://www.figleaf.com > > > > http://training.figleaf.com > > > > > > > > _______________________________________________ > > > > Flashcoders@chattyfig.figleaf.com > > > > To change your subscription options or search the archive: > > > > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > > > > > > > > Brought to you by Fig Leaf Software > > > > Premier Authorized Adobe Consulting and Training > > > > http://www.figleaf.com > > > > http://training.figleaf.com > > > > > > > > > > > > > -- > > > Weldon MacDonald > > > _______________________________________________ > > > Flashcoders@chattyfig.figleaf.com > > > To change your subscription options or search the archive: > > > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > > > > > > Brought to you by Fig Leaf Software > > > Premier Authorized Adobe Consulting and Training > > > http://www.figleaf.com > > > http://training.figleaf.com > > > > > _______________________________________________ > > Flashcoders@chattyfig.figleaf.com > > To change your subscription options or search the archive: > > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > > > > Brought to you by Fig Leaf Software > > Premier Authorized Adobe Consulting and Training > > http://www.figleaf.com > > http://training.figleaf.com > > > > > -- > Weldon MacDonald > _______________________________________________ > Flashcoders@chattyfig.figleaf.com > To change your subscription options or search the archive: > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > > Brought to you by Fig Leaf Software > Premier Authorized Adobe Consulting and Training > http://www.figleaf.com > http://training.figleaf.com > _______________________________________________ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
-- Weldon MacDonald _______________________________________________ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
