Author Topic: Swapping the top two stack values?  (Read 5015 times)

Offline Trafalgar

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Swapping the top two stack values?
« on: July 14, 2007, 06:46:13 PM »
Has anyone thought of any clever ways to swap the top two stack variables without needing a temporary variable? I haven't been able to come up with anything (yet). (But I'm thinking it may just be impossible)

I'm trying to make branch conditionals, but I can't unless I can swap stack values. That's because I need to keep values on the stack for each conditional, dupe them, and multiply them times the addresses of each store. The problem is that the store command is 'value address store'. If it were 'address value store', I could just dup address mult value store.

This is what it would look like (python-like code on the left, translation and comments on the right after the #) if store commands were 'address value store':
Code: [Select]
    #Branch conditionals:
    if (foo==2):        # *.foo 2 sub sgn abs - ++ (stack holds 1 value now)
        if (bar==3):    # dup *.bar 3 sub sgn abs - ++ & (stack holds 2 values now)
            #Note: The store commands here have the address (variable) and value backwards. It should be 'value address store', and we've written this using 'address value store'. Doing this with the way store really works is probably impossible (without a temporary variable, which would defeat half the point of having conditions on stores).
            sx = 1        # dup .sx mult 1 store (stack holds 2 values)
            up = 1        # dup .up mult 1 store (stack holds 2 values) (if there was no else, this should omit the dup?)
        else:            # - ++ (reverse the topmost stack value) (stack holds 2 values)
            sx = -1        # dup .sx mult -1 store (stack holds 2 values)
            up = -1        # dup .up mult -1 store (stack holds 2 values)
        #end of if/else - pop stack: dup xor inc (stack holds 1 value)
    elif (foo==3):        # dup - ++ dup *.foo 3 sub sgn abs - ++ & (stack holds 3 values - the first is the result of the if, the second is the !if, and the third is the result of this elif): (either TFF, FTF, or FTT)
        sx = 2            # dup .sx mult 2 store (stack holds 3 values)
    elif (foo==4):        # - ++ & (stack TF (if was true), FT (all conditions were false), or FF (a previous condition was true)) dup *.foo 4 sub sgn abs - ++ & (stack TFF, FTT, FTF, or FFF)
        sx = 3            # dup .sx mult 3 store (stack holds 3 values)
    elif (foo==5):        # - ++ & (stack TF (if was true), FF (a previous condition was true), FT (all conditions were false), or FF) dup *.foo 5 sub sgn abs - ++ & (stack TFF, FFF, FTT, FTF, or FFF)
        sx = 4            # dup .sx mult 4 store (stack holds 3 values)
    #end of elif:        # - ++ | - ++ (stack F (a previous condition, or the if, was true), T (all conditions were false))
    else:                # Note that it was "- ++ | - ++" when an elif ends, and "- ++" when an if ends.
        sx = 5            # dup .sx mult 3 store (stack holds 1 value)
    #end of if/else - pop stack: Since nothing else is on the stack: dup xor inc (stack holds 0 values)
    #That's the end of it
« Last Edit: July 14, 2007, 09:01:41 PM by Trafalgar »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Swapping the top two stack values?
« Reply #1 on: July 14, 2007, 10:42:22 PM »
You can try an XOR swap maybe. Not sure how it would work with the stack, though.  XOR swap.

Offline abyaly

  • Bot Destroyer
  • ***
  • Posts: 363
    • View Profile
Swapping the top two stack values?
« Reply #2 on: July 15, 2007, 02:14:17 AM »
I wonder if I can write a proof for impossibility for the stack swap.
Lancre operated on the feudal system, which was to say, everyone feuded all
the time and handed on the fight to their descendants.
        -- (Terry Pratchett, Carpe Jugulum)

Offline Trafalgar

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Swapping the top two stack values?
« Reply #3 on: July 15, 2007, 08:05:53 PM »
It looked pretty impossible to me - unless I put the value in twice, which would defeat the point of the thing (which is to reduce DNA size*).

I did get it implemented by using one memory location and inc and dec to flip it between 0 and 1, and it brought my Guardian bot down from a DNA length of 15 thousand to around 9 thousand, but the store-to-zero-not-popping-the-value-from-the-stack bug is keeping it from actually working. I might try making it write to 1000 instead of 0, but if that still costs energy, then the bot would probably rapidly energy hemorrhage from executing 140 store operations per cycle.

(Plus it's already going to be incurring the inc/dec energy cost from the workaround, which essentially involves using one inc or dec per if, elif, and else statement (unless they have no actual code in them besides more if/elif/else statements))

* I'm probably the only person writing ridiculously complicated bots with numerous conditions attached to almost every store, but I'm guessing that's probably because of the sheer infeasibility of doing such a thing directly in DB's bot language (as opposed to in an easier to understand language, which is translated to DB bot language).
« Last Edit: July 15, 2007, 08:10:23 PM by Trafalgar »

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Swapping the top two stack values?
« Reply #4 on: July 15, 2007, 09:41:51 PM »
I thought about implementing a swap command.  I think it's a reasonable thing to try.  Maybe in a future version.

While we're on the subject, is there anything else that you'd like to see a feature for that's difficult to do with the language at the moment?

Offline Trafalgar

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Swapping the top two stack values?
« Reply #5 on: July 15, 2007, 10:22:16 PM »
Quote from: Numsgil
I thought about implementing a swap command.  I think it's a reasonable thing to try.  Maybe in a future version.

While we're on the subject, is there anything else that you'd like to see a feature for that's difficult to do with the language at the moment?

I can think of two other things off the top of my head:
1. A function that returns x,y coordinates for a given angle and distance (or sine and cosine, but since their return values are fractions, they would be useless on their own, unless what they returned was scaled) - This would be a counterpart to angle() and pyth(). (Or a function that gets the x coordinate, and another function that gets the y)
2. A function that returns an arbitrary root of a number, e.g. a cube root, or whatever. This is just x^(1/y), where y is 2 for a square root, 3 for a cube root, etc, and x is the number to get the yth root of. (This is, of course, only impossible currently because the stack is integer-only.)

Both of those are things that I had a use for before.

Two potential uses for the first one are: Flying around an enemy (there are other ways to do this, though), and arranging bots in a circle.

A while ago, I tried to calculate the radius of a bot in a DB bot script, but couldn't due to the formula for it using cube roots. (FindRadius = (bodypoints * CubicTwipPerBody * 3 / 4 / PI) ^ (1 / 3)) Of course, it would make more sense to put more bot information in sysvars than to encourage re-calculating them in bot scripts.

In the end that turned out to be unnecessary, since the values stored in the eye variables seemed to be relative to bot size. (At the time, I was trying to detect when an annoying tiny bot had managed to get *inside* my bot's radius, preventing my shots from hitting it - and yes, I actually saw this happen).
« Last Edit: July 15, 2007, 10:24:17 PM by Trafalgar »

Offline abyaly

  • Bot Destroyer
  • ***
  • Posts: 363
    • View Profile
Swapping the top two stack values?
« Reply #6 on: July 15, 2007, 11:40:12 PM »
I want sysvars that give me the position of the bot I'm viewing relative to my position and orientation.
Eg: That bot is 300 (unit) ahead and -200 (unit) to my right
This is sort of possible with what we have now, but it's a mess and breaks on large field size.

I want *.robsize to actually update when the robot changes size instead of always giving 120

There were more that I can't remember at the moment.


Quote
* I'm probably the only person writing ridiculously complicated bots with numerous conditions attached to almost every store, but I'm guessing that's probably because of the sheer infeasibility of doing such a thing directly in DB's bot language (as opposed to in an easier to understand language, which is translated to DB bot language).
I think part of your size issue comes from generating the DNA instead of writing it
I'm looking forward to seeing what kind of monster you are making, although I hope it doesn't slow down the sim too much.
« Last Edit: July 15, 2007, 11:43:34 PM by abyaly »
Lancre operated on the feudal system, which was to say, everyone feuded all
the time and handed on the fight to their descendants.
        -- (Terry Pratchett, Carpe Jugulum)

Offline Trafalgar

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Swapping the top two stack values?
« Reply #7 on: July 16, 2007, 12:15:12 AM »
Quote from: abyaly
I want sysvars that give me the position of the bot I'm viewing relative to my position and orientation.
Eg: That bot is 300 (unit) ahead and -200 (unit) to my right
This is sort of possible with what we have now, but it's a mess and breaks on large field size.

I want *.robsize to actually update when the robot changes size instead of always giving 120

There were more that I can't remember at the moment.
I think part of your size issue comes from generating the DNA instead of writing it
I'm looking forward to seeing what kind of monster you are making, although I hope it doesn't slow down the sim too much.

It's in the starting gate now, although it's nowhere near readable (At the moment, I've mostly only posted the generated version of it - what it looks like before being converted/compiled/whatever is much more readable, at least to me ). What I posted would be more readable if I hadn't had it strip out the comments to make the file smaller (The .txt without comments is about 70 KB in size - the original file is only about 30 KB including comments), or if I had left on the option to insert the original source in comments (that would help if you're just reading the .txt, but would increase its filesize rather a lot too).

Having it generated helps quite a lot with reliability, though. I can't make a mistake writing chains of - ++ & blah blah blah when that's all done for me (except that I could make a mistake in coding them to be generated, but that's what planning before coding, and what testing to make sure it's doing what it should be, are for, of course).

I was thinking about when I should release PyBot so anyone could use it, but I'd need to write a good amount of documentation, and perhaps clean up some quirks first - For example, it doesn't follow (or understand) order of operations, so you have to use a lot of parens. If you tried to write "foo>=bar-3", it would think you meant "(foo>=bar)-3". It also throws a compiling error if you write "!=-3", as it doesn't recognize "!=-" as an operator  (You just need a space between the != and -). And the "foo when (conditions) = bar" isn't like any other language I've used, so it might take seem a little unusual (compared to more traditional if/else structures).

Anyways, I'll stop rambling about it now.
« Last Edit: July 16, 2007, 12:17:40 AM by Trafalgar »

Offline googlyeyesultra

  • Bot Destroyer
  • ***
  • Posts: 109
    • View Profile
Swapping the top two stack values?
« Reply #8 on: July 16, 2007, 01:07:52 AM »
Trust me, guardian WILL slow your sim to destruction. One of 'em will bring it down to around 2 cycles per second, and more will put it down to less than one.

I think you've developed a new strategy: Make the game lag enough that no one in their right mind would watch your bot to figure out how it works, and make the code complicated enough that no one cares to decipher it.

For now, I think your PyBot idea is great. However, once we get elseifs, nested conditionals, gotos, and a few other commands, I think it'll be far less useful. After all, you can then code in the defines manually once we get 'em.

Commendations on your amazingly powerful bot. Methinks I'll be bumped to third.

Offline Numsgil

  • Administrator
  • Bot God
  • *****
  • Posts: 7742
    • View Profile
Swapping the top two stack values?
« Reply #9 on: July 16, 2007, 01:48:06 AM »
I'm presently imagining up a new DNA system to allow for more complexity.  Something like a neural net hybrid with the current system.  I'd be interested if you would describe the sort of organization for your bot (reading bot code isn't something I enjoy).  It's definitely a stress test, it think.

I'll start a new thread where we can discuss DNA.

Offline abyaly

  • Bot Destroyer
  • ***
  • Posts: 363
    • View Profile
Swapping the top two stack values?
« Reply #10 on: July 16, 2007, 04:19:29 PM »
Do you think you can reduce the amount of inflation your DNA compiler causes? I forsee a grim future where every bot lags the sim like guardian and one man bucket.
Lancre operated on the feudal system, which was to say, everyone feuded all
the time and handed on the fight to their descendants.
        -- (Terry Pratchett, Carpe Jugulum)

Offline Trafalgar

  • Bot Destroyer
  • ***
  • Posts: 122
    • View Profile
Swapping the top two stack values?
« Reply #11 on: July 16, 2007, 08:45:46 PM »
Quote from: abyaly
Do you think you can reduce the amount of inflation your DNA compiler causes? I forsee a grim future where every bot lags the sim like guardian and one man bucket.

That's what the purpose of implementing branching conditionals was - By using that, I got the DNA length for that bot down from around 15K to around 9K. And it would be even smaller if there was a stack swap operator.

But the main reason Guardian's DNA is so large is that I attached a large number of conditions to a large number of stores. I also let PyBot check almost every store to make sure it wasn't already being set, but that doesn't add a huge amount to code size - it uses dup to avoid recalculating the value. It changes the output code like so:
from: blah blah value calculation here .address conditions mult store
to: blah blah value calculation here dup *.address sub sgn abs conditions & .address mult store
The only things added are one dup, *.address, and sub sgn abs and an &. So that doesn't add a lot.

Yes, there is some potential inflation, though, of course, where a human author would hand optimize something. For example, fairly early in Aura's code, you have it do '*.refypos *.ypos sub *.refveldn add dup mult'. If someone wrote that for PyBot using '((refypos-ypos)+refveldn)*((refypos-ypos)+refveldn)', it would be larger. However, in light of that, I have made it possible to use dup in PyBot. '((refypos-ypos)+refveldn)*dup' would compile exactly to what's in Aura's code there.

(I'm translating Aura's code by hand to be PyBot-compilable to see how it will come out, and to see whether there is anything I can do to reduce the amount of inflation - like adding dup support)

Edit: So far, it looks like it would run faster, but that's mainly because you used sqr in (> and probably <) comparisons, and mult for anding conditions, and PyBot uses floor and & for those purposes instead (it only uses mult to multiply the 1 or 0 result of combining all the conditions by the address).
« Last Edit: July 16, 2007, 08:56:01 PM by Trafalgar »

Offline abyaly

  • Bot Destroyer
  • ***
  • Posts: 363
    • View Profile
Swapping the top two stack values?
« Reply #12 on: July 18, 2007, 04:20:40 PM »
Please forgive any mistakes you find; some have already been pointed out to me >.>
I also think Aura is far from optimized, since I have a lot of "0 sub" type things in there. Thankfully it didn't grow complex enough to need it.
Also, I dont think I used < at all, since it looks ugly to have both kinds sitting there next to each other.
Lancre operated on the feudal system, which was to say, everyone feuded all
the time and handed on the fight to their descendants.
        -- (Terry Pratchett, Carpe Jugulum)