Team NUS. Lim Yew Jin 1. Overview =========== The NUS entries are based on rtscomp06.game2.simtest_nogfx where a higher-order plan is executed using a preset finite state machine (FSM). Each unit is assigned to a group, and plans are decided on a group-level. For example, a "Join" plan will move units towards each other and complete by assign all units to a single group before passing execution to the next stage of another plan. Units have access to the group order and are able to execute the group order using function calls for moving and attacking. 2. Note on Tactical Combat ========================== Given that the only criterion for a sucessful attack is range, it appears that the optimal strategy is to arrange the units on the outline of the fattening polygon (with length equal to or slightly less than the weapon range) of the convex hull of the set of the enemy units while attacking. This ensures that the maximum number of units can attack a single enemy unit while minimizing the number of enemy units that can return fire. We attempt to maintain this distance constantly. i.e., if an enemy unit retreats, we move forward; if an enemy unit advances, we move backwards. 3. Game Details =============== 3.1 Game 2 ========== 3.1.1 Movement ============== Pathfinding is done using slightly modified versions of the "Force Field" pathfinding libraries found in the libs directory. We modified some constants to allow units to be more compact. When a PATH_FAILURE message is returned by the library, we make a single heuristic step to move out of any potential obstacle and perform pathfinding again. 3.1.2 Influence Maps ==================== We make extensive use of influence maps, where each unit radiates a score of 1.0 for every cell within weapon range and 0.5 for every cell between weapon range and twice weapon range. The score (friendlyInfluence - enemyInfluence) is used to determine whether or not a cell is under own or enemy control. 3.1.3 Attacking =============== Internally, attacking is performed by pathfinding towards the current enemy location. Furthermore, whenever the enemy target changes location, we check to see if it has moved far away. If so, we replan. 3.1.4 Strategy Outline ====================== 1. Decide whether or not bases are far apart and both sets of own and opposing bases can be divided into two halves. 2a. If yes, proceed to a mass join strategy where two groups of 25 units join at a location found to be sufficiently large to accommodate every unit. 2b. If not, join in groups of 10 units by moving to the unit that is closest to an enemy unit and has "sufficient" friendly support (using influence map scores). 3. Merge with any nearby friendly group, if any. 3a. Attack the nearest enemy unit with influence weaker than the current group while following tactical combat strategy. 3b. If no weaker enemy unit is found, then attack nearest enemy unit. 3c. If no enemy unit exists, then attack nearest enemy base. 3.2 Game 4 ========== 1. Form a compact dense circle of units for a maximum duration of 170 frames (heuristically chosen). 2. All units are attracted to (and move towards) the nearest enemy unit to them. 3. Units avoid sheep and other friendly units using a flocking algorithm computing repulsion forces on every frame 4. If a unit detects that there is a friendly unit within a 0.3 radian arc in front of it, it attempts to spread out to form a line by moving perpendicular to the obstacle, towards a less crowded area of the line. This is done by computing the number of units within a 100 unit radius of points 50 units left and right of its heading, perpendicular to its direction of travel. It then travels to the side which has fewer friendly units. 5. The average and minimum distance of all units to their nearest enemy units is now computed. 6. While this average is more than 90 units, use the following policy: 6a. Units whose distances to their closest enemies are more than the average distance to enemy units move at maximum speed 6b. Units whose distances to their closest enemies are equivalent to the minimum distance of all units to an enemy unit move at 20% of their maximum speed 6c. Units whose distances to their closest enemies are equivalent to the minimum distance of all units to an enemy unit plus the unit radius (4 units) move at 30% of their maximum speed 7. When the average is less than 70 units, compute the maximum hit point rating of all units, and compute the corresponding Preferred Combat Range per unit: the number of hit points the individual unit has less than the entire force's maximum number of hit points divided by four. ie, (max HP - unit HP) / 4 All units which are out of range of the future position of enemy units (scaled by 3 frames) move towards their nearest enemy with the following policy: 7a. All units whose distances to their closest enemies more than the minimum distance of all units to an enemy unit move at maximum speed 7b. All units whose distances to their closest enemies are equivalent to the minimum distance of all units to an enemy unit move at 50% of their maximum speed All units which are within range of an enemy unit (less than preferred combat range) move directly away from the enemy unit closest to them. All units within a 0.2 radian arc in the direction in which it is moving away have repulsion forces applied with a magnitude based on the inverse square of their distance away from the retreating unit's future position (scaled by 3 frames). 8. If a unit's destination based on repulsion and attraction is outside the bounds of 50 units away from the map boundaries, then it attempts to test every point in an arc around itself to find a point within the 50 unit boundary, and then proceeds in that direction, theoretically enabling them to slide along the boundaries. (in practice this fails when multiple pursuing enemy units cause its repulsion vector to oscillate when surrounded at corners) ---------------------------------------------------------------------- Team Carlos III, "ALCAZAR SAIZ, VIDAL" <100033425@alumnos.uc3m.es> Here is a description based on the one I wrote for the README file: Our client uses an heuristic planner to calculate a coarse path to minerals using costs assigned to different areas (generally 4*4 tiles, but this can be changed in the definition of COARSE_VALUE). First of all, static costs (those coming from terrain obstacles) are calculated, and afterwards, whenever a worker is going to pass through one of the areas, its cost is updated so the planner may decide that for other workers another path or a different mineral cluster is lest costly. Waypoints are usually the center of those areas, so precision is low. An exception to this happens when a worker is close enough to a mineral cluster or the CC, since no planning is necessary. By this, a certain degree of collaboration is achieved, although right now only simple paths are obtained (mainly due to the fact that the size of the grid, 8*8, is very small for paths with several waypoints to be generated). When the goals are set, finer pathfinding is done using the pathfinding modules SimplePathfinder, ForceFieldPE and SimplePFAdapter. Just as a side note, using planning for every worker is computationally quite costly (around 0.20-0.25 seconds per worker), so the client controls coordination by caching the goals and keeping timers for each worker. If there is not enough time but a worker has its goals set, no pathfinding is used and the workers are sent straight to their goals, but this rarely happens since once their goals are calculated no more calls to the planner are made (that's why once a bit of time has passed, it runs smoother). Probably this approach was a bit strange and not the best one for sure, but we wanted to use planning to see how it behaved in real-time environments. In the end it really does not do much, but still! At least this has given us a bit of insight about the subject, and since it is the first time we participate, we are happy with it :) ---------------------------------------------------------------------- Team UBC, "Zephyr Zhangbo Liu" The description of our entries is shown below: Game2: -Collision avoidance using bitmask. -Divide the tanks into squads according to each CC initially. Each squad will move toward the nearest enemy CC while firing at the weakest enemy within its fire range. -Each squad can have a target which can be a CC, a player squad or even an area. A cooldown time will be assigned to forbid changing targets too frequently. -The squads can merge together into a bigger squad if they are close enough and do not have a target at the moment. -Enemy clustering will be applied. If a squad detects a cluster of enemy is attacking the player's CC, it will evaluate whether it is possible to rescue the CC. If so, it will allocate certain amount of tanks which it believes can complete the mission and then split into two squads: one to rescue the CC, the other continue on its formal mission. On the other hand, squads will avoid big cluster of enemies. -If there is only one player CC left, the general AI will evaluate whether it is necessary to enter another defensive mode. If so, all available squads will assemble at the CC to defend and then assign a squad to attack the nearest enemy cluster. Game4: -Form a Wedge Formation of 5 groups, 10 marines each. -Enemy clustering with distance, followed by Convex Hulls to find "weak" points. -Use Force Field to avoid obstacles and enemy hulls. -Only move inside enemy hull influence when we have 0 cooldown. -Dynamic clustering of our force and divide them into small groups. -We only assign our smaller groups to hull corners, and each corner can be assigned to no more than one group. -We would not assign more than 1.5 times of our force against an enemy cluster ------------------------------------------------------------------------- From: Tomasz Batkiewicz Tomasz BatkiewiczGame 1 strategy: - each worker goes in staight line to the nearest mineral and back, - when it encounter obstacle (terrain, sheep or other worker) it attemps to avoid it, a\ lways on the right side (turning right). Game 2 and 4 strategy: When (almost) all my fighters are synchronized (their position are nodes in grid): (1) selecting nodes (in hex. grid) from which enemies can be attacked (attack range - d\ istance between nodes <= distance from node to nearest enemy <= attack range), (2) evaluating position in each node (depending on distance to 2nd, 3rd, 4th, ... neare\ st enemy), (3) propagating results through grid (using BFS), value in next node = avg from values \ in previous nodes, (4) adding extra score to nodes directly by my fighters' positions, depending on the di\ stance from nearest enemy and average distance to nearest enemy (for all my fighters), and usage of the nearby enemy units while attacking (as many of them as possible sh\ ould be unused after move) (5) setting direction for each of my fighters to the best unused (free) neighbour node. When enemy is in attack range, and my fighter is not in cooldown, it chooses the weakest en\ emy in range (with lowest hp, building only if there is no other enemy units in range). Heuristic (4) makes my fighters attacking in line (they tries to have constant distance to \ nearest enemy), and surround him before they are close enough to attack (especcially if enemy has t\ ight formation). They also try to flee from battle, if other attack group destroys its local ene\ my, waiting for them to help in attack, unfortunately synchronized movement makes them too slow\ to escape without losing some units. Heuristic (2) makes my fighters search for the weak points in enemy formation, and attack h\ im from that points. Enemies with less than 2 allies nearby are ignored. If enemy formation is syme\ tric, this sometimes divide formation in two smaller groups (unfortunately some units cannot deci\ de whitch group they should join), but they are all commanded in the same way (formation don't\ know how many attack group it has). Main source code for this is in method Formation::commit(), executed once per game frame. Some classes / methods / fields are unused, They were used in previous version and I forgot to remove them. ------------------------------ Team NPS, From: "Darken, Christian (Chris) (CIV)" Game 4 description attached. (nps.pdf) For Game 1, we treated each worker as state machine with states such as = IDLE, WALK, MINE. We randomly assign to each worker a target mineral. In = the beginning, each worker tries to go directly to its target mineral. = If this is not possible, it tries to reach a random position on map, and = then to resume its way to target mineral. If this procedure is not = successful for couple of times, the agent tries pathfinding or changes = its target mineral. The same procedure is used when agent tries to reach = control center. To build our client for game 1 we used SampleAI, build = in pathfinding in ORTS and example clients from previous tournament. ------------------------------- Team UMich, From: "Sam Wintermute" Our agents for 1-3 are mostly the same as last year, with a few bugs fixed (although judging by game2 results, not all of them). The game 4 agent doesn't use Soar, it just assigns all of the marines to attack at the start, and the attack manager (same as used in 2 and 3) handles it from there. We have a paper at AIIDE this year on our system, I've attached a copy. (SORTS.pdf) -------------------------------- Team Uofa, (Sterling Orsten) sorsten@cs.ualberta.ca Overall: Team UofA's competition entries are based on a hierarchy of AI "commanders". Although the system is still in its infancy, we have thus far found it highly useful in constructing our entries. The basic notion is that each commander class has a specific goal, and maintains ownership over a set of units which it can use to accomplish that goal. Commanders which have complicated goals can spawn other subordinate commanders, and assign them some subset of their units. Ideally, subcommanders would notify their superiors of a variety of important conditions through event dispatch. In practise, only a few types of commanders actually provided this status notification. Game One Entry: Team UofA's entry for Game One was based around fairly simple principles. A set of "access points" would be generated around the perimeter of each cluster of minerals. These access points represented distinct locations from which a worker would be close enough to at least one mineral to mine. Generally, there could be a maximum of eight access points around a single mineral, although in practise you would expect somewhere between two and four access points. A set of unique routes are then created, each route spanning the distance between the controlCenter and one access point. These routes are sorted by distance, and the shortest routes are distributed to workers first. In a typical game, our entry would load large numbers of workers onto the minerals which are closest to the controlCenter. This was both an advantage, in minimizing overall trip times, and a disadvantage, in that congestion was a larger issue than it needed to be. However, our implementation was re-used to perform the gathering in Game 3, where our design decisions had a couple of important side effects. Game Two Entry: Team UofA's entry for Game Two was a simplified version of our initial design. The entry as submitted works by breaking the set of tanks down into squads based on their proximity with one another. In the typical case, the tanks belonging to each base wind up in separate squads, although it is also possible for two nearby bases to form a single large squad. These squads then hunt enemy tanks independently of one another. Based on whether or not any given unit is within firing range of the enemy, we switch control between moving via pathfinder code and moving via combat code. Our squad combat AI subsystem is designed to keep units clustered densely to maximize firepower while staying outside of the firing ranges of enemies that are not being targetted. Although our implementation does not specifically go after enemy bases until all tanks have been destroyed, it will fire on enemy bases that are passed by squads without a better target. When used against certain opponents, our implementation can take out three or four enemy bases before assaulting the main body of the enemy forces. In the event of a victory over the opposing tanks, our implementation can then quickly defeat the remaining bases, scoring a timely victory. Game Three Entry: Team UofA's entry for Game Three is easily the most complicated. Several commander classes were used to accomplish a wide variety of tasks. Although the entry sometimes fails to act intelligently, it succeeds in utilising the full set of actions available during Game Three. In our implementation, each base controlled by the player behaves in fundamentally the same way. The first priority of any base is to train several workers to provide immediate cash flow. After that, a barracks will be constructed, and resources will be split between constructing additional workers and training marines for defense. The second priority of a base is to maintain a small defensive force. Typically, four marines will be retained at any given base to stall for time in the event of an attack. The third priority of a base is to train additional forces to contribute to a global "attack force" which, once activated, attempts to destroy specific enemy targets. Bases which are under attack will only transfer units to the global force after their immediate vicinity is clear of opposing forces. On a global scale, several important things are happening at any given time. Early in the game, the highest level commander will request small numbers of workers to scout the map, locating other resource clusters as well as the position of enemy fortifications. Later on, scouts will revisit every mineral location periodically in order to find new enemy expansions, and to estimate the strength of enemy forces. Whenever a good opportunity arises, a worker will be sent, along with a small escort, to attempt to build an expansion base. These bases will function essentially identically to the first base, and it is possible in a prolonged game for our entry to construct three or four such bases. Also, if excess cashflow is present after constructing a barracks at at least two bases, we enable the construction of factories, which train tanks to contribute to the global attack force. It should be noted that this entry reuses the gathering code implemented for Game One. Some of the Game One entry's weaknesses serve as strengths in Game Three. Since we make sure to keep as many workers as possible mining from the nearest possible minerals, we avoid the creation of drawn out, vulnerable supply lines. This also helps to reduce fog of war issues, so that only rarely are workers required to travel to mineral locations that are not currently visible to the client. Game Four Entry: Team UofA's entry for Game Four is the only entry not to use the commander hierarchy. Instead, it is run completely on the lowest level. In essence, full control of all fifty units is given to our combat AI, which attempts to manage units effectively in battle. The AI manages such tasks as keeping units clustered densely to maximize firepower, keeping units out of range of untargeted enemy units to maximize lifetime, and concentration of fire on targeted enemy units to maximize kill speed. Some special purpose code is in place to attempt to keep units equidistant from the nearest enemy position, which helps to avoid exposing individual units to enemy fire without support. The entry is meant to demonstrate the low level tactical code that is available to all of our entries. Although our approach was simplistic, especially in light of some of the much more impressive entries submitted by other teams, we had the advantage of a system that was robust when applied to other game categories. Our entries for both Game Two and Game Three were able to make use of this tactical code, which was flexible enough to gracefully deal with terrain and imperfect information settings. ----------------------------------------------------------------------- Team Warsaw B, from Michal Brzozowski (mbrzozowski) In games 1, 2 and 4 we have the same the code for pathfinding and collision resolving. We generate a graph on top of the given obstacles for a single agent pathfinding. The graph in game 1 has one-way edges to avoid collisions as much as possible (workers are moving back and forth all the time). The agents interact with each other using forces dependent on distance and movement directions. The agents repel each other this way. There's not much more to game 1 than this. We assigned workers to the accessible corners of the closest minerals (up to 4 workers on a mineral this way). The algorithms for games 2 and 4 share one common idea. To fire the most shots and to be hit as little as possible, one should stay at the maximum distance from the enemy allowing to shoot at them. We simplified this, and our units stop whenever the enemy is at range. They don't start moving until their area is clean. They shoot at the weakest enemy at range. To make this idea more effective for a large group of units, we introduced a special type of movement we called rotation. Each unit approaching another unit that is currently shooting, has a force attracting it to the left or to the right, depending on a flag. This way the units approaching the battle field move along the line of shooting units, seeking a spot in the line to start shooting. We had no special strategy in game 2. Each unit moves toward the closest enemy unit and shoots at whatever has the fewest hp. In game 4 we implemented moving in formations, several types like a straight line, a "winged" formation, etc. We finally picked a simple type which is keeping the units in one vertical line, but each unit has an enemy unit assigned and it tries to always stay at its y-coordinate. This way we track whatever groups the enemy has made, and for each group we maintain a straight line formation, which we think is the most effective formation for attack. Thanks to the "rotation" movement, our units have a tendency to sorround the enemy if it's not keeping a front line. That's it. I think that our ideas are simple yet effective. I hope to hear from other teams especially those holding high places :).