Infinite Checkers game
March 11, 2009 01:01 AM
Hey.
In Checkers, a situation can arise between two computers playing each other where only safe moves are played; e.g. moves that don't result in the pieces from that side being jumped. This is exclusive to king pieces. I wanted to know what the best way to handle this would be.
I was planning on just forcing a side to make a dangerous move. Perhaps I could only force a move if only a certain number of moves had been made that were safe and hence didn't result in a jump?
Any suggestions are welcome, particularly criticism of my idea.
Cheers.
1,239
March 11, 2009 01:19 AM
How do you decide what move to make normally? Typically you'd have some sort of decision tree where you assume each side would be making the "optimal" move to maximize his benefit and minimize his opponents (I think they're called min-max trees or something... it's been a while since I did academic AI [smile])
You should theoretically be able to detect "loops" in that tree where the moves end up looping back to a previous state and avoid those branches.
You should theoretically be able to detect "loops" in that tree where the moves end up looping back to a previous state and avoid those branches.
March 11, 2009 01:43 AM
I'm using my own AI as I'm not really fussed about an extremely clever computer.
This is how I make moves:
At the moment, if the computer only has king pieces that are able to make moves (we'll call that condition X), then an unsafe move is forced. That obviously means that as soon as the condition X is met, the computer starts making stupid moves. So I figure if I keep a counter of moves that don't result in a piece being jumped after condition X has been met, then it will help eliminate the computer making stupid moves for no reason.
That will be fine for player vs human, but for computer vs computer, the "unsafe" moves that are forced don't necessarily mean that the pieces are advanced towards the opponent. The opposite happens; pieces move back and forth at separate ends of the board for ever. To fix this, I'm going to have to coerce the sides to advance towards each other and see if that works. Edit: Speeding up the game shows that eventually (it actually doesn't take that long) the pieces make enough "stupid" moves to be in range of the other side are jumped. So a computer vs computer game does end!
This is how I make moves:
bool Board::Do_Hard_Move(Player& player){ // Opposite side of side. Player& opponent = Get_Opponent(player); // Get all possible jumps by player. jump_info_vec jumps = Get_Player_Jumps(player); // Prevents predictability. std::random_shuffle(jumps.begin(), jumps.end()); // Priority 1. if(Safely_Jump_Opponent(jumps, KING)) return true; // Priority 2. if(Jump_Opponent(jumps, KING)) return true; // Priority 3. if(Safely_Jump_Opponent(jumps, REGULAR)) return true; // Priority 4. if(Jump_Opponent(jumps, REGULAR)) return true; // Get opponent's possible jumps. jump_info_vec opponent_jumps = Get_Player_Jumps(opponent); std::random_shuffle(opponent_jumps.begin(), opponent_jumps.end()); // Priority 5. // Don't need to check if jump results in opponent jumping us // because saves have to be done regardless. if(Save_Jumpee(opponent_jumps, KING)) return true; // Priority 6. if(Save_Jumpee(opponent_jumps, REGULAR)) return true; // Get all possible advances by player. advance_info_vec advances = Get_Player_Advances(player); std::random_shuffle(advances.begin(), advances.end()); // Priority 7. if(Safely_King_Piece(advances)) return true; // Priority 8. if(King_Piece(advances)) return true; // Priority 9. if(Safely_Advance_Piece(advances, REGULAR)) return true; // Priority 10. if(Advance_Piece(advances, REGULAR)) return true; // Priority 11. if(Only_Kings_Remain(advances)) { // Only kings can move, so they're going to keep playing safe moves for ever // if we don't force them to make a risky move. if(Advance_Piece(advances, KING)) return true; } else { // Other pieces that are able to make moves besides kings remain; game won't last forever. // Priority 12. if(Safely_Advance_Piece(advances, KING)) return true; // Priority 13. if(Advance_Piece(advances, KING)) return true; } // No moves could be made. return false;}At the moment, if the computer only has king pieces that are able to make moves (we'll call that condition X), then an unsafe move is forced. That obviously means that as soon as the condition X is met, the computer starts making stupid moves. So I figure if I keep a counter of moves that don't result in a piece being jumped after condition X has been met, then it will help eliminate the computer making stupid moves for no reason.
That will be fine for player vs human, but for computer vs computer, the "unsafe" moves that are forced don't necessarily mean that the pieces are advanced towards the opponent. The opposite happens; pieces move back and forth at separate ends of the board for ever. To fix this, I'm going to have to coerce the sides to advance towards each other and see if that works. Edit: Speeding up the game shows that eventually (it actually doesn't take that long) the pieces make enough "stupid" moves to be in range of the other side are jumped. So a computer vs computer game does end!
769
March 11, 2009 08:11 AM
If it is true that the best move for both parties in a king v king endgame is to do nothing, then there is something wrong with the rules. I knew there was a reason I didn't like this game ;).
I suspect that there is a rule similar to that in chess which states that if the same board position is repeated 3 times the game is drawn. If advancing results in a loss than an intelligent computer (or human) will play for the draw.
I suspect that there is a rule similar to that in chess which states that if the same board position is repeated 3 times the game is drawn. If advancing results in a loss than an intelligent computer (or human) will play for the draw.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
