Re: FW: [Flashcoders] sprouts data structure
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 1990http://en.wikipedia.org/wiki/1990, David Applegatehttp://en.wikipedia.org/w/index.php?title=David_Applegateaction=edit, Guy Jacobsonhttp://en.wikipedia.org/w/index.php?title=Guy_Jacobsonaction=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
FW: [Flashcoders] sprouts data structure
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
Re: FW: [Flashcoders] sprouts data structure
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
Re: FW: [Flashcoders] sprouts data structure
(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
Re: FW: [Flashcoders] sprouts data structure
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
Re: FW: [Flashcoders] sprouts data structure
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 1990http://en.wikipedia.org/wiki/1990, David Applegatehttp://en.wikipedia.org/w/index.php?title=David_Applegateaction=edit, Guy Jacobsonhttp://en.wikipedia.org/w/index.php?title=Guy_Jacobsonaction=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,
