Ceasar's Mind

Follow me: @Ceasar_Bautista

Posts Tagged ‘strategy

Potential Fields

leave a comment »

So while surfing for a solution to my own AI problems, I found an article on potential fields. I had used these before in trying to develop an AI for Naval Commander, and achieved limited success, but I couldn’t figure it out well enough and so I ditched the whole thing.

Anyway, a potential field is kind of like a magnetic field. Basically, the AI places charges around the map, positive charges near high value targets, and negative ones around dangerous areas and impassable terrain. Allied units use the field by testing a few points around them, figure out where the most potential is, and moving toward the location. By strategically placing the charges, the AI can guide armies in a very dynamic and simple way.

So here our potential field is represented by the lightness of the square, with light squares being more attractive. The rocks, being impassable, and the white enemies, being dangerous, emit negative potential, coloring the nearby squares dark, while the goal areas emits positive potential, lighting the map up. Together, these fields  provide a way for the green unit to get to its destination all without any kind of path finding algorithm.

The article goes on to explain a few useful tricks, such as placing positive charges on top of enemy units to attract allied units to them, and then placing a weaker negative charge on top of them in order to get our units to attack from a certain range. Anyway, I think there is a lot of potential with this idea. I highly recommend you check the article out and you can count on me investigating the idea in the future.

(A thunderstorm won’t let me embed the link. Check it out here for now: http://aigamedev.com/open/tutorials/potential-fields/)

Written by Ceasar Bautista

2010/07/19 at 20:22

Command 0.04

leave a comment »

This update is very minor, but it’s the start of something bigger, of which I’m having trouble with. Basically, I’ve made it so that the AI tries to send the least amount of units to necessary to capture planets. Unfortunately, it only works with terminal nodes:

The new AI works by allowing each planet to store the number of armies that it needs to conduct the AI’s plan. It sends that value to it’s parent node, and that goes all the way up, so that all the nodes know how much they need to conduct the AI’s plan.

The image at the right is a little hard to read, but basically, node A tells B that it needs 2 armies, then B tells E that it needs 10, 2 to capture A and 8 to capture itself. The process, repeats upward.

This works for terminal nodes, so why doesn’t it work for B? The problem, I’m almost certain, is that I’m using a depth first search, and A is never being notified that B is receiving enough forces to capture A.  Now that would be very easy to fix, except that if I did that, then E would never send to B, since it would consider A and B both captured.

Anyway, I need some help.

Written by Ceasar Bautista

2010/07/19 at 17:41

Command 0.03

leave a comment »

Building off of 0.02, I made a few changes to the algorithm. In the old algorithm, the search would stop whenever it hit an enemy node. However, that would prevent it from seeing anything beyond the front line, which could potentially be a problem. If, for example, our base connects to a 10+1 node and a 25+1 node, both the same distance away, our base should probably attack the 10+1 node. However, if behind the 25+1 node is a 0+100 node, then we may wish to rethink our initial decision.

Additionally, I rewrote parts of the code here and there to make things a little more organized for myself. With that, I’ve created an AI for Red, to showoff in the videos anyhow, but for the player I’ve implemented a new system for attacking. Where previously, a player’s click would send all immediately available units to the targeted node, the new system is set up so that it not only does that, but continues to stream afterward. The stream can be disabled by clicking the streaming node twice.

But anyway, here is a video of the new AI in action:

Written by Ceasar Bautista

2010/07/17 at 00:40

Command 0.02

leave a comment »

The initial AI failed because nodes failed to consider the strength of their moves beyond attacking the nodes that they were immediately connected to. This version attempts to fix that, using a depth first search on each node:

The AI still has a way to go though. It makes no effort to keep track of how many units it has sent to a node, often sending more than it should. On the same note, it makes no effort to keep track of how many units the player has sent to a node, or for that matter, could send. Hopefully I can fix that soon.

Basically, it works like this: First it selects a blue node to analyze, then it finds all of its neighbors (called children). If the any of the children are not blue or don’t connect anything except for the parent, then it scores the node by figuring out how much time it would take to capture the node. If the node is blue and has children of its own however, then it analyzes that node, but all the while keeping track of the ancestors so that the current generation doesn’t mistake an ancestor for one of it’s children, preventing infinite loops in the search.

However, through testing the AI I encountered a few problems. Perhaps the worst thing was that I had labeled all my variables weird names, which made it very difficult to track what was going on. When my code performed badly, it was extremely hard to debug because I had not only had to figure out what each variable was doing, but I also had to figure out what variable was keeping track of what. So the point here: Make sure you label stuff nicely. Typically, it’s okay to use shorthand in keeping with your style, but for complicated stuff save your self the trouble and label things nicely.

Secondly, while going through the search the AI actually would overwrite the values of nodes sometimes, so I had to make special variables just to keep track of the scores of the nodes at each level of search.

Written by Ceasar Bautista

2010/07/16 at 19:37

Progress

leave a comment »

So it’s been kind of quiet here lately, and that’s because I’ve been studying up on Java so that I could develop a proper game in order to develop a proper AI. The game here (currently titled “Command”) is based off of Little Stars for Little Wars, almost exactly at the moment, although I have a few minor plans for the future. Anyhow, here is a quick demo:

As you can see, the AI is still in need of work (I just put that together hours ago). But I’m excited for the prospects!

Currently, the AI works by making a list of all the planets it is connected to, and then scoring them. The score is calculated by dividing the gains by the costs. The gains in most cases is the additional production, except of course if the planet is already owned by you. The costs include the distance, the current strength, and the projected strength of the planet when the army arrives. The depth as you can tell, is still rather shallow though, which is why the AI functions so oddly in the video.

Also, I should note, that this AI will be used plainly to understand macro level decision making. I suppose I will have to play around with it in the future in order to make it simulate real conditions a bit better, but at the moment it ought to give a fairly decent idea of how to one should manage armies strategically.

Written by Ceasar Bautista

2010/07/13 at 23:41

An AI for the RTS

leave a comment »

The two last articles on chess and artificial intelligence were written for two reasons. First, to show that the successful development of an AI reveals how a game is to be played optimally, or almost optimally. Second, the development of an AI often reveals how our minds work. 

Combined with the fact that, at least as far as I noticed, I have no idea why I make the decisions I do while playing strategy games most times leads me to want to try and make an AI for the RTS. Typically, when making decisions in RTS games I go by what feels right rather than analyzing my options. And while I suppose I could give reasons for my actions, I don’t think I could give reasons for my reasons.

This problem was especially apparent while trying to design an AI for Naval Commander, a simplified RTS game I developed, I noticed that I couldn’t understand my own decisions. And you’ll notice that my discussion of the RTS focuses on very narrow patterns in a very a complicated system.

As a designer, this is a bit of a problem for me. It basically ensures that my games will come out badly if I try to be innovative with the mechanics and it does a good job at throwing off balance too.

The solution therefore, is to design an AI. The better my understanding of the mind, mathematics, and game theory, the better I come to understand the interaction of the mechanics. From there, I can look at what makes it tick, and reverse engineer its workings to figure out how people think and supplement play and design. However, I’ve thought about RTS AI before, and it’s not at all as simple as the AI for chess. (To be continued…)

Written by Ceasar Bautista

2010/07/05 at 00:55

Prioritizing Targets

with one comment

Not sure where this belongs exactly yet, but I figured it was worth mentioning. In regards to all of these Hit Points and Damage things, there is a way to prioritize which targets you take out besides what’s most convenient and it’s simple really: Determine which unit is dealing the most damage per hit point, and kill him first.

Take for example, Halo 3. Consider you encounter the two enemies above simultaneously. The one on the left is called a Hunter, armed with a large Assault Cannon, and on the right is a Grunt, armed with a Fuel Rod Cannon. Both weapons are extremely dangerous. However, the Hunter is very difficult to kill, possessing thick armor and a large metallic shield on his left arm which no projectile can penetrate, while the Grunt is very easy to kill, possessing no armor and very little hit points.

The decision before you is this: To target the Hunter first and attempt to dodge both weapons while attempting to find a weak spot in its armor,  or to shoot at the Grunt and kill him quickly and then to fight the Hunter alone. Not much of a choice unless you like a challenge.

Mathematics tell us to take exactly the same course of action in RTS battles. Put simply, to figure out which unit to strike first, determine the DPS of all enemy units and divide it by their hit points and then strike the unit which has the highest result. Usually though, this is intuitively obvious.

Factor in Capital

In strategy games though, there is also capital. That is, while in most cases a damaged unit can be regenerated or repaired, sometimes even for no cost besides time, a dead unit stays dead, and is a permanent loss of resources. With this in mind, the priority can shift to striking the unit with the highest cost to hit point ratio.

Ultimately, it comes down to whether or not you can successfully ensure a kill. If it’s not possible, then it’s best to prioritize by damage to health ratios in order to preserve the hit points of your force. Otherwise, it’s significantly better to take out what you can and then regenerate your units before fighting again on much less level ground.

Why Cheap Units Are Still Useful

The idea of worrying about capital losses usually means trying to invest minimally in weak units since they die very easily. I’ve often wondered if I should make a new formula to adjust for this problem, making expensive units less and less cost effective. I think though that cheap units are underestimated. The one power that they have over their more expensive counterparts is that they can be in multiple places at once. Utilized correctly, this feature can overwork an enemy defense and allow you to penetrate where a more expensive force couldn’t. (The trick is to set it up so that the cheap provides provide an extra kick for your other more expensive units, making each one more powerful individually, and then striking the enemy. He’ll be unable to divert his resources as necessary since they are all centralized in expensive units.) However, this is based off of my experiences with Naval Commander, which accidentally was balanced “incorrectly” since the attack mechanism would choose a random target in range instead of focusing on the weak units, effectively making the strength of units scale linearly. I’ll have to play with the idea a little more in the future.

Written by Ceasar Bautista

2010/06/21 at 23:56