Results 1 to 10 of 10
Thread: Need advice on algorithm
 04152015, 08:40 AM #1Member
 Join Date
 Apr 2015
 Posts
 5
 Rep Power
 0
Need advice on algorithm
Hey guys,
I have a project that I have been asked to do but I am uncertain about the best approach to it and wanted some help finding out what would be the best algorithm to use? Any recommendations on algorithm or how to approach the problem are welcome
I am not looking for anyone to do it for me , just looking for help on how to approach it.
Thanks
The game has two players: x and o. The players take alternate turns, with player x moving first at the beginning of each game.
Player x starts at position (1,1) while o starts at (8,8).
Each turn, a player can move like a queen in chess (in any of the eight directions) as long as her path does not cross a square already filled in or occupied. After moving, the space vacated by the player is designated as filled and cannot be moved to again. Notice that only the space that was occupied is filled, not the entire path.
The game ends when one player can no longer move, leaving the other player as the winner.
The coordinate (1 1) indicates the top left hand side of the board. The board is specified as a list of rows. Each row is a list of entries:
 is an empty square
* is a filled in square
x is the current position of the x player o is the current position of the o player
The board will always be 8 by 8.
Your player function should take in the parameters as described above and return a move as a list in the format (row column) within 1 minute. If you cannot move, return (nil nil). The Tournament Referees will check for this. If you return an illegal move, the other player (and the Tournament Referees) will detect it and you will lose. Additionally if your time expires you will lose.
 04152015, 11:34 AM #2Just a guy
 Join Date
 Jun 2013
 Location
 Netherlands
 Posts
 5,114
 Rep Power
 12
Re: Need advice on algorithm
Me personally I'd start with thinking out a possible data structure for that game board which is at the heart of your entire problem description. At least have something to work and experiment with. That will also force you to really dig through that problem description and identify all the bits and bops in it which you will need to model to be able to produce the answers your future algorithm must be able to produce.
"Syntactic sugar causes cancer of the semicolon."  Alan Perlis
 04152015, 11:49 AM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: Need advice on algorithm
I didn't give this problem much thought yet, but I know a variation of this problem: one queen is placed in the upper right corner H8 of the chess board. Players take turns and are allowed to move the queen down, to the left, or diagonally down/leftwards; the player who has to place the queen at position A1 (bottom left corner) loses the game. Surprisingly (at least to me), the optimal positions of the game are positions (x, y) where x/y approximates phi or 1/phi (== phi1), where phi is the Golden Ratio. Maybe this problem is similar ...
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 04152015, 12:00 PM #4Member
 Join Date
 Apr 2015
 Posts
 5
 Rep Power
 0
Re: Need advice on algorithm
Hi Gimbal2,
Thank you for the response, I have started with a two dimensional array as the board so (1,1) is the top left corner and (8,8) is the bottom right corner, I forgot to mention that this has to Include AI in it, so one of the players has to be AI based, I am looking for an Algorithm that will help with that process.
 04152015, 12:04 PM #5Member
 Join Date
 Apr 2015
 Posts
 5
 Rep Power
 0
Re: Need advice on algorithm
HI JoshAH,
Thank you for your response, I wrote this post early this morning and left out a key element, One of the players is an AI based player, and I need an algorithm that will help with this process, I am going to be marked on performance of the algorithm, I am using a 2 d array at the moment for the board that I setup so (1,1) being the top left corner and then (8,8) being the bottom left corner,
I am unsure how to approach the AI part for performance and anyone withe experience could recommend an algorithm or any information about how to approach this or where to start would be greatly appreciated.
 04152015, 12:26 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Re: Need advice on algorithm
Google for "exhaustive search", "game tree" and "alpha beta pruning".
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 04152015, 01:07 PM #7Member
 Join Date
 Apr 2015
 Posts
 5
 Rep Power
 0
Re: Need advice on algorithm
Hi Josh
ok, thank you for them, I will do a little more research on them and see which is more suited, Thank you once again
Regards
Syn
 04152015, 02:36 PM #8Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 14
Re: Need advice on algorithm
The Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 04152015, 07:21 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
 04272015, 08:41 PM #10Member
 Join Date
 Apr 2015
 Posts
 5
 Rep Power
 0
Re: Need advice on algorithm
Thank you all for your feedback, I have begun by developing my player moves and just going to start the AI Now, I have made the board and allowing user input for both the AI and the player, I'm still uncertain about what algorithm is going to be most efficient, I guess its time to mess around and try get some answers, Thanks again everyone, Anyone else has any feedback, feel free to add :)
Similar Threads

Football tournament algorithm. Any advice would be greatly appreciated :)
By Castro__711 in forum New To JavaReplies: 4Last Post: 12182013, 09:07 PM 
Advice please
By Martin_smith in forum New To JavaReplies: 6Last Post: 09302013, 06:26 PM 
i need an advice!
By waseem1345 in forum Forum LobbyReplies: 2Last Post: 11122012, 01:25 AM 
Advice for a NPC Path Algorithm
By Grimey in forum New To JavaReplies: 26Last Post: 06132012, 03:10 AM 
need for some advice
By kasiopi in forum AWT / SwingReplies: 3Last Post: 01262011, 12:36 PM
Bookmarks