Towards a good StarCraft bot - Part 0 (Preliminary) - "Simplification"
A couple days ago I got inspired by a question in the BW forum: “What would be a good strategy for a Brood War bot?” At the same time, I read an article by a StarCraft developer, written in 2010. Without wanting to offend anyone, I was shocked by the apparent low level of software engineering exhibited. If a leading game developer writes an entire article on the issues of double-linked lists, then there must be something amiss. The topic is far too simple to present a real issue worthy of discussion. It feels a bit like wanting to educate people on the advantages of automated testing in 2016. Clearly, game developers are very creative people and the BW team has accomplished a master piece. But when it comes to solid engineering I fear they are lacking (even accounting for the fact that software engineering as a whole was much less developed back in the days).
It is not a coincidence that the most robust and solid (software) engineering takes place in contexts where quality is a matter of life and death. Examples are the airline industry, the health industry, or NASA. I encourage game developers to take a look beyond their own horizon and adapt best practices cross-industry-wide. However, I will not go into software development. At least not for now. But I do want to point out some general strategies and concepts throughout this series that should help create solid products.
Note for example, that there are two approaches to reducing errors in a (software) product. You can either invest into
Minimizing the introduction of errors
Finding and fixing existing errors
In theory, executing 1) perfectly is sufficient. In practice, it is impossible. The reason being that even standard software development is way too complex for any single human to fully comprehend (try writing a simple bug-free algorithm on your first attempt without compiler support if you don’t believe me. You will fail). This is why entire test labs have been built and testing can easily take up to 50% of the development effort. Obviously, investing into 1) is still well worth it, because it reduces the effort needed on 2). We must remember that the days are gone where 1 or 2 genius developers would create an engine within a few weeks, sleeping in the office and injecting caffeine directly into their veins. Nowadays entire teams work on single components. This bears an additional risk: The code is only as solid and robust as its weakest contributor. Moreover, this not only holds for the present, but also for all future contributors to come. I once made the mistake to introduce a really fancy aspect oriented mechanism when consulting for a corporate. It allowed for completely non-intrusive testing (that means, the productive code was completely free from test code, which is good). It was quite elegant, but unfortunately people did not understand the concept of aspect oriented programming at the time. When I looked at the code a couple years later, my contribution was gone. It had been replaced by an inferior, but simpler mechanism. Of course, as a newbie holding a master’s degree fresh from university I myself broke many a concept as well due to failure of understanding the underlying architectural principles.
Lesson learned: You have to account for the fact that team members come and go and that the average programmer is… well… average. In order to create solid and robust code you need to design towards that average programmer. Else he will break it. And doing so means: simplify, simplify, simplify!
What does this have to do with StarCraft bots? My point is: When attempting to design a good StarCraft bot (note: so far nobody has succeeded!) you need to simplify. Simplify massively. The whole problem space is just way too complex for anyone to comprehend and appreciate right away. Especially in the limited scope of a master thesis, which seems to be a common context for bot developers.
It is worth more to beat a progamer in one single matchup on one single map in a BO5 than to be ranked D on iccup as a bot playing all 3 races.
Here I present mechanisms in order to reduce the problem space of StarCraft bot development. Some or many of which will seem obvious. I list them nevertheless for the sake of completeness. They do hold no matter what kind of bot you write. Whether you program a 4-pool rush script or a sophisticated AI using machine-learning, data mining, Bayesian networks and what not. You might object and say: “But this will not be a true bot! It is far too limited!”. Let me assure you it is much easier to start specialized and then generalize than the other way around. Einstein is my witness! (special theory of relativity: 1905, general theory of relativity: 1916)
Pick only one specific matchup. That is, one race for your bot, one race for your opponent.
Arguably a mirror matchup is easiest.
Pick only one specific 2-player map.
Remember that different maps can have subtle differences that are very difficult to handle. Like Wall-ins depending on spawning location. Such complexity is distracting during development.
Keep your spawning location constant as long as possible (sooner or later you will have to cover both).
Pick only one specific strategy
Every decent amateur knows that it is immensely helpful to have a game plan and to stick to it as much as possible during a game. They also know they should stick to a single strategy across multiple games while practicing rather than mixing it up every single game, because consistency facilitates learning. This also holds for bots. Having one single strategy will e.g. greatly simplify your manual or automatic replay analysis when optimizing at a later stage.
Being the aggressor limits the number of possibilities and hence simplifies decision making. Be active rather than reactive.
Obviously an advanced bot can deviate from the initial strategy in order to react to scouting information, etc. But it is still easier to deviate when there is only one strategy to deviate from.
Start with a (small) subset of all available units
It probably makes little sense to attempt to incorporate fancy defiler and queen play right from the start as a Zerg bot. Try e.g. Hydra/Ling first
Modularize. Break down aspects of the game into as small components as possible. Examples:
Mining resources
Expanding
Moving around the map
Terrain
Scouting
Wall-ins
Attacking
Defending
Micro units (each own unit type against each opponent unit type)
Identify absolutely relevant components depending on your strategy and drop the rest (to start with)
E.g. don’t worry about wall-ins until you consistently lose to rushes
Use “broad strokes” rather than very elaborated local optimizations when threating each of the identified components
Yes, it is more efficient to mine from the closer mineral patches first, but why not start with a “trivial” mining module
Yes, two marines can outmicro a Zealot. But why not use the simplest possible algorithm to do so before attempting to account for other units, terrain, hit-points, etc.
The last point on broad strokes is of particular importance. Simplification is two-fold: Simplify the problem by reducing the problem space (specialize) and simplify the solution by focusing on the main case (generalize).
IIRC the last grand finals (2015) consisted of a Zerg expanding all over the map and massing hydras destroying a 2-base turtle Protoss attempting to max on carriers 3 times in a row -> 3-0.
maybe you and I have different understandings of "good", but I am not impressed.
IIRC the last grand finals (2015) consisted of a Zerg expanding all over the map and massing hydras destroying a 2-base turtle Protoss attempting to max on carriers 3 times in a row -> 3-0.
maybe you and I have different understandings of "good", but I am not impressed.
nice showcase, LetaBot! I have read a couple of your posts before. It would be interesting to hear from you what of the points that I mentioned you followed during development. To you have anything to add or correct based on your experience? Your article on mineral mining would be an example of a very local optimization (http://www.teamliquid.net/forum/brood-war/484849-improving-mineral-gathering-rate-in-brood-war for reference)
On August 13 2016 05:47 imp42 wrote: nice showcase, LetaBot! I have read a couple of your posts before. It would be interesting to hear from you what of the points that I mentioned you followed during development. To you have anything to add or correct based on your experience? Your article on mineral mining would be an example of a very local optimization (http://www.teamliquid.net/forum/brood-war/484849-improving-mineral-gathering-rate-in-brood-war for reference)
You will lose every AI tournament. It might be useful as a test bot for the other bots to take on. A benchmark of sorts. But to start out with only 1 match up in mind and them going to one that can do all 4 (random included) would be very inefficient compared to making a bot that can play all 4 straight away. After all, you will have to switch against a random player.
- Pick only one specific 2-player map
Same problem as above. Translating this into a full bot later on is very inefficient
- Pick only one specific strategy
Same problem as above.
- Start with a (small) subset of all available units
Same problem as above.
The thing about all these four points is that you are basically describing a rush bot. There is a reason that LetaBot isn't a rush bot anymore. And even when I was programming on my rush bot I made sure that eventually it could turn into a macro bot (which it did). But if I designed my bot with those principles in mind from the start it wouldn't have gone beyond being a rush bot any time soon.
Instead the way you simplify the game state would be things like the influence map that my bot uses. In the game vs fischei you already saw the heuristics based version in action.
Another way would be the combat simulator in UAlbertaBot.
- Modularize.
AFAIK All top bots do this
- Identify absolutely relevant components depending on your strategy and drop the rest
You will need at least some simple heuristics to deal with the other aspects of the game, unless you are making a rush bot and never plan to go into the mid game.
- Use “broad strokes” rather than very elaborated local optimizations when threating each of the identified components
Bots that specialize in 1 certain aspect of the game tend to do better than the more general bots. So far the only bots that have taken some games off C level players have been bots that have such specialty.
So to summarize, you are better off reducing the game state as a whole through things like combat simulators or influence maps, instead of trying to restrict the gameplay itself.
The only case where I could see this being a good thing is if you are testing a specific module. For example, for my mineral gathering algorithm I used a map setting where my bot wouldn't be attacked and would only have to produce 1 supply depot.
Another example would be using a micro tournament map to test your unit control algorithms, then integrating the best one into your bot.
But as a whole, if you want to create a good bot you will have to have your bot be able to play a lot of different maps, all the possible match-ups it can face, change build orders and strategies when needed, and be able to use almost all units (you don't necessarily need valkryies as a terran for example).
LetaBot, so you dismiss most of my arguments. I absolutely respect your view, especially since you also have results to back it up, but I can't say that I agree.
Just to give you a better perspective and not with the intention to impose some kind of "authority", some of my qualifications:
[2016/12/8: edited out list]
Again, I list this mostly because I have kept a rather low profile here so far, and only as support - not evidence - that I do know a bit about software engineering.
IMHO, if we talk about good practices, knowledge of two books is crucial: The Pragmatic Programmer Clean Code To people who don't know them: they will help you tremendously. I have many more recommendations if anyone is interested.
Anyways, I have a whole series planned. So I am looking forward to an interesting exchange and hope that even you (LetaBot) can take away one or the other learning or alternative point of view.
Are you honestly serious with that last post? Your initial post was already quite funny considering you thought you were coming up with some revolutionary ideas on how to approach bot development but now you start listing your irrelevant accomplishments (regardless of the silly pretext you give) to give your trite suggestions power and to try and dismiss LetaBot.
Instead of being so pompous, actually come here and show us some of your skills in action. Develop your own bot and show us how superior it would be.
B-royal I am not dismissing LetaBot. I have read many of his interesting posts and respect what he has done. While he is quite exposed through his contributions, he has no idea of who I am. So I thought I would give some background info that is relevant to assess my knowledge and experience. And yes, I feel every listed point is relevant, else I would not have mentioned it. You do not know my accomplishments in sports nor do you know how many instruments I play or how much money I make. Because that would be truly irrelevant.
[Edit] In case said relevance is not immediately clear, I picked some of the less obvious: - MAS in Management: gives me the economics and knowledge management perspective. The theory behind SC economics - Software Architect: able to design large-scale software architectures at a higher level - Tester: knowledge of testing concepts that facilitate bot testing, as well as error classification - founder of several companies: entrepreneurial characteristics. Gives me a "let's see what we can do with what we have" attitude rather than the "let's see what we need to have in order to achieve x" attitude - Member of Mensa: able to reason on an abstract level, comprehension of abstract concepts - languages: natural language processing of course an important sub-field of AI. It gives me a much better understanding of how grammar, syntax, and semantics work.www.unlweb.net or www.ithkuil.net could potentially turn out to be useful for an AI [/Edit]
Please also note that this blog post is labelled "Part 0" Preliminary. I felt the need to express some general thoughts first. Part 1 will be on StarCraft economy, from an economics perspective. I will explain what a Production Possibilities Frontier is and how it can be used to limit the space of what an opponent can have at any given time in the game.
On August 14 2016 11:56 LetaBot wrote: Are you going to create your own bot imp42?
Also the Production Possibilities Frontier is already covered by the build orders text mined from liquidpedia by Dennis Soemers.
Those build orders take that into account.
Yes, I am thinking about creating a bot I am in the fortunate position that I don't really need to work atm. That is, I can take a sabbatical and invest a couple of months in a bot.
I had seen the BO mining, but honestly I am not sure at all that it suffices for what I have in mind, for 4 reasons:
- it is very discrete and not complete. If at some point in the future an AI wants to take advantage of the PPF in order to come up with its own timings, then we need a more continuous approach
- the main application of the PPF is to limit possibilities of what the opponent could have at a given point in time based on incomplete scouting information. For an AI, I don't want to hardcode: "if starport at time x, then no Zealot upgrade possible yet" etc.
- the mined BOs AFAIK are based on actual games played by human players. We know that bots have other possibilities, e.g. regarding efficient mining. This potentially alters the BOs. As a minimum, it alters the timings.
- last but not least, there is no guarantee that the mined BOs are in any way optimal
On August 14 2016 11:56 LetaBot wrote: Are you going to create your own bot imp42?
Also the Production Possibilities Frontier is already covered by the build orders text mined from liquidpedia by Dennis Soemers.
Those build orders take that into account.
Yes, I am thinking about creating a bot I am in the fortunate position that I don't really need to work atm. That is, I can take a sabbatical and invest a couple of months in a bot.
I had seen the BO mining, but honestly I am not sure at all that it suffices for what I have in mind, for 4 reasons:
- it is very discrete and not complete. If at some point in the future an AI wants to take advantage of the PPF in order to come up with its own timings, then we need a more continuous approach
- the main application of the PPF is to limit possibilities of what the opponent could have at a given point in time based on incomplete scouting information. For an AI, I don't want to hardcode: "if starport at time x, then no Zealot upgrade possible yet" etc.
- the mined BOs AFAIK are based on actual games played by human players. We know that bots have other possibilities, e.g. regarding efficient mining. This potentially alters the BOs. As a minimum, it alters the timings.
- last but not least, there is no guarantee that the mined BOs are in any way optimal
I hope that makes sense to you.
You can make a PPF sure thing. Just don't forget that in the way you described it so far, you don't seem to take into account build orders that rely on faking a different build order.
EPT
Fake Fake Double (vs. Protoss)
