חוקים חדשים (?) לקודגורו אקסטרים-6

[CodeGuru]

שלום לכולם,

קודגורו אקסטרים-6 יערך ביום שישי 13.8.2010.

מה דעתכם על שינוי חוקים?
אפשר לשנות שלא כל הפקודות יקחו אותו הזמן (למשל – כתיבה תקח יותר); אפשר להוסיף דברים יצירתיים כגון "שדה מוקשים" (מקום שאם אתה כותב בו, הכתיבה קופצת חזרה אליך); אפשר לשפר את הגרפיקה, להוסיף תנאי עצירה כאשר כל השחקנים שנותרו הם מקבוצה אחת; ועוד…

מה דעתכם?

CGX

[GalDor]

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.

[ybungalobill]

GalDor:
No-one said anything against far call. I mentioned it just as an example of the tendency of just finding a method to increase the fill rate rather than improving the logic.
Also I have no problem with smart bomb in the middle of the gave: you have to think of making your bot polymorphic or put only a small amount of code simultaneously into the arena.

As I see all of us agree that different execution times are good. But we have to discuss the exact timing scheme. Basic guidelines I propose are:
* Memory reads/writes are proportional to the amount of memory read/written in bytes/words. (IMO in bytes)
* Private/protected segments are fast.
* Public segment write is slow;
* Register reads/writes are fast;

And some things to decide:
* Does instruction fetch counts as memory read? (IMO yes)
* How exactly do we count memory/register reads/writes in ALU instructions, JMPs, CALLs, etc…? (IMO this is the hardest issue)
* Do we want to base the timing solely on data transfer or on functionality too (i.e. computing EA took several clocks on 8086)?

RFC

Y. Galka

[GalDor]

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.

[GalDor]

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).

[GalDor]

These rules might not be too realistic regarding arithmatic and read/write times, but they should make the game more interesting.

[shinigami]

שדה מוקשים יכול להיות טוב רק אם הוא יהיה ניתן לזיהוי בדרך זו או אחרת

גרפיקה יותר טובה תתקבל בברכה אבל זה לא כל כך משנה

נראה לי שתנאי עצירה כשהשחקנים מאותה קבוצה רק יהרוס את המשחק

אני נגד שינוי הזמנים של הפקודות
(אולי העלאת האפקטיביות של אנרג'י אבל לא יותר)

מה דעתכם על פקודה שמפצלת את הקוד שלך ואת זמן ההרצה שלך ביניהן?

[ybungalobill]

Hello all!

Your claims are unjustified.

Quote:

… the current call far command has added an interesting
mechanic, and the limits of its technology have not been reached …

Really? The instruction set of 8086 is finite, you know. far call is just the only instruction that wrote 2 words at once. There are no more such instructions, so the possibilities of "increasing the fill rate" was exhausted.

Quote:

… compound instructions (such as repe movsw, call far, pusha,
etc.) should read/write faster than a separate call …

Why? Don't you think it's unfair?

Also explain: what is a compound instruction. "repe movsw" is the only
instruction from your list that merit this title, that's because it's
compound of a prefix instruction and a regular instruction. "call far"
is translated to multiple microcodes just as any other instruction,
like "add [ebx], ecx" is also "compound" in this sense. And pusha
doesn't exist in 8086 (thanks to Oded for clarifieng that for me!).

Quote:

… (this was true on 8086 as well).

Well, in the precise sense of "read/write faster" they didn't. All the read and write took exactly 5 cycles per word. What you mean is maybe that they read/write faster on average per instruction. That is when you take into the account the instruction decode and other internal logic time, then "call far" wrote faster than two separate "call"s.
Although I couldn't find precise timing for 8086 instruction officially published by intel, all other sources seem to agree on them. So, it looks like "push eax; push eax" was faster than "call seg:reg" with 22 clocks / 28 clocks in favor of push, while writing the same amount of memory.

As for your instruction costs I agree in general.

Quote:

נראה לי שתנאי עצירה כשהשחקנים מאותה קבוצה רק יהרוס את המשחק

How exactly is it possible? Justify.

Quote:

אני נגד שינוי הזמנים של הפקודות …

Why? Rationale?

Quote:

העלאת האפקטיביות של אנרג'י

NRG's functionality is too simple. There aren't many different things you can do with it. By making it more effective you'll just force everybody to use it (because otherwise they'll be defeated by those who do) and then it will just increase everybody's speed by some factor… which is equivalent to not increasing it at all.

Quote:

מה דעתכם על פקודה שמפצלת את הקוד שלך ואת זמן ההרצה שלך ביניהן?

Rationale? I can't think of any real use of it. It'll just decrease the variance of the score while remaining the same expected value. Also it sounds much more complicated to implement than all the other things suggested here.

[ybungalobill]

Fix: I meant bx, cx and ax instead of ebx, ecx and eax (of course).
And it also looks like "pushf" is even faster for some reason (10 clocks) than "push ax" (11 clocks).

[GalDor]

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 @loop

It 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.

[shinigami]

לפי דעתי חלק מהשרדות של קבוצה הוא מנגנון שגורם לשתי התוכנות שלה לא להרוס אחת את השנייה ואם יהיה תנאי עצירה כששתי התוכנות האחרונות הן מאותה קבוצה לא יצטרכו להתחשב בזה כלל

הזמנים של הפקודות לא נראים לי בעייתיים אין לי הסבר מתוחכם לזה, פשוט כולם עבדו עם אותם זמנים עד היום אז למה לשנות?

אנרג'י במצבו הנוכחי הוא אופקוד די מיותר למה צריך לקרוא ל4 פקודות וויט בשבילו?
אני חושב שאם היה אפשר לקרוא לו ב2-3 פקודות הוא היה הופך ליעיל, חוץ מזה שאני לא מאמין שכולם ישתמשו בו מהסיבה הפשוטה שלא כולם משתמשים באף אחת מהאסטרטגיות המתקדמות במשחק

אולי הפקודה המפצלת קשה ליישום אבל היא יכולה להוסיף נפח חדש למשחק שבו אתה יכול להישאר עם תוכנה אחת מהירה או הרבה איטיות ולדעתי אם תאפשרו שימוש בפקודה כזו התוצאה תהיה כמה שורדים מאוד מיוחדים

[FSM]

לדעתי אסור שזמן כתיבה יהיה פרופורציונלי למספר הבתים שנכתבו, כי כל הקטע בתחרות זה למצוא פקודות שעושות את מה שאתה רוצה בצורה היעילה ביותר. אם בכל צורה שתפציץ את הזיכרון זה יהיה באותה מהירות ואם פעולות של חישוב יהיו זניחות ביחס לכתיבה, אז בעצם כל השורדים יפציצו בדיוק באותו קצב וזה יצור ניוון בתחרות.
לגבי עצירה כשהשחקנים מאותה קבוצה, גם אם הם הורגים אחד את השני אז אחד ימות והשני ישרוד ונקבל אותה תוצאה, זה מיותר להמשיך את ההרצה.
אנרג'י במתקונתו הנוכחית לא יכול להוות תועלת לאף אחד, גם אם לקדם אותו בכל פקודה, לוקח לו ממש מלא זמן להגיע לטעינה מלאה ואז הוא מאיץ רק פי 2, שזה כלום בהתחשב שצריך להמשיך ולעדכן אותו.
הפקודה המפצלת זה רעיון לא רע בכלל מבחינה תאורתית, אבל זה בקלות יכול להוביל לכך שירוצו מליארדי תהליכים בו זמנית ולא נוכל להריץ עד הסוף. מצד שני אפשר למשל לאפשר פיצול רק אם השותף כבר מת, ואז גם להקטין את משקל הניצחון (כלומר אם בסוף המשחק נשארו שני שורדים כשאחד מהם התפצל יותר פעמים מהשני, הוא יקבל חלק קטן יותר באופן משמאותי מהנצחון).

[pokop]

אני חושב ששינוי זמני הריצה של פקודות הוא סיבוך מיותר של התנאים כיום, שלא
יוביל לשום גישה אסטרטגית חדשנית.

אני חושב שלהשאיר מוקשים בזירה, למשל על ידי פקודה מיוחדת, יכול להוסיף
נופח התקפי חדש לגמרי.

לגבי פיצול של תוכנות, אני חושב שזה מסובך מאוד לתחרות. לעומת זאת, אולי
אפשרות להחזיר לחיים את בן הזוג שלך במידה והוא מת. למשל אפשר להפעיל פקודה
מיוחדת, שתחזיר אותו לחיים, בנקודה בה הוא מת. כלומר שכדי להחיות אותו,
אני צריך קודם לתקן את הקוד שלו, ורק אז להחזיר אותו לחיים.

אולי להוסיף אזור בזכרון, שבוא יהיה תיעוד של המקומות האחרונים ששונו
בזכרון, וכך שורדים יצתרכו להסוות את פעולות הכתיבה שלהם באופן משמעותי.
למשל אם שורד כלשהו משתגר כל כמה זמן למקום חדש, הוא יצתרך עכשיו לשלב בתוך
זה גם כתיבה סתמית, כדי שלא יגלו לאן הוא השתגר באופן מיידי. ואולי אפילו
להשתגר שוב לפני שמישהו יספיק לגלות איפה הוא נמצא כרגע.

כך גם, שורד יוכל לזהות למשל שמישהו מתקרב לתקוף באזור שלו, למשל אם שורד
תוקף באופן רציץ את הזכרון, ואני מזהה את זה קרוב אלי, אני אנסה להתחמק.

זה יכול להעשיר משמעותית את הדרישות ההגנתיות וההתקפה במשחק.

לגבי האופציה להפסיק את הריצה כאשר נותרו רק שורדים מאותה הקבוצה, מבחינת
התחרות זה חסר חשיבות, כי בכל מקרה אותה קבוצה מנצחת. מבחינת זמן ההמתנה
שלנו בזמן שאנחנו רוצים להריץ כמות גדולה של ניסויים, זה בזבוז זמן.

לעומת זאת, לפעמים רוצים לראות אם השורדים משמידים אחד את השני בכל זאת.
לכן יש להוסיף את האפשרות לבחור אם להפסיק ריצה כאשר שניהם של אותה קבוצה
או לא להפסיק.

[ybungalobill]

GalDor, presenting your survivor doesn't make things clearer. I know what the technique is. Note that what you actually say is that the weaknesses of call far haven't been reached yet, that is how we can adapt to this technique to turn it against who use it.

Quote:

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.

Ok, I'll bear with your original terminology. I agree, that's "triangle inequality" in case you know mathematics a bit. But I think also that "push" shouldn't be much cheaper than adding 2 to sp and writing a word (that is the timing metric should be Lipschitz continuous). push was faster than "add; mov" on 8086 because it was a single instruction. Instruction decoding took time, so decoding one instruction that did 2 things was faster than decoding 2 instruction each doing one of these things. I wanted to approximate this behavior by counting the instruction fetches as a memory read. It's not a penalty (because it penalizes everyone in p/m the same way), but it achieves what YOU wanted to do by simpler rules. Lets look at this (assuming sp is in public segment):

                Your rules / your+mine hybrid
push ax             ; 8    /   1+8
sub sp, 2           ; 1    /   1+1
mov [sp], ax        ; 10   /   1+8

call dword ptr [bp] ; 8+8  /   1+8+8
sub sp, 4           ; 1    /   1+1
mov [sp], ax        ; 10   /   1+8
mov [sp+2], ax      ; 10   /   1+8

As you can see there is no so much difference. I just suggested to emulate real behavior, as defining "compound instructions" looks artificial to me.

Quote:

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.

You should know that 8086 is not pipelined. The only thing it does in parallel is prefetching up to 6 bytes from IP while executing previous command. You never need to wait for memory read unless someone else LOCKs the bus. rep movsw worked faster than a loop just because the processor didn't need to decode the command after each memory transfer. You can again achieve this with my rules by not counting the fetch memory read on REPetition.

btw, why you didn't come to the IOI preparation this week? I hoped I could catch you there.
And as we are 4 who like different execution times, help me to persuade the other 3 conservatives please.

Quote:

לפי דעתי חלק מהשרדות של קבוצה הוא מנגנון שגורם לשתי התוכנות שלה לא להרוס אחת את השנייה ואם יהיה תנאי עצירה כששתי התוכנות האחרונות הן מאותה קבוצה לא יצטרכו להתחשב בזה כלל

Hmm… I'm not going to argue with you that 0.5 + 0.5 == 1.0 + 0. Think about this again. Or read what other said.

Quote:

הזמנים של הפקודות לא נראים לי בעייתיים אין לי הסבר מתוחכם לזה, פשוט כולם עבדו עם אותם זמנים עד היום אז למה לשנות?

I ignore the first half of your sentence as it can be interpreted in two opposite meanings (are they problematic or not? explanation of what?). Anyway, "everybody walk by foot, so why should we use this strange technological innovation? How've you called that? ah, a wheel?". You know, rules can be changed to make competitions more interesting. Rules of international competitions do change. Some people, including me, think that CodeGuru X became something different from what it meant to be in the first place. I find this competition boring and unfair with current rules. I want to make it more challenging for everybody.

Quote:

אנרג'י במצבו הנוכחי הוא אופקוד די מיותר למה צריך לקרוא ל4 פקודות וויט בשבילו?
אני חושב שאם היה אפשר לקרוא לו ב2-3 פקודות הוא היה הופך ליעיל, חוץ מזה שאני לא מאמין שכולם ישתמשו בו מהסיבה הפשוטה שלא כולם משתמשים באף אחת מהאסטרטגיות המתקדמות במשחק

You're lucky that I can't formalize human behavior. I agree that not everybody will use it. Of course not! But NRG is a kind of feature that you can predict the implication of it on the game. The prediction is that if it becomes more effective (that is increase your chances to win) it will just decrease the score of those who don't use it. So it becomes mandatory to win.

Quote:

אולי הפקודה המפצלת קשה ליישום אבל היא יכולה להוסיף נפח חדש למשחק שבו אתה יכול להישאר עם תוכנה אחת מהירה או הרבה איטיות ולדעתי אם תאפשרו שימוש בפקודה כזו התוצאה תהיה כמה שורדים מאוד מיוחדים

Ok, lets formalize it. The amount of work you can do in time T is: T*v*C. C is the number of copies you make, and v is your speed. But you said that the time is also proportional to C: v = const/C; so amount of work is T*const, which doesn't depend on C.
You may think that it's still good because if one of the copies is dead, you are still in the arena. Well well… I tried to prove that it doesn't matter, but I see I'm wrong. Actually under some reasonable assumptions the expected time your group is alive grows as ~ln(C).

Anyway, I propose to don't add a way to split your execution dynamically. Rather it's more logical to allow to bring more than 2 survivors from the beginning (or less than 2) and divide the execution speed based on that.

[GalDor]

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.

[מאת]

תגובות