התגובות שלי בפורום
-
תגובות
-
Sorry, some of the post seems to be missing… Here is how it works. The growth condtion is (if q*t*C<1/2, or 1/2>t*C*q. This is also: C<1/(2*q*t). Thus if 1<<1/(2*t*q), growth is almost unstoppable. So: t<<1/(2*q). But q is generally of order 7*(num of enemies)/arena, so we get: t<<arena/(14*enemies). This gives the reason for the invincibility of the replicator.
I see no objections to your timing, but I think that the only way to be sure is to actually try them. Anyhow, I think shinigami wants to implement something like the spl instruction of the original corewars – to be specific, he refers to a replicator that uses its time to create more copies.
Let the odds of a single copy surviving one round be p. Then let us assume that the replication time is t. Then after one replication cycle, your population is:
C*2*p^(t*C)
(assuming that the death of survivors is approximately independent, which is more or less correct for p~1 and neglectiong the acceleration due to death of survivors).
These assumptions are true if you have many survivors…
So you need:
p*(t*C)>1/2
or, since p=1-q where q<<1 is the chance of death,
1-t*C*q>1/2,
assuming t*C<<size of arena. Therefore,
1/2>t*C*q
or,
C<1/(2*t*q).
q is typically of order: 7*(num of enemies)/arena
so: C<arena/(14*t*enemis), and thus if:
arena/(14*t*enemies)>>1, the survivor is invincible. This condition is equivalent to:
arena>>14*t*enemies, so for 6 enemies, you have:
arena/84=65536/84~780>>t.
So if a single survivor can replicate in 10 moves, it cannot be reasonably killed to less than 78 copies. So unless you change ALOT of the timing, a replicator is invincible.The limits of call far have not been reached. It is a technological race between scanner and bomber – but not only them. Here is a simple survivor (I call it "anti-ninja") that was later incoporated (together with countermeasures against enemy "anti-ninjas") into XLII:
mov cx, cs
mov ss, cx
inc ah
mov al, 0xa4
mov sp, ax
mov bx, 0x12
@loop:
add sp, bx
call @loopIt is just another step of the path. Underdog got nearly scanner proofed, but sacrificed firepower and some functionality.
A "compound instruction" means doing several things at once – e.g. adding 1 to sp and writing something shouldn't be cheaper than a push command. Also, rep movsw is more pipelined, as you don't wait for your request for a memory read before continuing. It should write just a little bit faster. pusha was just given as an example to clarify my meaning, and indeed it is unavailable.
These rules might not be too realistic regarding arithmatic and read/write times, but they should make the game more interesting.
Here are my suggestions:
logic/arithmatic=1 cycle
public write=10 cycles per word, where writing one byte counts as a whole word
compound public write=8 cycles per word, same rules
private write=3 cycles per word, same rules
compound private write=2 cycles per word, same rules
private read=compound private read=2 cycles per word, same rules
public read=compound public read=4 cycles per word
No instruction fetch penalty (the additional size, vulnerability, and repair time are penalties enough)
For instructions such as add [bx],[bp+7] you take the slowest process (if ds points to the arena, then in this case it is the write time) and calculate costs by it (so in that case, we get 10 cycles).I'm against late-game smart bombing. It is an "unfair" way to win.
Anyhow, compound instructions (such as repe movsw, call far, pusha, etc.) should read/write faster than a separate call (this was true on 8086 as well).
I suggest a balance that will encourage players to "repair" their own code, which means large read/write time difference and VERY fast logic, so that you need to use heuristics to locate and repair damage. Right now, it's simply faster rewrite yourself completely. This new balance (which will have to be fine-tuned) will bring large survivors into the arena, rather that the 4-5 byte sized survivors we have now.In my opinion, the current call far command has added an interesting mechanic, and the limits of its technology have not been reached. However, some GUI modifications are necessary.
The "different execution time" is a very good idea (although I do think call and call far should take the same time). I suggest that survivors have VERY fast logic and registers and fast access to shared/stack segments. The arena should be slower, with compound operations (such as call far) taking less then twice the atomic operations (such as call). This is both realistic, and gives rise to the possibility of a rapidly reconstructing code, that uses heuristics to fix itself on the run. Dynamically rewriting too much of your code will become too expensive. Also, this would finally make NRG feasible and practical. One final feedback: add a cooldown feature for the heavy bomb (rather than a limited number of them) and make the smart bomb only usable early on (say, first 300 turns) – otherwise it is almost imposible to avoid.
BTW, I don't really like the mine idea – it seems a bit artificial.Regarding the changes people make:
People genrally try to improve their survivor, for instance implementing changes they thought of after they already sent the survivors, but before the competition itself. They can also now optimize certain parameters of their survivors against their opponents (since they now have access to them).
People can also use the smart bombs more wisely now, knowing what series of bytes to "lock on" to.
It is also recommended to scramble all of your parameters (such as wait times, number of bombs, movement speed, etc.) so that people won't be able to optimize themselves to you as well as you optimize yourself to them.
For instance, the main reason that UnderDog got third place last year was because he didn't change himself enough. He was on a tight competition for #1 place with XLII, but we (XLII) managed to use the smart bomb to lock on to a specific set of bytes his algorithm forced him to have. If he had used precautions (duplicated or encrypted code, like XLII) or changed himself enough, this would have failed. He died almost instantly on every fight we had together, and so on the final when we were together every time, he lost almost every time and got third place.
It is generally recommended to make your code impossible to read, so that your enemies can't adapt as well to your strategy – or find its flaws. This can be achieved by finding bugs in common debuggers so that anyone executing your code will get an error message (one version of Apocalypse did this with the cmd debugger, but we didn't implement this because our survivor was too big already). We actually did this using a more subtle trick (read the second post where I posted XLII). You can also encrypt it in a strange way so that debuggers have trouble – for instance, XLII code is split into two parts on the two survivors of the team such that one needs to xor both parts to get the code – which is troublesome to do with debuggers that aren't meant for simultaneous debugging, or with only a limited amount of time.
This is still breakable. The best you can do is simply make cracking your survivor not worth the effort.About code samples – you can get the previous winners through the website, but anyhow, a good example of development would be the introduction of scanners (e.g. HutsHuts and XLII) that turned traditional far callers obsolete (there is a good explanation of this available on a thread by HutsHuts), followed by a new innovation by underdog, that might just turn these obsolete as well. There are a lot of survivors that used cooperation and smart bombs (see XLII, 007Ninja, Apocalypse, Underdog etc.) but the ENERGY opcode is rarely used (it has been suggested to cut it's length by 2 bytes, to make it more usable).
Taking over zombies isn't too common, but it was done several times in the past.
Redcode operates in a completely different way then assembly (eg. no registers) and this makes translation troublesome. There is no essential problem to make a program that eventually has the same output, but the speed will be completely different. Survivors and tricks optimized to run in Redcode will make an 8086 survivor slower than hell. Furthermore, Redcode is deeply multithreaded, while 8086 is not.By the way, for those wondering how we didn't die the instant the engine read:
mov fs, bx
is because of a really nice thing we discovered about how the engine (and apparently 8086 proccesses segment codes). We planned on using that knowledge of us to prevent anyone using a newer disassembler from understanding what we did. The trick is this:
Each opcode associated with segment registers defines the specific register according to three bits. Virtually almost any processor translates them as follows:
000: es
001: cs
010: ss
011: ds
100: fs
101: gs
However, the original 8086 (and the game engine) ignore the first of the three bits, thereby enabling access only to es, cs, ss and ds. As a result, the engine will translate:
mov fs, bx
as:
mov es, bx
while any newer 16-bit disassembler will still display:
mov fs, bx
(note that push is encoded differently, so this doesn't work with it)That gives you a non-natural number!
I have managed to prove that the odd numbers with square roots modulo 0x10000 are the numbers of the form 8x+1. If A is a root of 8x+1, then the others are:
-A, 0x8001*A, 0x7FFF*A
And there four roots, not two!
Anyhow, about division, it too has many solutions – division by 2 gives (if A is one solution):
A+0x8000*k
and division by 4:
A+0x4000*k
and so on. The point is, we are dealing with modular arithmatic, not the normal arithmatic, so even though the equation works, your algorithm won't, and you're neglecting a lot of subtleties.It's more difficult than that – doing sqrt modulu 0x10000 is not like takinga normal sqrt – and there are no negative numbers, as -x is equivalent to 0x10000-x. Actually, you can't even divide by two – 0x4000*2=0xc000*2=0x8000.
No – otherwise it would be too easy to kill other people – I could "hook on" virtually any opcode, thus killing a very large amount of enemies, without actually having a powerfull survivor…
I've had no slowdown whatsover. Furthermore, the engine is written in java, which has an automatic garbage cleaner, so I can't see how there can be any leaks (I have read the code – it doesn't do anything that might cause a leak in a garbage collected language, such as keep an array that grows with each match or something. The code's quite simple and elegant…). Is it possible that this has something to do with your system?
