Archived

This topic is now archived and is closed to further replies.

Need help with Attax (AI)

This topic is 6074 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello I''ve been making an attax kind of game, and by now it''s already (almost) fully functional. It''s possible for two persons to play against each other. The problem i''m having it''s in the AI of the game. I want the possibilitie of having the computer to play against a person and, also, the computer to play against him self (linux style). Now, in order to make the computer decently smart, it''s going to take a lot of trouble. I can''t just make the computer select the move in wich he takes more pieces from the adversarie, because it''ll be too easy for someone to win (actualy, this idea will problably be implemented because im thinking in having the possibilitie of diferent computer settings). But the problem is still in making the computer decently smart. Can someone help with ideas/algos? Thanks.

Share this post


Link to post
Share on other sites
I don''t even know what the game is, but I bet it''ll be similar to chess or checkers AI.

You have the existing board in RAM, and you create a board for each possible move. Then you need some method of rating each board (in chess each piece on the board have a specific value, with checkers it''s easy). You keep search deeper down the board-possiblities until you run out of time (or hit a preset depth limit - a difficulty setting).

Pick the move toward the best position for the cpu.

Magmai Kai Holmlor
- The disgruntled & disillusioned

Share this post


Link to post
Share on other sites
Yes, im sorry, i should have given a description of the game since it's not very well known (i myself only heard of it when i started fooling arround with linux).

Attax has to do more with checkers.

You have a board of 7x7.
You start with 2 white pieces and 2 black, each of them starting in oposite corners of the board.

There are 2 kinds of movements available.
You can deslocate (copy) your piece to any of the eight adjacent houses (if free), or you can move (a jump) your piece to any house wich is at a distance of 2 blocks (if free).

In either one of the cases, when you make a move, if there are any pieces of the other player in some of the eight adjacent houses, they become your's (they change color).

The game ends when the board is full, or when one of the players doesn't have any valid moves to make.

Obviously, wins who has more pieces when the game ends. (we can also have a tied game).



It seems like i need some way of rate each play and position of the board.
Does this also mean that i would have to try and guess what will be the other player's best move? (this would be very complicated)

Thxs for your help.

Edited by - wolverine on April 26, 2001 5:46:15 AM

Share this post


Link to post
Share on other sites
It's called a min-max search. What you do is this.

Look at all the possible moves you can make from you current position (if there's a lot, then just take a few of them, say ten). Now you give each outcome a score, say based on the number of pieces you have, or something. This is the first level in your tree. Now, for each branch, you extend them one more level. But instead of you moving and giving them a score, make a move from the perspective of the other player, and give them a score, based on the same parameters above, so if they get a lot of pieces, then you have a large score for that score. Now, repeat the process from your side, extending the tree down to as many levels as you want, or until your time runs out.

Here's a quick diagram, which shows two levels down, and a small number of moves:

|
+--------+--------+--------+--------+
| | | | |
4 5 3 7 2 <- your move
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+
| | | | | | | | | | | | | | |
5 6 4 5 7 6 4 4 3 2 8 3 4 2 1 <- enemy move


Now, you give each of the top branches a final score, so that you can pick the best move. The way you do this, is for each child node, you pick the one with the highest score, and subtract it from your score. Here's code:

    
int branch_score( Node n )
{
int score = n.getScore();
int max_score = 0;
for each child in n
{
if( branch_score( n ) > max_score )
max_score = branch_score( n );
}

return( score - max_score );
}


The way this works is it gives the other's players best moves a large negative score, and your best moves a large positive score.

(Edited for typos)

Edited by - dean_harding on April 26, 2001 5:59:00 AM

Share this post


Link to post
Share on other sites
That sounds good.

And the best thing is that i don´t have to recalculate the hole tree every time the computer has to make a move, because part of it may have been already calculated. The only thing i need to take care is to pick the moves to insert in the tree (i can´t insert every move because, since the pieces can increase, there would be too many possibles moves)

I´ll give it a try.

Thanks to both of you.

Share this post


Link to post
Share on other sites
Hey, that sounds good.

And the best thing is that i don´t have to calculate the hole tree every time the computer plays, since a part of it is already done. I just need to take care in choosing which moves to put in the tree (I can´t put all the possible moves because there will be too many of them when the number of pieces starts to grow).

I´ll give it a try.

Thanks both of you for your help.

Share this post


Link to post
Share on other sites