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
