CODING CONTEST #2

SpaceWar! The name conjures up images of black and white vector graphics, endless quarters fed into the slot, and little lines spinning through space when a ship got destroyed.....

Well this isn't going to be like that spacewar....but hopefully, it will be as much fun.

The Contest Challenge:
Write an AI for a starship. The winner is the program that survives a fight to the finish in the game.

The Rules
Attached to this post are 2 programs:
a) Starship
b) SpaceWar

You only have to modify Starship, SpaceWar is there to allow you to test your program. Within Starship, there is but one subroutine that needs to be changed:
MoveAndFire
This sub determines how to move and who to shoot. ie. it's the AI.
You should also change the initial text that is in the txtReceive textbox. This will be the name of your ship. Initially it is set to "USS Enterprise" so please change it to something else.
If you want, you can also change the ICON associated with the form. This will change the icon that appears in the game.

Game Rules:
a) You start with 200 units of fuel
b) If you end the turn with 0 or less units of fuel, you are destroyed
c) The last ship not destroyed is the winner
d) You use 1 unit of fuel per turn for life support
e) You use 1 unit of fuel per turn if you fire
f) You use 1 unit of fuel for thrusting 1, 3 units for thrusting 2.
g) If you get hit, you lose a random number of fuel units
h) If you are in the centre of the map (defined as +/- 10 units x and y), you refuel at a rate of 5 fuel per turn
i) Movement is newtonian, ie. there is momentum.
j) Movement beyond the edge of the map (defined as +/- 100 units x and y) is forbidden. Your ship will bounce off the edge.
k) Your chance to hit another ship depends on the average range to that ship and the acceleration of that ship.
l) Damage is attenuated by range

You have 2 weeks to complete your program.
Since this is a work in progress of sorts, I reserve the right to change the SpaceWar code and/or the basic StarShip code. I expect that it will be frozen after 1 week though.

Operation Instructions
To run spacewar, you should first run the Starship programs. Each instance of the program running represents one ship. You need at least 2 ships running. Then run the SpaceWar program. On the "commands" menu, select "FindShips". This will tell SpaceWar to seek out the running Starships and add them to it's database. The select "StartWar" from the "commands" menu to begin the battle.

Hints and Ideas
You have to decide where to go and who to shoot. Your movement choices boil down to
a) move to the centre and refuel
b) hide around the edges and conserve fuel
Your firing criteria can be
a) fire at closest target
b) fire at strongest target
c) fire at whoever last fired at you

So pick your strategy carefully.

As always, programs are expected to compile on my machine. Those that do not, or crash, are disqualified.

"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder<P ID="edit"><FONT class="small"><EM>Edited by BillSoo on 07/23/01 11:27 AM.</EM></FONT></P>

Sounds great !

By the way, Bill, I've been away for a while, who has won the first contest ?

Greetz

<font color=green>Do or do not
There is no try</font color=green>

it's brilliant! but it's a tradegy! here in sydney the trial HSC is starting in two weeks...it's gonna be your fault when i fail my final exams billsoo...

but i'm gonna try and have a go anyway...


The fact that nobody understands you doesn't mean you're an artist.

Geez Yoda! You did!

I had that message up for well over a week and you didn't see it? I guess you *have* been away.

Good luck on this one!


"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

*LAUGH* I just thought it was his way of saying "Who's ya daddy??"...

______
Cheers!

are we supposed to code that ourself or will that be one of the changes made later? cuz whenever my ship hits the wall it blows up

Your program will only decide the direction of thrust (up, down, left or right) and who to target. The rules of the universe are set by the SpaceWar program which you do not modify.

Your ship explodes when it hits the edge? I haven't had that effect...I'll take a look at it, but bear in mind that even if you arn't hit, you will use up fuel over time (unless refueling) and maybe that's why you are exploding...



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Yeah, I agree, this sounds fun! I don't think I'll do very well, but I'll try!

Jacob Sheehy
http://www.sheehy.ca

Multitasking - screwing up several things at once

Well.....there is a fair bit of luck to this...

For instance, the initial placement is random so if you happen to be put in the middle, that's an advantage. Or if you are way over on one side while everybody else is clustered together, that's a huge advantage.

For that reason, I'm considering changing the initial placement routines so that these irregularities are reduced. But there will still be an element of luck in hit probabilities, who you happen to be close to etc etc.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

another part of luck will be who gets chosen to be ship number 1. this is only theoretical, but what if everyone decides that their method for picking out targets will be to just go down the line (1 to n). in this case, ship number one could be 10x better than every other ship but will die at the very beginning without getting a chance, just because it happened to be chosen as number one. the best(fairest) way would be to run the battle as many times as there are ships, giving every ship the chance to be #1 and also #n

I also had some other questions...
1. is there a limit to the amount of fuel we can aquire. I know we start out with 200 but can we go above this limit?
2. what happens if one ship runs into another? is that considered a hit, as if both had been shot?

sorry to pester you but I would like to atleast get something decent in and I only have two days to do it. I'm leaving to go camping on wednesday for the next two weeks. Thanks. Adios

You cannot go above 200. 200 is the max. I know I didn't actually code that in the SpaceWar program that I posted, but it's in my copy...

I have considered running the program a number of times so your suggestion has merit. The problem would be if a different program won every time...running it once at least has the advantage of a clear victor.

But hey, I'm open to suggestions. If more people want multiple runs, or possibly single ship duels in a round-robin style, or just one big bash-up, then I'm willing to go that way. Also, if it turns out that most people need more time, like 3-4 weeks, then I'd be willing to go that way too. But 4 weeks is probably pushing it for a simple program like this....



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Sounds like an interesting contest. I plan to enter if I can swing the time.

One question -- it appears that the velocity vectors are reset to zero each turn (in Sub txtReceive_Change). That would mean no momentum and no drifting, right? It also makes the bounce effect (when you hit the edge) essentially meaningless. Obviously, this is contrary to how it's explained in the rules. Am I missing something?

Also, it seems to me that the accuracy penalty should be based on a difference in the vectors of the firing ship and the target ship, rather than just on the target's acceleration.

Good one Rubric, you caught a bug in the code (one of many I'm sure images/icons/wink.gif). You are correct: there should be a drift/momemtum effect. I've changed the code to reflect this.

While you may be correct about the vector effect on accuracy (who really knows though), I felt that it was just simpler to use range and acceleration only.





"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Yeah, I figured the acceleration thing was just for simplicity. :)

Will you be posting an updated version of the code? In the mean time, can you confirm how it will be changed -- I assume you would just delete the lines that say dx = 0 : dy=0.

Yes I will be posting updated versions as time goes by. For now, getting rid of those two equates will do.

There is one other change where the most fuel you can have is maxed out at 200. And some eventlist changes.

Plus I fixed some bugs with the reset code.

As I said, this is a work in progress....

I've attached my current version:





"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

I know this is supposed to be a competition but I am new to vb and I was wondering if someone could explain the code below to me. I thought I had it all figured out but my shots never hit the target so I must be doing something wrong.


*****ORIGINAL CODE*****
s = "MoveFire," & CStr(MyID)
moves = Split("u,d,l,r,uu,dd,ll,rr,ul,ld,ru,rd,l,r,u,d,,,,,", ",")
s = s & "," & moves(Int(Rnd() * (UBound(moves) + 1)))
Do
t = Int(Rnd() * NumShips + 1)
Loop While t = MyID
s = s & "," & CStr(t)
SendMessage GameHwnd, WM_SETTEXT, 0&, ByVal s

***MY CODE***
burn = "0" 'stand still
myID = 2
target = 1

s = "MoveFire," & CStr(MyID)
moves = Split(burn, ",")
s = s & "," & moves(Int(Rnd() * (UBound(moves) + 1)))
s = s & "," & CStr(target)
SendMessage GameHwnd, WM_SETTEXT, 0&, ByVal s

any help in explaining why this doesn't work would be great!

While it is a competition, I also hope it will be a learning experience (both for you and for me) as well as fun.

So there is nothing wrong with asking for help.

To simplify your code:

burn = "0" 'stand still

'myID = 2 'do not set myID yourself. It is assigned by SpaceWar
'and can change during the game
'target = 1 'the list of available ships are in the Ships() array. Be sure
'to avoid shooting yourself...Your ship has the index given by MyID
'if you set target=0, you don't shoot.
'also, the odds of hitting are pretty small at long range

'assuming you have only 2 ships, you could do something like:
target = 1
If MyID = 1 then target = 2

s = "MoveFire," & CStr(MyID) & "," & burn & "," & cstr(target)
SendMessage GameHwnd, WM_SETTEXT, 0&, ByVal s



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

thanks for responding so quickly...but I still think I have a problem. I used most of the simplified code that you gave me (I already have a function that picks out a target and makes sure it isn't shooting itself) and I know that the chances of hitting are slim from far away, but I didn't even get one hit in 67 turns. I never hit myself or the opponent and I am positive that the target value is not set to zero. what else could be wrong?

This won't work in VB4(32-bit), will it?

GamerX:

This is a problem because I want to compile the source code on my system. If you are careful, you can probably write your code so that it can easily be converted to VB6. Then I can compile it and run it.

If you post your code before the contest ends, I can compile it and tell you if it works or not. If not, then you have a chance to fix it.





"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Try it with the SpaceWar code contained in the second attachment above....

There may have been a bug in the original that I forgot about....(I made a number of changes, maybe that was one of them....)



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Out of my grasp, however I would love to see some of the code , I have never done AI or games for that matter, but would love to see how it is done.

"No one can know everything, only so much as to drive us to look for the rest." -PrOpHeT-

Oops, sorry ... *blush*

Seems like this one is going to attract a lot more participants than the previous contest, and good thing too ! I've been staring at the code for a day now and still haven't got a clue how I'm going to pull it off.

<font color=green>Do or do not
There is no try</font color=green>

bill
i've been playign around and i know i shouldn't have
but i've added a listbox to my starship form to try and debug things
and now i think the findwindowex line in the find ships procedure of the space wars form doesnt work
but i've got no idea how to fix it

help? :)
btw this is great fun!

The fact that nobody understands you doesn't mean you're an artist.

Get rid of the listbox and use Debug statements.
I'm guessing the child control is conflicting with another when FindWindowEx is looking for them.

Good Luck
-cl

FindWindowsEx will find all the child controls on the ship program. Since there is only one control (the textbox), spacewar only looks for one control. If you put another control on, FindWindowsEx may find that instead so it, instead of txtReceive, will become the control that gets messages sent to it.

As CL says, use debug statements. Or print to the form itself. Incidentally, you can add controls to the SpaceWar program no prob, just not the Startship program.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

I put a selfdestruct button on my StarShip program and I kept losing - I wonder ... 8D

<font color=green>Do or do not
There is no try</font color=green>

It just occurred to me that debug statements might not work either. The problem is that the Spacewar program will ask the Starship program for the name of it's executable file (so it can extract the icon). If there is no executable (you are running in IDE mode to use Debug and you haven't compiled the program), there will probably be some kind of error.

You might be able to get around this by compiling the program first. Or you can modify the SubmitEXE function so that it returns a hardcoded path to an existing EXE file. Or you can not use debug but instead, write your comments to a text file or to the form surface. eg:

me.print "hello world"


"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Since it seems that the program may not be as clear and obvious as I, the author, expected (go figure) images/icons/wink.gif, maybe some psuedocode will help:

a) 2 or more starship programs are run
b) the spacewar program is run
c) from the menu, "FindShips" is selected
- spacewar uses FindWindow to find a window with the caption "Starship Program" - SO DON'T CHANGE THE CAPTION
- Having found the window, spacewar changes the caption so it doesn't find it in the next search
- spacewar uses FindWindowEx to find all the child windows (controls) on the main window. Since there is only one control (txtReceive), it stops at the first control it finds and records the hWnd of that control
- spacewar reads the text string that is contained in the control and uses it as the ships name
- spacewar then proceeds to send various bits of text to txtReceive which causes a Change Event in the textbox
- each change event causes the text received to be analyzed and the proper data is extracted
- one event, SubmitEXE, requires the Starship program to return its pathname to SpaceWar
- each event contains a REPLYMESSAGE API call that tells SpaceWar that it's message has been received
d) from the menu, "StartWar" is selected
-the program processes a series of turns until the number of ships is < 2. At this point, a winner (if any) is declared.
e) for each turn
- spacewar asks each ship for its movement orders. It then processes these orders to calculate the new position
- after all ships have moved, spacewar calculates the range between ships at the start of the turn, and at the end, and uses the average range and acceleration to determine if a ship hit it's target, and for how much damage
-after all ships have fired, spacewar examines each ship to see if it has exploded (fuel < 1). If it has, then the LAST starship in the array is COPIED OVER the dead ship, then the array is reduced in size by one. This has the effect of removing the dead ship from the array. It also has the effect of CHANGING THE ARRAY ORDER
- so the final step is to update all surviving ships with information from the ships array. We also reset the ship id just in case it changed when the order changed.


Your job is to maneuver your ship and to select a target. You have several bits of info to help you with your decisions.
a) you know your own location, velocity and fuel level
b) you know the enemies last location, last velocity and a rough estimate of fuel level
c) you know who shot at who last turn (eg. who shot at you)
d) you know how much each action costs:
- life support = 1
- accelerate once = 1
- accelerate twice = 3
- fire = 1
- refuel = add 5
e) you know the basic hit algorithm
if a random number between 0 and 100 > (average range * (acceleration + 1)) then you hit
if you hit, then damage = ((random number between 0 and 4) + 5) * 10/(range + 1)
- basically, you cannot possibly hit if the range > 33 and acceleration is 2, or if range > 50 and acceleration=1 or if the range >100
- secondly, damage goes up exponentially the closer you get.

Hope this helps.

"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

say, do we assume no friction?

Friction is not a concern.

Except possibly if you hit the edge of the map. Your velocity will be reversed (elastic universe) and cut in half (not perfectly elastic).

Anyway, you don't have to code this...it's already in the SpaceWar program. But I suppose knowing this might help you design your AI.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

I don't know if this is how it is supposed to be but from the first description of the game it seems a ship should refuel at 10, 10. however the ships do not begin to refuel until they are within 9 units away.

Well, the actual code says

<pre> <font color=blue>If</font color=blue> (.x < 10) <font color=blue>And</font color=blue> (.x > -10) <font color=blue>And</font color=blue> (.y < 10) <font color=blue>And</font color=blue> (.y > -10) <font color=blue>Then</font color=blue>
.Fuel = .Fuel + 5 <font color=green>'add fuel for refuelling</font color=green>
<font color=blue>If</font color=blue> .Fuel > 200 <font color=blue>Then</font color=blue> .Fuel = 200
EventList.AddItem .Name & " refueling"
<font color=blue>End If</font color=blue>
</pre>

so you are correct, you refuel if abs(x) and abs(y) are both < 10.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

what does it mean if I get a run time error 6, "overflow" when i run my ship in the main program? it only happens about a 1/4 of the time so I don't have a clue how to fix it.

another little thing that I noticed is that the scrolling window on the bottom left that holds the ships' names never resets so the names just keep on piling up. I don't know if this hurts anything though...

I've noticed that any variables you use in your Starship form do not reset when you reset the game from SpaceWar.exe. Your overflow error might be caused by an integer value exceeding 32000. (I had a similar problem with a boolean var that wasn't getting reset-- it didn't cause an error, but caused my ship not to work right.)

Work around: Reset all your variables manually in Sub SubmitEXE in the starship form.

Are you saying that:
a) you are running starship compiled
b) space war is running from the IDE
c) you get a runtime error in starship?

If you want, you can post your starship code or if you want to keep it secret, sent it via e-mail.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Bill, are you now an Admin rather than a Mod?

______
Cheers!

No (sarcasm), he has an "A" next to his name for kicks...
Lol...

-cl

I was promoted images/icons/smile.gif...


"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Well, definite congratulations are in order!!

______
Cheers!

Yes! Congratulations!

Gratz Bill ! I've got a question for you : about one third of the time I can't connect to the website. Any idea what's causing this ?

<font color=green>Do or do not
There is no try</font color=green>

No. I'm just an administrator; I'm not the webmaster.

I can guess, but then so can you....


"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

hey, guys ... this all looks very fun and all ... i like the idea of AI ... i used to work with a lot of games that delt with recursion that would single out wrong moves by the computer opponent so that playing the computer opponent would render the opponent quickly impossible to beat ... i'm not sure if this applies to this game because i don't have the time to try it ... but i just like AI

elbow deep within the boarder line. show me that you love me and that we belong together.

If you are talking about a kind of tree searching algorithm, then I would say that it would not be that applicable here. There are a number of key differences:
1) the game has simultaneous movement rather than sequential
2) the game has a random element in the "to hit" calculations
3) It would be relatively easy to find all possible moves for a turn, but evaluating each move would be difficult...



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Yeah, it is hard to get the AI to be remotly smart, I mean making a good decision, but that's just me...I'll keep working

Jacob Sheehy
http://www.sheehy.ca

The more I C, the less I see.

BillSoo, I hope I'm not stepping on your toes, but I thought others might find this modification of your code useful. I did not change any of the functional stuff. I just changed the display so I could see the whole battle field, and highlighted the refueling zone. The ships appear as little dots now, instead of space shuttle icons. I also slowed it down, so you can watch it easier (with a "fast" button, if it gets boring.) To me, it's a lot easier to test when you can see everything that's going on.

If anyone is interested, you can also make one of the ships a different color (so you can track it easier) by changing the value assigned to TestShip in the Form Load procedure.


Anyway, I'm having fun working on my ship. I'm surprised there is no strategy discussion here. I guess everyone is being secretive. (Either that, or nobody's playing....) Does anyone want to post any test ships?

I used icons because the spacewar program will strip the existing icon from your startship program and use that. Therefore, it's possible to design your own ship icon.....

But I agree with your other changes.

I have received a submission from SRFNAKED. He sent it to me privately via E-mail. Now I would normally require entrants to post their code publicly, but in his case, he sent me the code and left for 2 weeks vacation. Therefore, he won't have a change to modify or fix his code. To make it a bit fairer then, I've decided not to post his code until the end.

In a 2 ship system, strategy is quite simple. Move to the centre and shoot the other guy; but in multiple ship systems, it gets a lot more complicated....

Since everybody is driving for the centre, I've seen cases where the first few ships to arrive blow each other up before the others get there. In cases like that, slower is better.

But what if you had a few ships that arrived first and instead of targetting each other, picked on the more distant ships? They would have an advantage, being at the center and all and would probably win...

Who do you decide to target? It's ususally a good idea to shoot at whoever shot at you last. But if nobody did, or if multiple ships did, then you have to decide. You might pick the closest. That way, you will do the most damage with your shot. But it also means that he will likely fire back, and since he's so close, you will *take* a lot of damage in return.... Another idea is to attack the strongest. If enough "weaker" ships did that, he won't be strongest for long....or you can attack the weakest. If you blow him up rapidly, that's one les ship to worry about.....or pick on someone who everybody else has shot at. That way, he may not target you but pick on one of the others....

A whole range of options comes into play when you have multiple ships, including simply not firing at all....


"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Yes, those are good points. I was also thinking of checking the vector of potential targets. A target that appears to be close, may actually be travelling so fast (+10 or +12) that it really won't be that close when you fire. Likewise, a ship that appears to be more distant, may end up right on top of you.

I'm also considering a little maneuvering within the central zone. In general, it's not useful to accelerate once you're in the refueling area. Yes, opponents get a reduced chance to hit you, but the amount of reduced damage does not offset the extra fuel usage. On the other hand, if you're stuck BETWEEN two other ships, and you're the closest target for both of them, it is worth moving.

so i run the two programs and find ship
then nothing happens!

~

I think you have to have two ships running. Make a copy of the starship program, and run both copies. Then run Spacewar and it should work.

When the contest is over, I will be interested in what other people come up with, so if we could organise something where the top 3 coders post their code, or something like that? I would love to see the results

Jacob Sheehy
http://www.sheehy.ca

The more I C, the less I see.

OK we are now getting close to the deadline and so far, I've received 2 submissions, both by E-mail and both because their authors were going to be out of town this weekend.

Well I'm going to be out of town this weekend as well so any other submissions sent by E-mail WILL NOT BE RECEIVED. This is because my address given is my work address and I don't check my work mail when I'm home or away.

So POST your code if you want to compete.

The contest winner will be determined on Monday night. However, if there are a bunch of you writting ship code but need more time, let me know and I may extend the deadline.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

hey
can we have a deadline in GMT bcos monday night means nothing to me here in sydney

thanx...


The fact that nobody understands you doesn't mean you're an artist.

OK, 12 midnight monday evening. Greenwich Mean Time.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Sorry to have missed out on this Coding Contest. How often do you have these?

It depends on how many people seem interested. Since I only got 2 entries to this particular contest, the next one will probably be awhile coming....

"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder

Well Bill, doggone it I wanted to but right now I just don't have the time. Now if this darned accounting thing would come together I'd have a little more free time. images/icons/smile.gif

Don

Time is the best teacher; unfortunately it kills all its students.

gimme one more hour.... i'm just home from an english exam and its 12:30 pm....

The fact that nobody understands you doesn't mean you're an artist.

ok here it is... i could probably outsmart this spaceship in a hot air balloon... it goes into orbit around the centre instead of going in there... ohwell
still lots of messy code for everyone to enjoy
and if you want to see what it's thinking, it leaves a file called "log" & myid & ".txt" showing what it shot at and where it thrust each turn and why
theres a really funny bug going on, i dont know why, but, as the log shows, the dx/dy values often come up as 0 or something that they're obviously not; the ship's decision is based on the values in the log though, and not the actual ones, so.... thats where i think most of my problems are at the moment.

anyway
thanks billsoo, it was a lot of fun working on this
pity not many others entered
i guess maybe it was a bit hard though

next time ...mmmm... a cricket simulation, or swimming ;)

The fact that nobody understands you doesn't mean you're an artist.

Contest is closed.

I will have the results shortly.



"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder