התגובות שלי בפורום
-
תגובות
-
יש לנו בעיות טכניות עם הפורום הישן. בנתיים רצ"ב העלאה ידנית של שלוש הודעות רלוונטיות:
הטיפ היומי – קוד המקור והסברים על ארבעת השורדים, Eat@Bit.not.Meat,2/5/2005 5:26:34 AM,בימים הבאים נציג כאן טיפים שימושיים, רעיונות, שורדי דוגמה נוספים וחזקים יותר ועוד. אתם מוזמנים להוסיף טיפים משלכם.
אם קודי המקור נראים משובשים, העתיקו אותם לעורך טקסט (למשל notepad) ושם הציגו את הקוד כשהוא מוצמד לשמאל.
BOMBER
קוד המקור מצורף למנוע. כותב CC בית אחד בכל מחזור בן 3 פקודות, החל מכתובת 0 ומתקדם באופן רציף לאורך הזכרון. יכול לדרוס גם את עצמו.
CANNON
קוד המקור מצורף למנוע. כותב CC בית אחד בכל מחזור בן 3 פקודות. מתחיל לאחר הקוד של עצמו ומתקדם בקפיצות של 8 לאורך הזכרון. מכיוון שגודל הקפיצות (
הוא מחלק של גודל הזכרון (64K) הכתיבות יחזרו על עצמן לאותן כתובות לאחר ביצוע סיבוב שלם לאורך הזכרון (64K/8 כתיבות). מכיוון שהקוד עצמו קטן מ 8 בתים, הכתיבות ידלגו על הקוד
עצמו ולכן הוא לא יכול לדרוס את עצמו.
SHOOTER
קוד המקור:
MOV DI,AX # Initialize DI to our code start address
MOV AX,0CCCCh # Load 0xCCCCh to Ax, this will be written to the memory
@loop:
STOSW # Write Ax (0xCCCCh) to memory address (DI) and increment DI by 2
ADD DI,9 # Add 9 to DI
JMP @loop # Repeat last two commands forever (hopefully)
שורד זה דומה לCANNON, אבל כותב בכל פעם 2 בתים, בפעולה של WORD, פעם במחזור של 3 פקודות. מתקדם בכל פעם 11 בתים. מתחיל לכתוב לכתובת של תחילת הקוד,
אבל מכיוון שהפקודות הראשונות הן פקודות אתחול המורצות פעם אחת, לפני הכתיבה הראשונה, אין בעיה לכתוב עליהן. מכיוון שהקפיצות (11) הן ללא מכנה משותף עם גודל הזכרון
(64K), סיבובים חוזרים כותבים לכתובות שונות בזכרון, כך שלכאורה במהלך 11 סיבובים על הזכרון יש כיסוי של כל הזכרון. הבעיה היא שבדרך הקוד דורס גם את עצמו, בתחילת
הסיבוב השלישי על הזכרון ולכן אם המשחק לא הסתיים ופעולתו של השורד אינה מופרעת על ידי שורד אחר, הוא יעוף תמיד בסיבוב מספר 35753 של הרצת המנוע.
BIMP
קוד המקור:
XCHG DI,AX # Initialize DI to our code start address
ADD DI,10 # DI points to the start of loop
MOV SI,DI
ADD SI,10 # SI points to the start of loop
STD # Set direction flag, MOVSW will go backward
@loop:
DEC DI #
DEC DI # DI Points one word before start of loop
MOVSW # Copy the whole loop (12 bytes)
MOVSW # to the 12 bytes before its
MOVSW # current location
MOVSW # Copy the last 2 bytes first
MOVSW # DI and SI pointers decreased by 2
MOVSW # each time because DF=1
INC DI # Now DI points to the start of the
INC DI # new copy of the loop
JMP DI # Jump to the start of the new loop
שורד זה משכפל את עצמו, תוך כדי התקדמות אחורה בזכרון. בכל פעם הוא מעתיק את עצמו לפני תחילת העותק הנוכחי וקופץ לתחילת העותק החדש. השורד אינו מנסה לשתול קוד עוין,
אבל במהלך שכפולו העצמי הוא דורס שורדים אחרים שלרוב יפלו כשינסו להריץ את פקודת הקפיצה לכתובת ב DI. אם יש שם כתובת אקראית, סביר שזה יפיל את השורד האחר וכך גם אם
השורד האחר משתמש ב DI כמצביע לכתיבת קוד עוין (CC) לזכרון. שורד שישמור ב DI ערך טוב יכול לשרוד את מתקפת הבימפ, על ידי קפיצה לאיזור אחר בזכרון או על ידי הצטרפות
להרצה של קוד הבימפ.
================================
הטיפ היומי 2 – טקטיקות הגנה והתקפה + כמה שורדים פשוטים ולא כל כך רעים
שני פרמטרים פשוטים הם היוצרים את ההבדל העיקרי בין שורד לשורד. הפרמטר העיקרי המשפיע על יכולת ההגנה, השרידות, של שורד הוא פרופיל הפגיעות שלו – מספר הבתים בזכרון אשר שינוי שלהם יכול לפגוע בשורד. מספר זה יכול להשתנות במהלך הזמן ולכן נתחשב בממוצע. בפרט, בתחילת ההרצה, פרופיל זה גדול ומכסה בדרך כלל את כל הקוד, כולל האיתחול. ברוב השורדים קיים קטע של איתחול אשר מורץ פעם אחת בלבד ולאחר מכן כבר אינו פגיע ולכן הפרופיל יורד לאחר האיתחול. מכיוון שהאיתחול לוקח לרוב זמן קצר, נתעלם מקטעי איתחול ונתייחס למצב הקבוע.
הפרמטר השני הוא קצב ההתקפה, מספר הבתים הממוצע שנכתב במחזור אחד. ככל שמספר זה גבוה יותר, כך השורד תוקף מהר יותר את השורדים האחרים וגדל הסיכוי שלו להפיל אותם לפני שהם יפילו אותו. גם כאן נתעלם מפקודות איתחול ונתייחס למצב המתמיד.
ברוב המקרים, ניתן לקבל הערכה גסה של זמן ההישרדות הצפוי של שורד על ידי גודל הזכרון (65536) כפול סכום קצבי ההתקפה של יריביו, מחולק בפרופיל הפגיעות של השורד.
חשוב לציין שפרמטרים אלה זה לא הכל ויש גורמים נוספים העלולים להכריע, למשל האם ההתקפה נעשית ברצף או בתפזורת והאם השורד עלול לתקוף גם את עצמו. נדגים את הרעיון בעזרת שורדי הדוגמה.
BOMBER
הלולאה המרכזית כוללת 3 פקודות, כשבכל מחזור נכתב בית אחד. לכן קצב ההתקפה הוא 1/3.
לאחר האיתחול, רק פגיעה בלולאה המרכזית יכולה להזיק לשורד. הלולאה המרכזית כוללת 5 בתים (קל לראות זאת ע"י dis assembler, הפקודה u ב debugger של חלונות). לכן פרופיל הפגיעות הוא 5.
CANNON
גם כאן נכתב בית אחד כל 3 פקודות, כלומר קצב התקפה ממוצע של 1/3. כאן הלולאה המרכזית מונה 7 בתים ולכן פרופיל הפגיעות הוא 7. נתונים אלה מצביעים על שורד טוב פחות מהבומבר, אבל יש כאן 2 יתרונות שלא באים לידי ביטוי במספרים. בניגוד לבומבר, הקאנון לא תוקף את עצמו. הקאנון תוקף בתפזורת, בקפיצות של 8 ולכן הוא מנצל טוב יותר פגיעות גדולה של שורדים אחרים. זאת בניגוד לבומבר שתוקף ברצף ולכן לא מנצל למעשה פגיעות של שורדים אחרים ולכן יעילותו שקולה למצב של פגיעות 1 במתחרים.
SHOOTER
גם כאן הלולאה המרכזית מונה 3 פקודות, אבל השוטר כותב בכל מחזור 2 בתים ולכן קצב ההתקפה שלו הוא 2/3. פרופיל הפגיעות שלו הוא כגודל הלולאה המרכזית, 6 בתים.
BIMP
לולאה מרכזית בת 11 פקודות שכוללת כתיבה ל 6 מילים או 12 בתים, כלומר קצב התקפה של 12/11. גודל הלולאה הוא 12 בתים וזה פרופיל הפגיעות. כמו הבומבר, גם הבימפ תוקף ברצף ולכן אינו מנצל פרופיל פגיעות של היריב.
עכשיו ננסה ליישם את העקרונות ולבנות שורדים בעלי פרופיל הגנה נמוך ובעלי קצב תקיפה גבוה.
השורד הפשוט ביותר שניתן לבנות, הוא שורד ה LOOP:
LOOP
@loop:
jmp @loop
שורד זה אינו מבצע למעשה דבר, אבל יש לו פרופיל פגיעות נמוך ביותר, 2 בתים בלבד. לכן יש לו סיכוי גבוה להחזיק מעמד בזמן שהאחרים מחסלים זה את זה ולהגיע לקו הגמר, לבדו או לרוב בתיקו עם שורד נוסף. הרצות מול שורדי הדוגמה נותנות תוצאות מפתיעות ביחס לשורד כה פשוט.
טיפ: שורד זה שימושי מאד כדי לבדוק שורדים משלכם. לא ניתן להריץ שורד בודד לצורך בדיקה ולכן הוספה של שורד לופ מאפשרת בדיקה עצמאית של שורד שלכם ומעקב, האם הוא עף בעצמו (עקב באגים או התקפה עצמית) וצפיה נוחה בכתיבות בלי הפרעות מכתיבות של שורד נוסף. זה גם מאפשר לבדוק עצמאית טקטיקות התקפה של השורד שלכם, בלי שיהיה חשוף במקביל להתקפות מהיריבים.
כדי לבדוק את השורד שלכם מול יריב בעל פרופיל פגיעות גבוה יותר, ניתן להוסיף פקודות NOP בתוך הלולאה.
רמז: ניתן להגיע גם לשורדים בעלי פרופיל פגיעות נמוך יותר.
כעת ננסה ליצור שורד בעל קצב התקפה גבוה. המנוע תומך רק בפקודות על 8 או 16 ביטים ולכן פקודה בודדת מסוגלת לכתוב ל 2 בתים לכל היותר. שורד פשוט דורש בכל לולאה ביצוע של לפחות 3
פעולות:
1. כתיבה
2. עדכון כתובת לכתיבה הבאה
3. קפיצה לתחילת הלולאה
זו הסיבה שרוב שורדי הדוגמה כוללים לולאה בת 3 פקודות, אבל ניתן לשפר זאת. הפקודות STOSW, MOVSW כוללות עדכון של מצביעים וכתיבה בפקודה אחת, דבר שחוסך לנו פקודה ומאפשר לולאה של 2 פקודות בלבד:
ATTACK1
<איתחול>
@loop:
STOSW
jmp @loop
כאן יש כתיבה של 2 בתים כל 2 פקודות, כלומר קצב התקפה של 1. ניתן לשפר זאת, על ידי שכפול של פקודת STOSW, כמו שנעשה בבימפ:
ATTACK2
<איתחול>
@loop:
STOSW
STOSW
STOSW
STOSW
STOSW
jmp @loop
אם נשכפל את הפקודה N פעמים, נקבל כתיבה ל 2N בתים ב 2N+1 פקודות, כלומר קצב של 2N/2N+1. ככל שנעלה את N יעלה קצב ההתקפה, אבל במחיר של פרופיל פגיעות גבוה יותר.
במנוע החדש שתומך בפקודה REP, ניתן לשפר זאת:
REPEATER
<איתחול>
@loop:
MOV CX,0FFFFh
REP
STOSW
jmp @loop
כאן קצב ההתקפה הוא כמעט 2, לכאורה, פרופיל הפגיעות גבוה במעט מהלולאה המקורית. באופן מעשי, לולאת ה REP לעולם לא תסתיים (למה?) ולכן פרופיל הפגיעות כאן נמוך מאד (כמה?)
שורד פשוט זה הוא אחד הטובים שניתן לייצר. שורדים אחרים יותר לא יעלו עליו משמעותית,אבל ההבדלים הקטנים הם אלה שיכולים להכריע בסופו של דבר.
רמז: ניתן להגיע גם לקצב התקפה גבוה מ 2, זה לא מאד פשוט ודורש טריק מסויים.
Eat Bit not Meat
מוגש בחסות "אכלו ביטים ולא חיות"
אתר מומלץ יומי: <a href="http://www.animal.org.il" Target="_BLANK">http://www.animal.org.il</a>,0,0,0,http://www.animal.org.il,,
אור,החלטתי לא להשתתף בתחרות, אבל הינה הרעיונות שלי,tnidtnid@gmail.com,2/13/2005 11:17:09 AM,לאחר הרבה זמן שאני ניסיתי וניסיתי לחשוב על שורדים טובים הגעתי למסקנה שאין לי מספיק ידע באסמבלי בשביל התחרות.
בנוסף גם הקבוצה שניסיתי לארגן לא רצתה ללמוד או לא הבינה את שפת האסמבלי בשביל התחרות.
למרות שאני לא אלך לתחרות, היה לי ממש כיך ללמוד כך אסמבלי, ואולי שנה הבאה אם מספיק ידע ואולי עם קבוצה באותה רמה אני אנסה שוב.
בכל אופן היו לי כל מני רעיונות שאולי יעזרו(גם אם הם כרגע לא ממש טובים) לאחרים למרות שכבר מאוחר מדי לתקן שורדים אבל אולי זה יעזור כהכנה לתחרות.
–רעיון נחמד שחשבתי עליו למרות שאין בו הרבה תועלת הוא להשתמש במיקום של השורד על ההלוח כדרך להגרלת מספר ראנדומלי, וכך ניתן קצת להכניס מזל לתחרות.
אם למשל בשורדים פשוטים שמפציצים את הלוח כל פעם תוסיפו את ax אז כל משחק חדש המרווח של הקפיצות ישתנה בהתאם למיקום.
–רעיון נוסף הוא שבמקום לכתוב רק לכיוון אחד של השורד, אפשר לכתוב לשתי הכיוונים (אחורה וקדימה).
דוגמא:
@loop:
mov w[bx],0cdcdh
mov w[si],0cdcdh
sub bx,9
add si,9
jmp @loop
–רעיון נוסף הוא שעדיף לכתוב פקודה לא חוקית ששונה מהפקודה שנמצאת על רוב הלוח int 3 ….
כך אם יש שורד מסוג שורד הוא ינסה לפגוע במקומות ריקים.
–רעיון קטן שיכול להיות שימושי תחת מצבים מסויימים הוא לאכסן חלק מקוד התוכנית באוגרים.
דוגמא פשוטה היא להשתמש בפקודה STOSB במקום ב כדי MOVSB כדי לצור שורד שמשכפל את עצמו:
mov di,ax
add di,@end-@start
mov ax,0aah
stosb
@end:
–שורד שסורק אחר שורדים אחרים ואז מפציץ במרוכז:
@init:
mov bx,ax
add bx,1075
@core:
@scan:
add bx,11
cmp b[bx],0cch
je @scan
@check:
and bx,65535
cmp bx,ax
jb @kill
add ax,60
cmp bx,ax
sub ax,60
jbe @core
<FONT
הפתרון שלך לא מדויק. התשובה שלי יכולה לשמש כרמז או הבהרה לאחרים.
ההנחה היא שהמערך מכיל משהו. מדובר בקטע קוד. קטע אחר מאתחל אותו.
השאלה היא מה מחשב הקטע, ז"א מה משמעות הערכים של המשתנים לאחר הריצה.
כל התרגילים נפתרו בהצלחה (כל הכבוד).
רצ"ב הבהרה בקשר לשאלת המספרים:
נתון מספר שבע ספרתי (נניח של מכונית שנוסעת ברחוב). לצורך הדוגמא
1267825
המטרה ליצור תרגיל שתוצאתו מאה תוך שימוש בשבע הספרות על פי סדרן המקורי וארבעת פעולות חשבון (וסוגריים).
למשל, אפשר להגיע למאה מהמספר לעיל על ידי החישוב
(1*2*(-6+7)+
*2*5השאלה, כאמור, היא איזה חלק מהמספרים אפשר לפתור.
פתרון יפה.
יש עוד כמה דומים (אל תפרסמו פתרונות, השאירו לקוראים לנסות את כוחם לבד):
א. 1,5,6,7 להגיע ל-21;
ב. 2,4,6,8 להגיע ל-25;
ג. 2,3,4,5 להגיע ל-26 בלי להשתמש באותה פעולה פעמיים.
אבל נשאיר חידה שמתאימה יותר לפורום (תכנות): עבור איזה חלק של המספרים השבע ספרתיים ניתן להגיע ל-100 בעזרת 4 פעולות חשבון?
CodeGuru
נכון.
למתעניינים, הנושא פורסם במספר מקומות בעולם מאז חוברה החידה, למשל באוניברסיטת ברקלי
תודה על הצעת התיקון. רצ"ב הגרסא המעודכנת
add al,ah
mov di,ax
mov ax,0cccc
l:
add di,17
dec cx
repne
scasw
mov [di-2],bx
inc bx
jne l…
לבקשת הקהל, רצ"ב הזומבי במילים:
add al,ah
mov si,ax
l:
add si,17
lodsw
cmp ax,0cccc
jne l
mov [si-2],bx
inc bx
jne l..איך נמשיך מכאן?..
מטרת התוכנית איננה להלחם (אם תריצו אותו תראו שהוא מנסה די בהצלחה לא לגעת באחרים). התוכנה הזו נועדה לתת לאחרים הזדמנות להרוויח ממשהו חכם יותר מאשר הפצצה לכל עבר. יחד עם ארבעת המתחרים, נזרוק לזירה עוד (עשרה?) זומבים כאלה. כל מי שימצא את אחד הזומבים (איך?) יוכל לחטוף אותו ולקבל עוד זמן ריצה עבורו.
כותרת: MasterMind
שלום,
השם המקובל למשחק הוא MASTERMIND. הוא הומצא בידי ישראלי לפני כ-35 שנה, ובשנת 1976 D.E.Knuth (כן, מי שכתב את Art of Computer Programming) פרסם מאמר על איך לפתור את המשחק.
תוכל למצוא מידע עליו, למשל, באתרים:
http://www.unc.edu/~radu/mm/MMS.html
http://www.geocities.com/rmackwani/
http://delphiforfun.com/Programs/MasterMind.htmכותרת: הערות לשינויים
* בקשר למגבלות כתיבה – רעיון נחמד. צריך לאפשר לכתוב במרחק מסוים (ולא רק בתא סמוך), אחרת התוכנית האפשרית היחידה תהיה IMP (או משהו שמזגזג קדימה ואחורה באופן דומה). מרגע שיש מגבלת כתיבה מרוחקת, אפשר באמת גם לשים את השחקנים במקומות ידועים ולהפוך את המשחק לפחות תלוי במזל.
* במה יעזור לאתחול את הלוח אקראית?
* כבר עכשיו (בחוקים הנוכחים) ניתן "לכבוש" שחקני יריב. אם במקום לתת לו לבצע פקודה בלתי חוקית, תשלח את השורד היריב לקפוץ אל תוך קטע קוד שלך, בעצם השתלטת עליו, ויש לך שני שחקנים בכל מהלך.
* אפשר להכליל את שחקני בית הידועים לא רק לתקיפה, אלא גם לחיפוש. למשל – צריך לאתר כלבלב שהקוד שלו ידוע מראש.
** ודיברנו גם על שיתופי פעולה בין שחקנים שונים; על מגבלת כתיבה ב10,000 הצעדים הראשונים; על אפשרות לתת לתוכנה קלט אנושי מדי פעם; על גרפיקה מעניינת; ועוד ועוד.
