Everybody! This is important. In a few days, these forums will be moving over to using the totally sweet Discourse platform. To ensure this migration happens smoothly with no loss of content, these forums are currently in a read-only mode. I do apologize for the inconvenience.

There is never a good time to turn the forums off for an extended period of time, but I promise the new forums will be a billion times better. I'm pretty sure of it.

See you all on the other side in a few days, and if you have any (non-technical) questions, please e-mail me at kirupa@kirupa.com. For technical questions, try to find a tutorial that corresponds to what you are looking for and post in the comments section of that page.

Cheers,
Kirupa

Results 1 to 13 of 13

Thread: A challenge for passionate AI programmers

  1. #1

    Pallete A challenge for passionate AI programmers

    Hi all, I have a challenge that is puzzling me. Maybe it's not that hard, but I'm new to AI programming, so...

    I have to develop an AI for a game of my own, a turn-based puzzle game. It's something chess-like, as it needs a CPU opponent to think ahead of what the player will be doing the next turn to be effective. The challenge is that the game board is divided into areas that rotate, so the AI has to make a hard guess for the gaming world can change after every move. The game is a multiplayer 1 vs 1 now, and I need help to make the AI for the single-player.

    WHAT I NEED IS NOT PROGRAMMING. I will do that.

    I need some AI expert which wants to step up and help me in solving this challenge with the theory and the basis for this AI. I won't pay him because I can't now, although the game has great plans and anyone involved will be rewarded in some way.
    The game is currently made in Flash but we want to port it to the iPhone or DS (hopefully). Credit is of course guaranteed, I will make clear who made the AI anywhere on the site and the product if it ships for the intended platform.

    Enough talk now! If you want, the game is online and you can try it on http://www.ufho.it
    It's one vs one but it's also turn-based, so you can open two windows and play in both as guest (user: guest and password: guest).
    In the site there's a guide that explains the game. It's located at http://www.ufho.it/guida2_en.php?lang=en#3

    If you want to help, I'd simply like some hint like an algorithm adapted for this game. I will take care of the programming afterwards, I only need theoric implementation.

    Thanks in advance to anyone who accepts this challenge! And feel free to ask me for anything!

    Ciro Continisio
    UFHO

  2. #2
    From reading the description of the game, it looks like just using a standard chess AI algorithm is enough.

    Read up on alpha-beta pruning search algorithm, which is an optimized version of the min-max algorithm that is useful in all alternating turn based games.

    The basic idea of min-max is that you should make moves that your opponent have a hard time defending against. To turn the concept into an actual algorithm, you need to be able to evaluate the game board and turn it into a score. This is called an 'evaluation function.'

    So for a given board position, you can say the score is X, where the higher the X, the closer you are to winning the game. On your move, you are trying to find positions that have the highest score, and on your opponent's move, they are trying to find positions that have the lowest score for you.

    That is basically where the min-max algorithm comes from. You know your opponent will find moves that is the 'min' score, so you should find moves that have the 'max', or highest minimum score. That fits our intuition of a move that is hard to defend against.

    As for an evaluation function, you can just use A*. The smallest number of moves and number of turns needed to reach the gem is basically your evaluation function. Except in your case, the closer you get to the gem, the higher the score. Your power gems special ability can be incorporated into A*s distance function, so the AI can figure out if getting a power gem is worth the moves it took to get there.

    That's the high level description of how I would approach the problem. Both algorithms are pretty well standard, the trick is tweaking evaluation function for alpha-beta, and tweaking the distance function for A*.

    Hopefully this helps. Tell me if anything was unclear.

  3. #3
    First of all thanks for spending time in writing back, Lida.
    I read all you said and documented on A*, min-max algorithm and alpha-beta pruning. While it is surely a good starting point, I don't understand how I can evaluate the goodness of one move. I mean, in chess the move is only one for each turn. So you take one hypothetic move, you evaluate all the enemy's hypothetic moves for that one, and you give it a score.
    In my game, you have 6 moves to spend. How can I decide wether to spend 2 moves to actually move myself instead of spending them to rotate the area the enemy is in (so I slow him down)? Do you mean I have to try ALL the possibilities and give them a score for evaluating?

    Sorry if I'm incompetent, I just started with this AI thing

  4. #4
    Quote Originally Posted by ccontinisio View Post
    First of all thanks for spending time in writing back, Lida.
    I read all you said and documented on A*, min-max algorithm and alpha-beta pruning. While it is surely a good starting point, I don't understand how I can evaluate the goodness of one move. I mean, in chess the move is only one for each turn. So you take one hypothetic move, you evaluate all the enemy's hypothetic moves for that one, and you give it a score.
    In my game, you have 6 moves to spend. How can I decide wether to spend 2 moves to actually move myself instead of spending them to rotate the area the enemy is in (so I slow him down)? Do you mean I have to try ALL the possibilities and give them a score for evaluating?

    Sorry if I'm incompetent, I just started with this AI thing
    If you want to make it easier on yourself, don't allow the 6 moves every XX seconds against the computer. Have it be turn by turn, with some sort of speed multiplier so that if one person gets more turns via a powerup or something, they'll just take two turns in a row. Something like that.

    Otherwise, with your AI, you'll need to decide, ok, the computer could conceivable take all 6 turns in like..12 milliseconds, so you'd have to figure out someway to space out those moves. I haven't spent too much time playing your game, but you could give the AI a couple different states, like attacking & defending, so that, maybe when defending, they computer would wait for the user to make a move and react once, then analyze, maybe switch to attacking.. This will be exponentially harder than keeping it completely turn based.
    you = function(){
    setEnabled( true );
    live();
    setEnabled( false );
    }

  5. #5
    Quote Originally Posted by therobot View Post
    If you want to make it easier on yourself, don't allow the 6 moves every XX seconds against the computer. Have it be turn by turn, with some sort of speed multiplier so that if one person gets more turns via a powerup or something, they'll just take two turns in a row. Something like that.
    I'm sorry but I don't mean to change the mechanics of the game. We made a big test with a lot of users, and some emerged as real experts. With them we agreed that the game is good as it is, it has a special balance and in the end when played by veteran players, it can offer some serious tactical pleasure. So I can't make it one move at a time or real-time.

  6. #6
    Quote Originally Posted by ccontinisio View Post
    First of all thanks for spending time in writing back, Lida.
    I read all you said and documented on A*, min-max algorithm and alpha-beta pruning. While it is surely a good starting point, I don't understand how I can evaluate the goodness of one move. I mean, in chess the move is only one for each turn. So you take one hypothetic move, you evaluate all the enemy's hypothetic moves for that one, and you give it a score.
    In my game, you have 6 moves to spend. How can I decide wether to spend 2 moves to actually move myself instead of spending them to rotate the area the enemy is in (so I slow him down)? Do you mean I have to try ALL the possibilities and give them a score for evaluating?

    Sorry if I'm incompetent, I just started with this AI thing
    The 6 moves doesn't matter to the algorithm, since you only need to evaluate the board after you finish moving. So you generate all the possible board position after using up the 6 moves then evaluate.

    The problem with having 6 moves, is that there are going to be a huge amount of potential board position for just one turn. You are not going to be able to see many turns in advance, so your evaluation function needs to be pretty good.

    You can generate a smaller set of board positions based on some rule of thumb, but the AI may have some blind spot due to your rule of thumb not being good enough.

  7. #7
    Ok, thanks... now it comes the thinking time for me...
    Anyway the "rules of thumb" thing is not too good, I prefer searching with the algorythm every time.

  8. #8
    I'm no AI programmer, so take my suggestion here with a grain of salt: What if you had a generic evaluate function along with some pre-programmed strategies or rules of thumb based on suggestions from some of your veteran players (i.e. the most important spots on the board, strategies, etc). When someone picks multiplayer it could randomly choose one of the strategy sets and then, in conjunction with your evaluate function, use that to play the game.

    Again, not an AI programmer, so this may be a horrible idea...

    ~Cody

  9. #9
    Quote Originally Posted by ShadowViper View Post
    I'm no AI programmer, so take my suggestion here with a grain of salt: What if you had a generic evaluate function along with some pre-programmed strategies or rules of thumb based on suggestions from some of your veteran players (i.e. the most important spots on the board, strategies, etc). When someone picks multiplayer it could randomly choose one of the strategy sets and then, in conjunction with your evaluate function, use that to play the game.

    Again, not an AI programmer, so this may be a horrible idea...

    ~Cody
    I think that makes sense if you are making a game based on AI 'personalities.' That's probably what C&C Generals or Civilization does.

    So if you have a campaign mode where you fought different AIs, then you need that kind of variety in how AI react. Otherwise, I don't see much benefit.

  10. #10
    ShadowViper, I don't think it's a good idea since that would make the AI very stupid... or I needed to prepare in advance a BIG deal of gaming situations... and that's hard and long. And maybe not convenient. Anyway thanks for the interest!

  11. #11
    Quote Originally Posted by Lida Tang View Post
    The 6 moves doesn't matter to the algorithm, since you only need to evaluate the board after you finish moving. So you generate all the possible board position after using up the 6 moves then evaluate.
    I disagree here. If you want to use alpha-beta pruning, you should evaluate as early as possible! If the first move has already a huge impact on the evaluation, it might break down to only deciding the five following moves.

  12. #12
    Quote Originally Posted by Favardin View Post
    I disagree here. If you want to use alpha-beta pruning, you should evaluate as early as possible! If the first move has already a huge impact on the evaluation, it might break down to only deciding the five following moves.
    It may matter to the speed of the algorithm, but not to the correctness. alpha-beta pruning is just an optimization.

    In fact, if the game doesn't force players to use up all moves, the generation of all possible board positions will include 1 move only positions. If you order the positions based on how many moves were used, then it will have the optimization effect that you want.

  13. #13
    Quote Originally Posted by Lida Tang View Post
    It may matter to the speed of the algorithm, but not to the correctness. alpha-beta pruning is just an optimization.

    In fact, if the game doesn't force players to use up all moves, the generation of all possible board positions will include 1 move only positions. If you order the positions based on how many moves were used, then it will have the optimization effect that you want.
    Well, of course. But as my mom used to say: "Prune smart, prune early"

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Tags for this Thread

Posting Permissions

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

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012