|06/09/2008 18:05:54 Yet another Bot thread - Easily made strong bot?|
|Now, I'm not an expert coder myself, and I don't really understand the intricacies of communication with the server, but wouldn't it be very easy to create a very strong bot by making it check every single possible move internally, using something like bmaker's battlelib in order to find the set of moves which most reliably creates the best possible outcome which the other player can take advantage of the least (done so by checking the opponent's possible turns after any given turn). I know this bot would take forever to take it's turn (although since it's all done internally, it shouldn't really stress the server), but I pretty sure this WOULD work, with out any complicated coding.|
|06/09/2008 21:59:04 Re:Yet another Bot thread - Easily made strong bot?|
It is possible... and yes it would take forever. The main obstacles are coding it and memory limitations. It would only be able to look ahead maybe one or two turns before the computer runs out of memory. Chess has many many many fewer move options yet a brute force search over all possible moves to find the "best" move usually cannot look more than maybe seven or so (rough estimate) turns ahead. I could be wrong though...
This message was edited 3 times. Last update was at 06/09/2008 22:00:19
|07/09/2008 18:56:05 Re:Yet another Bot thread - Easily made strong bot?|
It does sound that easy. That's the hard part about AI. What seems easy at first glance to humans is really a lot harder to put into an algorithm that works.
Commonly, turn-based AI uses a board evaluation function that helps it score whether or not a given board configuration is better than a previous one. So you typically exhaust all possibilities (trimming branches intelligently if one is obviously bad), and evaluate each position. The problem is that there are so many, many moves that the solution takes so long to calculate that you can never play your turns. When you say "it will take forever", you're right. And that's the issue at hand.
Let's say I have an open field map and I have five troopers and my single opponent has five troopers. Each of my troopers has at best 37 movement square option each turn.
So to calculate all of my possible movement placements (only including movement alone, not attacks, nor captures) we'd have to do:
We could stop there, but looking ahead is pretty important. In order to see how useful those positions are, I'd need to calculate the opponent's response to each of those possible positions. He also has 5 troopers, so for every one of my 69 million possibilities, I need to evaluate 69 million of the opponent's possibilities. So that give us something like this:
37^5 * 37^5 = 4,808,584,372,417,849
If every calculation took a millisecond to do, then this single turn would take 1,524 centuries to complete.
Note this is only a turn with a few units and two players. If you wanted a more powerful bot, it could take a lot longer, especially if they had to try to calculate moves on a map like this:
To work around these problems in Chess and Go, computer AI has to build a lot of expertise that allows them to trim the look-ahead trees very quickly. Doing that effectively without making really bad strategic plays is difficult, which is why it has taken Go so long to produce any moderately strong Go playing bots:
Hopefully this explains why this problem isn't as easy as it sounds,
This message was edited 4 times. Last update was at 07/09/2008 19:00:53
|07/09/2008 22:34:47 Re:Yet another Bot thread - Easily made strong bot?|
|Very nice explanation, Mattie.|
|09/09/2008 00:00:01 Re:Yet another Bot thread - Easily made strong bot?|
|yeah, thanks a lot! Great explanation.|
|18/10/2008 12:36:56 Re:Yet another Bot thread - Easily made strong bot?|
|Well, if a good programmer wants to hook up, I would love to help build a killer Bot. Let me know! firstname.lastname@example.org. Put Killer Bot Project in the title so I know it's not spam. Peace!|