بازی زندگی Conway

بازی زندگی Conway ، همچنین به عنوان Game of Life یا Simply Life شناخته می شود ، یک اتومبیل سلولی است که توسط ریاضیدان بریتانیایی جان هورتون کانوی در سال 1970 ابداع شده است.

"بازی" در واقع یک بازی صفر است ، به این معنی که تکامل آن با وضعیت اولیه آن تعیین می شود و نیازی به ورودی بازیکنان انسانی ندارد. یکی با ایجاد یک پیکربندی اولیه و مشاهده نحوه تکامل آن با بازی زندگی در تعامل است.

GOL و CGOL معمولاً مخفف استفاده می شوند.

فهرست

قاعده

جهان بازی زندگی یک شبکه متعامد دو بعدی نامتناهی سلولهای مربع است که هر یک از آنها (در هر زمان معین) در یکی از دو حالت ممکن است ، "زنده" (جایگزین ") یا" مرده "("از طرف دیگر "خاموش").[1] هر سلول با هشت همسایه خود ، که سلول هایی هستند که به طور مستقیم به صورت افقی ، عمودی یا مورب مجاور هستند ، تعامل دارد. در هر مرحله از زمان ، انتقال زیر رخ می دهد:

1. هر سلول زنده با کمتر از دو همسایه زنده می میرد (به عنوان زیر جمعیت یا قرار گرفتن در معرض [2]).
2. هر سلول زنده با بیش از سه همسایه زنده در حال مرگ است (که به آن به عنوان جمعیت بیش از حد یا ازدحام بیش از حد گفته می شود).
3. هر سلول زنده با دو یا سه همسایه زنده ، بدون تغییر ، به نسل بعدی زندگی می کند.
4. هر سلول مرده با دقیقاً سه همسایه زنده زنده خواهد شد.

الگوی اولیه "بذر" سیستم را تشکیل می دهد. نسل اول با استفاده از قوانین فوق به طور همزمان در هر سلول موجود در دانه ایجاد می شود - تولد و مرگ و میر به طور همزمان اتفاق می افتد ، و لحظه گسسته ای که در آن اتفاق می افتد گاهی اوقات کنه نامیده می شود.(به عبارت دیگر ، هر نسل یک تابع خالص از قبل است.) این قوانین به طور مکرر اعمال می شود تا نسل های دیگری ایجاد شود.

ریشه

Conway به مشکلی که در دهه 1940 توسط ریاضیدان مشهور جان فون نویمان ارائه شد ، علاقه مند بود ، که سعی در یافتن یک ماشین فرضی داشت که بتواند نسخه هایی از خودش را بسازد و هنگامی که او یک مدل ریاضی برای چنین دستگاهی با قوانین بسیار پیچیده در شبکه مستطیل پیدا کرد ، موفق شدوادبازی زندگی به عنوان تلاش موفقیت آمیز Conway برای ساده سازی ایده های فون نویمان ظاهر شد.

این بازی اولین حضور عمومی خود را در شماره اکتبر 1970 از علمی آمریکایی ، در ستون "بازی های ریاضی" مارتین گاردنر ، تحت عنوان ترکیب های خارق العاده بازی جدید Solitaire John Conway "زندگی" انجام داد. از دیدگاه نظری ، جالب است زیرا قدرت یک دستگاه تورینگ جهانی را دارد: یعنی هر چیزی که می تواند به صورت الگوریتمی محاسبه شود ، می تواند در بازی زندگی Conway محاسبه شود. گاردنر نوشت:

این بازی Conway را فوراً مشهور کرد ، اما همچنین یک زمینه کاملاً جدید از تحقیقات ریاضی ، زمینه اتوماتیک سلولی را باز کرد. به دلیل قیاس های زندگی با ظهور ، سقوط و تغییر جامعه موجودات زنده ، متعلق به یک طبقه در حال رشد از آنچه "بازی های شبیه سازی" نامیده می شود (بازی هایی که شبیه فرآیندهای زندگی واقعی هستند)

از زمان انتشار آن ، بازی زندگی Conway به دلیل راههای شگفت آور که الگوهای می توانند تکامل پیدا کنند ، مورد توجه بسیاری قرار گرفته است. زندگی نمونه ای از ظهور و خود سازماندهی است. برای فیزیکدانان ، زیست شناسان ، اقتصاددانان ، ریاضیدانان ، فیلسوفان ، دانشمندان مولد و دیگران جالب است تا نحوه ظهور الگوهای پیچیده از اجرای قوانین بسیار ساده را مشاهده کنند. این بازی همچنین می تواند به عنوان یک قیاس آموزشی باشد ، که برای انتقال این مفهوم تا حدودی ضد انعطاف پذیر استفاده می شود که "طراحی" و "سازمان" می توانند در غیاب یک طراح به طور خودجوش ظهور کنند. به عنوان مثال ، دانیل سی دنت ، فیلسوف و دانشمند شناختی ، از آنالوگ زندگی "جهان" به طور گسترده ای استفاده کرده است تا تکامل احتمالی سازه های پیچیده فلسفی ، مانند آگاهی و اراده آزاد را نشان دهد ، از مجموعه نسبتاً ساده ای از قوانین بدنی تعیین کننده ماجهان خود[3] [4] [5]

محبوبیت زندگی Conway با ورود به آن به موقع برای نسل جدیدی از مینی رایانه های ارزان قیمت که در بازار آزاد می شدند ، کمک کرد ، به این معنی که این بازی می تواند ساعت ها روی این دستگاه ها اجرا شود که در غیر این صورت در شب مورد استفاده قرار نمی گرفتند. از این نظر ، محبوبیت بعدی فراکتال های تولید شده توسط رایانه را پیش بینی کرد. برای بسیاری ، زندگی صرفاً یک چالش برنامه نویسی بود. یک روش جالب برای هدر رفتن چرخه های CPU. با این حال ، برای برخی ، زندگی دارای مفاهیم فلسفی بیشتری بود. این فرقه را در دهه 1970 و بعد از آن توسعه داد. تحولات فعلی تا آنجا پیش رفته است که باعث ایجاد تقلید نظری سیستم های رایانه ای در محدوده یک هیئت زندگی می شود.

Conway قوانین خود را با دقت انتخاب کرد ، پس از آزمایش قابل توجه ، سه معیار را رعایت کرد:

1. نباید الگوی اولیه وجود داشته باشد که اثبات ساده ای وجود داشته باشد که جمعیت بدون محدودیت می تواند رشد کند.
2. باید الگوهای اولیه وجود داشته باشد که ظاهراً بدون محدودیت رشد می کنند.
3. باید الگوهای اولیه ساده ای وجود داشته باشد که برای مدت زمان قابل توجهی قبل از رسیدن به روشهای زیر رشد می کنند و تغییر می کنند:
   • محو شدن کاملاً (از ازدحام بیش از حد یا از بیش از حد پراکنده). یا
   • در یک پیکربندی پایدار که پس از آن بدون تغییر باقی می ماند ، یا وارد یک مرحله نوسان کننده می شود که در آن آنها یک چرخه بی پایان دو یا چند دوره را تکرار می کنند.

الگوهای

انواع مختلفی از الگوهای مختلف در بازی زندگی رخ می دهد ، از جمله الگوهای استاتیک ("هنوز هم زندگی") ، الگوهای تکرار ("نوسان ساز" - یک سوپراست از زندگی هنوز هم) ، و الگویی که خود را در سراسر صفحه ترجمه می کنند ("سفینه فضایی"). نمونه های متداول این سه کلاس در زیر نشان داده شده است که سلولهای زنده به رنگ سیاه و سلولهای مرده نشان داده شده به رنگ سفید نشان داده شده است.

Conway در ابتدا حدس می زد که هیچ الگویی نمی تواند به طور نامحدود رشد کند - به عنوان مثال ، که برای هر پیکربندی اولیه با تعداد محدود سلول های زنده ، جمعیت نمی توانند فراتر از حد متوسط محدود رشد کنند. در ظاهر اصلی بازی در "بازی های ریاضی" ، Conway جایزه 50 دلاری را به اولین شخصی که می تواند حدس را اثبات کند یا از آن رد کند قبل از پایان سال 1970 ارائه داد.: "اسلحه" ، که می تواند پیکربندی باشد که بارها و بارها اشیاء در حال حرکت مانند "گلایدر" یا "قطار پف" را شلیک می کند ، که پیکربندی است که حرکت می کند اما دنباله ای از "دود" مداوم را پشت سر می گذارد.

این جایزه در نوامبر همان سال توسط تیمی از انستیتوی فناوری ماساچوست به رهبری بیل گوسپر به دست آمد."اسلحه Gosper Glider" که به سمت راست نشان داده شده است ، اولین گلایدر خود را در نسل پانزدهم تولید می کند ، و یک گلایدر دیگر هر نسل 30 از آن به بعد. این اسلحه اول گلایدر هنوز یک جعبه محدودیت کوچکتر از هر اسلحه شناخته شده دیگر دارد و در بین اسلحه های تک بشکه ای رکورد کمترین جمعیت را با اسلحه Simkin Glider به اشتراک می گذارد.

اکتشافات بعدی شامل سایر اسلحه ها ، پف ها و "Rakes" بود که سفینه فضایی را حرکت و منتشر می کردند. Gosper همچنین اولین الگوی را با سرعت رشد درجه دوم بدون علامت به نام "پرورش دهنده" یا "خرچنگ" ساخت که با پشت سر گذاشتن یک دنباله اسلحه کار می کرد.

تکرار

از یک الگوی اولیه تصادفی سلولهای زنده در شبکه ، ناظران می یابند که جمعیت به طور مداوم در حال تغییر هستند زیرا نسل ها با هم تیک می زنند. الگوهای ناشی از قوانین ساده ممکن است نوعی زیبایی در نظر گرفته شود. زیرمجموعه های جدا شده کوچک و بدون تقارن اولیه تمایل به متقارن شدن دارند. هنگامی که این اتفاق بیفتد ، تقارن ممکن است در غنای افزایش یابد ، اما نمی توان آن را از دست داد ، مگر اینکه یک زیرزمین در این نزدیکی به اندازه کافی نزدیک شود که آن را مختل کند. در موارد بسیار اندک ، جامعه سرانجام از بین می رود و تمام سلولهای زنده از بین می روند ، اگرچه این ممکن است برای نسل های زیادی اتفاق نیفتد. بیشتر الگوهای اولیه در نهایت "سوزانده می شوند" ، یا چهره ها یا الگوهای پایدار تولید می کنند که برای همیشه بین دو یا چند حالت (معروف به خاکستر شناخته می شوند). بسیاری نیز یک یا چند گلایدر یا سفینه فضایی تولید می کنند که به طور نامحدود به دور از مکان اولیه حرکت می کنند.

الگوریتم

اولین نتیجه در بازی زندگی بدون استفاده از رایانه بدست آمد. ساده ترین زندگی و نوسان ساز هنگام ردیابی سرنوشت تنظیمات مختلف شروع کوچک با استفاده از کاغذ گراف ، تخته های سیاه ، تابلوهای بازی فیزیکی (مانند GO) و موارد مشابه کشف شد. در طی این تحقیقات اولیه ، کانوی کشف کرد که R-pentomino در تعداد کمی از نسل ها نتوانسته است تثبیت شود.

این اکتشافات الهام بخش برنامه نویسان رایانه ای در سراسر جهان برای نوشتن برنامه هایی برای ردیابی تکامل الگوهای زندگی است. بیشتر الگوریتم های اولیه مشابه بودند. آنها الگوهای زندگی را به عنوان آرایه های دو بعدی در حافظه رایانه نشان می دادند. به طور معمول از دو آرایه استفاده می شود ، یکی برای نگه داشتن نسل فعلی و دیگری که می تواند جانشین آن را محاسبه کند. اغلب 0 و 1 به ترتیب سلولهای مرده و زنده را نشان می دهند. یک حلقه دوتایی هر عنصر از آرایه فعلی را به نوبه خود در نظر می گیرد و همسایگان زنده هر سلول را به حساب می آورد تا تصمیم بگیرند که آیا عنصر مربوط به آرایه جانشین باید 0 یا 1 باشد. آرایه جانشین نمایش داده می شود. برای تکرار بعدی نقش های تعویض آرایه ها به طوری که آرایه جانشین در آخرین تکرار به آرایه فعلی در تکرار بعدی تبدیل می شود.

انواع پیشرفتهای جزئی در این طرح اساسی امکان پذیر است و روش های بسیاری برای صرفه جویی در محاسبات غیر ضروری وجود دارد. سلولی که در آخرین مرحله تغییر نکرده و هیچ یک از همسایگان آنها تغییر نکرده است ، تضمین می شود که در مرحله زمانی فعلی نیز تغییر نکنند ، بنابراین برنامه ای که پیگیری می کند که کدام مناطق فعال هستند می تواند با به روزرسانی در زمان صرفه جویی کند. مناطق غیرفعال

در اصل، فیلد Life بی نهایت است، اما رایانه ها حافظه محدودی دارند و معمولاً اندازه آرایه ها باید از قبل اعلام شود. هنگامی که ناحیه فعال در مرز آرایه نفوذ می کند، این منجر به مشکلاتی می شود. برنامه نویسان از چندین استراتژی برای رفع این مشکلات استفاده کرده اند. ساده ترین استراتژی این است که فرض کنیم هر سلول خارج از آرایه مرده است. این برنامه ریزی آسان است، اما زمانی که ناحیه فعال از مرز عبور می کند به نتایج نادرستی منجر می شود. یک ترفند پیچیده تر این است که لبه های چپ و راست زمین را به هم بخیه بزنید و لبه های بالا و پایین را نیز در نظر بگیرید و یک آرایه حلقوی ایجاد کند. نتیجه این است که نواحی فعالی که در لبه میدان حرکت می کنند، دوباره در لبه مقابل ظاهر می شوند. اگر الگوی بیش از حد بزرگ شود، باز هم می تواند نادرستی ایجاد شود، اما حداقل هیچ اثر لبه آسیب شناسی وجود ندارد. تکنیک‌های تخصیص پویا ذخیره‌سازی نیز ممکن است مورد استفاده قرار گیرد و آرایه‌های بزرگ‌تری برای نگهداری الگوهای در حال رشد ایجاد کند.

متناوبا، برنامه نویس ممکن است مفهوم نمایش فیلد Life با یک آرایه دو بعدی را کنار بگذارد و از ساختار داده متفاوتی مانند بردار جفت مختصات که سلول های زنده را نشان می دهد استفاده کند. این رویکرد به الگو اجازه می دهد تا بدون مانع در میدان حرکت کند، تا زمانی که جمعیت از اندازه آرایه مختصات زنده تجاوز نکند. اشکال این است که شمارش همسایگان زنده به یک عملیات جستجو تبدیل می شود و سرعت شبیه سازی را کاهش می دهد. با ساختارهای داده پیچیده تر، این مشکل نیز تا حد زیادی قابل حل است.

برای کاوش الگوهای بزرگ در اعماق زمانی زیاد، الگوریتم‌های پیچیده‌ای مانند Hashlife ممکن است مفید باشند.

همچنین روشی برای اجرای Game of Life با استفاده از به‌روزرسانی‌های ناهمزمان دلخواه وجود دارد، اما همچنان رفتار بازی همزمان را شبیه‌سازی می‌کند، که برای سایر خودکارهای سلولی نیز قابل استفاده است.[6]

تغییرات در زندگی

از زمان شروع اصلی زندگی ، قوانین جدید بر اساس ایده های مشابه تدوین شده است. بازی استاندارد زندگی ، که در آن یک سلول "متولد" می شود اگر دقیقاً 3 همسایه داشته باشد ، اگر 2 یا 3 همسایه زنده داشته باشد زنده می ماند و در غیر این صورت می میرد ، به عنوان "B3/S23" نماد می شود. اولین مجموعه اعداد ، که توسط "B" برای تولد نشان داده شده است ، لیست تعداد همسایگان یک سلول مرده می تواند برای به دنیا آمدن در نسل بعدی داشته باشد. مجموعه دوم ، که توسط "S" برای بقا نشان داده شده است ، همان چیزی است که برای ادامه یک سلول زنده مورد نیاز است. از این رو "B6/S16" به معنای "یک سلول در صورت وجود 6 همسایه است و در صورت وجود 1 یا 6 همسایه زندگی می کند". Highlife B36/S23 است ، زیرا داشتن 6 همسایه ، علاوه بر قانون B3/S23 بازی اصلی ، باعث تولد می شود. Highlife بیشتر به خاطر تکرار کننده ها شناخته شده است.

این امر می تواند بیشتر به قوانین غیر توتالیستی تعمیم یابد ، که موقعیت سلولهای زنده را در محله یک سلول معین در نظر می گیرد و نه صرفاً تعداد آنها هنگام تعیین تولد و بقا. برخی از تغییرات غیر توتالیستی مشهور در زندگی ، زندگی و برف های برفی است که خود سابق انواع بسیاری از علاقه ها را دارد. تغییرات اضافی در زندگی وجود دارد ، اگرچه اکثریت قریب به اتفاق این جهان ها یا بسیار آشفته یا متروک برای تضمین اکتشافات گسترده هستند.

سایر انواع محبوب اتومات های سلولی شامل قوانین نسل هایی مانند مغز برایان است که در آن سلولها به مرور زمان به جای اینکه فوراً از بین بروند ، و بزرگتر از قوانین زندگی مانند اشکالات مربوط به محلات بزرگتر در نظر گرفته می شوند. برخی از تغییرات هندسه جهان و همچنین قانون را تغییر می دهد. در تغییرات فوق ، جهان دو بعدی است و در یک شبکه مربع قرار گرفته است. تغییرات سه بعدی و یک بعدی ایجاد شده است ، همانطور که تغییراتی در آن وجود دارد که شبکه به جای مربع شش ضلعی یا مثلثی است.

قوانین Conway همچنین ممکن است به گونه ای تعمیم یابد که به جای دو ایالت (زنده و مرده) سه یا بیشتر وجود داشته باشد. سپس انتقال دولت یا توسط یک سیستم وزنه برداری یا با یک جدول مشخص می شود که قوانین انتقال جداگانه را برای هر حالت مشخص می کند. به عنوان مثال ، "جدول قوانین" چند رنگ "Mirek's Cellebration" و خانواده های حاکم "Life Life" هر یک شامل قوانین نمونه ای معادل زندگی Conway هستند.

الگوهای مربوط به فراکتال ها و سیستم های فراکتال نیز ممکن است در تغییرات خاص مانند زندگی مشاهده شود. به عنوان مثال ، Automaton 12/1 چهار تقریب بسیار نزدیک به مثلث Sierpiński را هنگام استفاده از یک سلول زنده واحد ایجاد می کند.

مهاجرت نوعی تغییر است که همان بازی زندگی است، با این تفاوت که دو حالت روشن وجود دارد (اغلب به صورت دو رنگ متفاوت بیان می شود). هر زمان که یک سلول جدید متولد می شود، حالت ON را به خود می گیرد که اکثریت در سه سلولی است که آن را به دنیا آورده اند. از این ویژگی می توان برای بررسی تعاملات بین سفینه های فضایی و سایر اشیاء درون بازی استفاده کرد. یک تغییر مشابه دیگر به نام QuadLife شامل چهار حالت مختلف ON است. هنگامی که یک سلول جدید از سه همسایه مختلف ON متولد می شود، مقدار چهارم را می گیرد و در غیر این صورت مانند Immigration مقدار اکثریت را می گیرد. به جز تغییرات بین سلول‌های ON، هر دوی این تغییرات مشابه Life عمل می‌کنند.