Results 1 to 10 of 10
  1. #1
    Synpredator is offline Member
    Join Date
    Apr 2015
    Posts
    5
    Rep Power
    0

    Arrow 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.

  2. #2
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    5,114
    Rep Power
    12

    Default 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

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default 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 H-8 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 A-1 (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 (== phi-1), where phi is the Golden Ratio. Maybe this problem is similar ...

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  4. #4
    Synpredator is offline Member
    Join Date
    Apr 2015
    Posts
    5
    Rep Power
    0

    Default 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.



    Quote Originally Posted by gimbal2 View Post
    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.

  5. #5
    Synpredator is offline Member
    Join Date
    Apr 2015
    Posts
    5
    Rep Power
    0

    Default Re: Need advice on algorithm

    Quote Originally Posted by JosAH View Post
    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 H-8 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 A-1 (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 (== phi-1), where phi is the Golden Ratio. Maybe this problem is similar ...

    kind regards,

    Jos
    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.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default Re: Need advice on algorithm

    Google for "exhaustive search", "game tree" and "alpha beta pruning".

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  7. #7
    Synpredator is offline Member
    Join Date
    Apr 2015
    Posts
    5
    Rep Power
    0

    Default 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

  8. #8
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Need advice on algorithm

    Quote Originally Posted by JosAH View Post
    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 H-8 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 A-1 (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 (== phi-1), where phi is the Golden Ratio. Maybe this problem is similar ...

    kind regards,

    Jos
    Interesting. Sounds like the algorithm may be based on some Fibonacci series.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default Re: Need advice on algorithm

    Quote Originally Posted by jim829 View Post
    Interesting. Sounds like the algorithm may be based on some Fibonacci series.
    Sure it is; the variant I described wants to move the queen to position (x, y) which are consecutive numbers in 'the' Fibonacci series: (0),1,1,2,3,5,8

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  10. #10
    Synpredator is offline Member
    Join Date
    Apr 2015
    Posts
    5
    Rep Power
    0

    Default 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

  1. Replies: 4
    Last Post: 12-18-2013, 09:07 PM
  2. Advice please
    By Martin_smith in forum New To Java
    Replies: 6
    Last Post: 09-30-2013, 06:26 PM
  3. i need an advice!
    By waseem1345 in forum Forum Lobby
    Replies: 2
    Last Post: 11-12-2012, 01:25 AM
  4. Advice for a NPC Path Algorithm
    By Grimey in forum New To Java
    Replies: 26
    Last Post: 06-13-2012, 03:10 AM
  5. need for some advice
    By kasiopi in forum AWT / Swing
    Replies: 3
    Last Post: 01-26-2011, 12:36 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •