1. Member
Join Date
Apr 2015
Posts
5
Rep Power
0

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

3. ## 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

4. Member
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.

Originally Posted by gimbal2
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. Member
Join Date
Apr 2015
Posts
5
Rep Power
0

## Re: Need advice on algorithm

Originally Posted by JosAH
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. ## Re: Need advice on algorithm

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

kind regards,

Jos

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

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

## Re: Need advice on algorithm

Originally Posted by JosAH
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

9. ## Re: Need advice on algorithm

Originally Posted by jim829
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

10. Member
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 :)

#### Posting Permissions

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