Jump to content
Sign in to follow this  
  • entries
    45
  • comments
    67
  • views
    16762

Warning: Brain Dump

Sign in to follow this  
Stagz

202 views

I've been working some on the "HexWars" game that I mentioned a few months ago, and have come up with a (nearly) playable version. Before I put out a version for y'all to play there are a few things that I want to finish off. One of those things is a computer player.

I have been toying around with the idear of how to make an "intelligent" computer player for a while. Taking the example game screen below (slightly altered image), I'll explain some rules and possible options for the player.



This image shows a state of the game board. Assuming that it is currently the "Yellow" player's turn, they have the following options:

1) Split the 99 troops up onto three squares, creating a defensive perimiter.
2) Move the 99 troops to a single square, preparing to attack.
3) Leave the troops where they are, to protect the resource node that they are sitting on. (a resource node will create more troops at the beginning of the owner's round).

Working through the problem in my head over the last few days, I realised that the computer is not smart enough to identify any one of these strategies, let alone decide which is best. Therefore, we will need to come up with some other set of generic pre-defined rules for it to decide which move to take.

In order to get the computer to identify which moves it will take, I was thinking about a few different strategies. The first that came to mind was a "brute force" method. This method would entail the computer listing all of it's possible moves, then all moves that could stem from this initial move (would need to be restricted to a certan depth), calculating the validity of the move using a points system. Unfortunately, like most brute force methods, this method would require too many calculations with a O(6n^D) (i think)complexity.

The next thing I though of was to map opponents troops, and get the computer to "move" it's troops towards the opponent. Unfortunately for this method, it would require the computer to calculate a path to each of the enemy troops, and decide on which ones to head towards. Not quite well thought out enough, but it did lead to a good enough google search :).

The google search identified a method known as Influence Mapping, that may be able to lend some intelligence to my compuer player. Basically, you start with a map of the important cells, and calculate their influence on the other cells. This is kind of where I was heading with the troop mapping, but lends it's self to allowing additional strategies to be implemented, such as defensive, offensive, or even "collect resource nodes". The neat thing about influence mapping is that it will allow the computer to identify a path for it to follow. For example, supposing an influence map based on the troop positions of the computer's opponents, the following influence map would be produced:



So, the movement that the computer would take in this case is fairly clear. It would move all 99 units to the next node marked 17, then the following turn (assuming that the state remained similar), it would probably move to the one marked 18, then 19, then attack the one node that has 20 opposing troops.

I'm sure that I haven't figured out all of the problems associated with this method, but it does seem to go a long way towards having a relatively intelligent computer player to combat. It would also give me the ability to allow the computer to have various different "strategies", based on which nodes get given the initial points.
Sign in to follow this  


1 Comment


Recommended Comments

Have you considered the alpha-beta pruning method to help cut down the number of moves you need to search via the brute force method? It still often blows up exponentially as you go further down the game tree, but if there's only a couple of "sensible" moves each turn (and I don't know if this is the case in your game) it works fairly well.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!