مدل سازی یک بازی پیچیده

مدیران انجمن: parse, javad123javad

ارسال پست
math0098

عضویت : سه‌شنبه ۱۳۹۷/۱۰/۱۸ - ۱۳:۳۵


پست: 1

سپاس: 1

مدل سازی یک بازی پیچیده

پست توسط math0098 »

بنابه برآوردها همه بازیهای ممکن شطرنج حدود 120*10هست.پرسش یک میلیارد دلاری و البته قدیمی اینه:سرانجام کدامها میبرند سیاه یا سفید؟!هدف مدل سازی برای یک بازی در حد و اندازه شطرنج در حقیقت فروکاست یک بازی به یک پرسش ساده است.کدامها سرانجام میبرند؟!فرض کنیم دوتا از یک نوع ابزار تخیلی(ابرابرابر کامپیوتر!که منظور ماشینیست که همه بازی های ممکنه شطرنج را تحلیل کرده و همه شاخه ها را برسی کرده است!)در اختیار داشته باشیم و بخواهیم این دو باهم بازی بکنند.جالبه اگه بدونیم که در واقع این دو هیولا اصلا باهم بازی نمیکنند! نتیجه به این بستگی خواهد داشت که کدامها سیاه و کدامها مهره سفید را در اختیار خواهند داشت .بازی به یک شیر و خط تبدیل خواهد شد!آیا ماشینهای کوانتومی آینده خواهند توانست این چالش را برای همیشه حل کنند؟!امیدوارم!

نمایه کاربر
You-See

نام: U30

محل اقامت: تهران

عضویت : یک‌شنبه ۱۳۹۳/۵/۱۹ - ۱۹:۰۵


پست: 1280

سپاس: 787

جنسیت:

تماس:

Re: مدل سازی یک بازی پیچیده

پست توسط You-See »

در شطرنج سوپرکامپیوتر ها همیشه اونی می بره که سفیده، یا نهایتا بازی به تساوی کشیده می شه.
اون پرسش هم یک میلیارد دلاری نیست، فوقش استادبزرگ شطرنجه، که فکر نمی کنم به میلیون دلار هم برسه. نمی دونم میلیارد رو از کجا آوردید؟
اگر تطابق ها به سرعت پیدا بشن، شاخه های تکراری حدف بشن، فضای داده به شدت کم می شه.
سیستم های امروزی هم از هرس کردن مینی ماکس استفاده می کنن تا بدون این که کل درخت رو پیمایش کنن، بهترین حرکت در n سطح زیرین خودشون رو پیدا کنن.
دوستای گلم حمایت کنید : https://cafebazaar.ir/app/com.nikanmehr.marmarxword/

math0098

عضویت : سه‌شنبه ۱۳۹۷/۱۰/۱۸ - ۱۳:۳۵


پست: 1

سپاس: 1

Re: مدل سازی یک بازی پیچیده

پست توسط math0098 »

Stockfish و AlphaZero از قویترین سوپر موتورهای حال حاضر شطرنجند و اینکه شما خودتون میگید یا برد با سفیده یا نهایتا مساویست.خب ولی پرسش من کلا یه چیز دیگه بود!اگه یک موتور تخیلی داشتیم که همه بازیهای ممکنه تو حافظش بود و دوتا از این نوع باهم اگر بازی میکردند نتیجه چی میشد؟!
بعدش شما درمورد دلار گفتین.منظور از چنین عبارتهایی چالش بودنشونه و نه نرخ دلار و یا یورو!
و کلا هدف از این پست گفتگو درباره مدلسازی ریاضیاتی چنین بازهاییست.

نمایه کاربر
You-See

نام: U30

محل اقامت: تهران

عضویت : یک‌شنبه ۱۳۹۳/۵/۱۹ - ۱۹:۰۵


پست: 1280

سپاس: 787

جنسیت:

تماس:

Re: مدل سازی یک بازی پیچیده

پست توسط You-See »

پاسختون داده شد.
در مورد دلار هم، بیان موضوعی تو تالار علمی بیان علمی هم می خواد، مظنه دلار و میلیارد و تریلیارد بیشتر به درد عامه می خوره.
اگر زدید، حتما دلیل محکمی براش دارید، پس بسم الله

همون طور که گفتم، چنانچه تمام حالات را بلد باشید، منطقی نیست که نفر اول همواره پیروز یا نهایتا نبازنده باشد؟
اصولا چه بازی ای را می شناسید که با دانستن تمام فضای نمونه، و انجام بازی پرفکت، شروع کننده بازنده شده باشد؟ برای نمونه شما رو ارجاع می دم به بازی تیک تاک تو
دوستای گلم حمایت کنید : https://cafebazaar.ir/app/com.nikanmehr.marmarxword/

Paradoxy

عضویت : دوشنبه ۱۳۹۳/۱۰/۲۲ - ۲۲:۱۷


پست: 2211

سپاس: 1012

Re: مدل سازی یک بازی پیچیده

پست توسط Paradoxy »

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

حالا بحث که اینجا هست اینه، شطرنجی که یک بازی دترمینیستیک هست پاسخش چیه؟ منظور از پاسخ اینه که صرف نظر از این که حریف شما در طول بازی چه حرکاتی رو بره، شما یه دیکشنری داشته باشی بغل دستت، و با استفاده از اون 100% مطمئن باشی برنده میشی. اولا این دیکشنری مال سیاهه یا سفید؟، در ثانی حتی اگه حریفت یک سوپر رایانه هم باشه عین خیالت نباشه و بتونی راحت ببریش با این دیکشنری. اینکه کامپیوتر های فعلی قادر به تولید این دیکشنری نیستند و مجبورن در هر حرکت با مینی ماکس چک کنن ببینن چه حرکتی میرن، به خاطر ضعف سرعتشونه. و پاسخیم که میدن جواب صد در صد بهینه نیست (در اون مقطع بهینه ترینه، در تمام طول بازی بهینه ترین نیست). بله سفید میبره چون یک حرکت جلوتره، اما ما دنبال یک پاسخ لوکال نیستیم که دو کامپیوتر با روش عددی دارن بهمون میدن، دنبال یک جواب دقیقیم، یک دیکشنری!
مسئله nqueen م دیده باشید همینه. ما یک سری جواب برای مقادیر مختلف n داریم، اما! معلوم نیست آیا جواب های دیگری هم هست؟ چند جواب داریم؟ هر ان چه جوابایی داره؟ ما این جوابا رو بدون brute force می خوایم، چون یهو به ازای یک n خیلی بزرگ اصلا نمیشه جوابی پیدا کرد. این هم جایزه چند میلیون دلاری داره و من به شخصه دیدم و لینکشم خواستید پیدا میکنم میفرستم. حالا این مسئله دوستمون رو نمیدونم جایزه داره یا نداره؟
البته بحث این خیلی مفصل تر بود من سعی کردم خلاصه کنم، مثلا یه چیز جالب دیگش اینه که ماکسیمم حرکت لازم برای پیروزی چندتاست؟ صرف نظر از حرکات حریف!

نمایه کاربر
You-See

نام: U30

محل اقامت: تهران

عضویت : یک‌شنبه ۱۳۹۳/۵/۱۹ - ۱۹:۰۵


پست: 1280

سپاس: 787

جنسیت:

تماس:

Re: مدل سازی یک بازی پیچیده

پست توسط You-See »

داوود جان حرف شما درست، ولی من هم گفتم اگر تمام فضا رو داشته باشیم مساله کاملا حل شده است.
و بله، منظور در اینجا بازیهای دترمینیستیک هست، نه مثل تخته نرد،
اون مساله NQueen هم مطمئنی؟ من تو دوره دانشجویی ترم 3 یا 4 تمام حالات رو درآورده بودما، یا شاید تشابه اسمی باشه.
در کل حرف من اینه که با داشتن اون دیکشنری که شما گفتی برای بازی های دترمین، همه چی اوکی هست. از قبیل شطرنج و تیک تاک تو.
شما اگر دیکشنری رو داشته باشی همیشه با سفید برنده، و یا غیر بازنده ای.
یادمه این رو یه جایی بصورت ریاضی هم اثبات کرده بودند، یا شاید من این طور خاطرم مونده باشه.
آره دیگه میلیون دلاری نه میلیارد دلاری و سیکستیلیون دلاری!
دوستای گلم حمایت کنید : https://cafebazaar.ir/app/com.nikanmehr.marmarxword/

Paradoxy

عضویت : دوشنبه ۱۳۹۳/۱۰/۲۲ - ۲۲:۱۷


پست: 2211

سپاس: 1012

Re: مدل سازی یک بازی پیچیده

پست توسط Paradoxy »

کل فضا مثلا حاوی ده به توان صد و بیستا حالته، شوخی که نیست. فعلا نمیتونیم بررسی کنیم.
بله مطمئنم، شخص خودمم دو حل تحلیلی به ازای ان های زوج و فرد گیر آوردم و با brute force جوابای دیگری رو هم گیر آوردم، منتهی به ازای یک ان بزرگ ممکنه میلیارد ها پاسخ وجود داشته باشه که بدیهیه بروت فورس قادر به حلش نیست، یک دونه جوابم نمیتونه گیر بیاره تازه، ما هم یه چهار تا حل تحلیلی (منظور همون جوابای بدیهیه، که مثلاً اولین وزیر رو میزاری خونه اول بعدی رو مبزاری ردیف بعد دو تا جلوتر، این ساده ها) بیشتر نداریم. جوابای دیگه چی؟ به ازای هر ان، ام تا جواب هست، ما همرو میخوایم.
http://www.claymath.org/events/news/8-queens-puzzle

این ادعا رو از کجا میگی که سفید برندس؟ مگه دیکشنری ش هست؟ ده به توان صد و اندی حالت رو ذخیره و بررسی کردن؟ یه روشی هست به اسم conjunction یا همچین چیزی، اثبات عددیه، یعنی خب مثلا وقتی ابر رایانه به فلان نتیجه میرسه بنا و بر این میزاریم که واقعا اینطوره، اما اثبات تحلیلی که در نظر گفتن همه حالات باشه نیست. یه قاعده طلایی یه بابایی گفته بود معروفم هست اسمش نمیاد تو ذهنم، حدس گلدباخ یا همچین چیزی، اینم با کامپیوتر میشه نشون داد که تا یه عدد خیلی بزرگ برقراره و با همین روش میشه اثبات کرد که مثلا حدسش درسته، منتهی ما دنبال این نیستیم، ما میخوایم مطمئن باشیم کل فضای نمونه همین جواب رو میده، شطرنجم همینه دیگه، حالا ابر رایانه با روش مینی ماکس خودش نشون داده که سفید برندست، اما تضمینی نیست که واقعا سفید برنده باشه یا دستکم من ندیدم تحلیلی کسی اثبات کرده باشه. بحث اینه که درخت حرکات شطرنج انقدر بزرگه انقدر بزرگه که نمیشه توش یک winning strategy پیدا کرد.

اینم ببینید باحاله:
https://youtu.be/PN-I6u-AxMg

اینا که باز خوبه، این NP hard problem ها واقعا پوست میکنه، امیدوارم مجبور نشید حلشونو پیدا کنید، چون حتی حل عددیشم سخته.

نمایه کاربر
You-See

نام: U30

محل اقامت: تهران

عضویت : یک‌شنبه ۱۳۹۳/۵/۱۹ - ۱۹:۰۵


پست: 1280

سپاس: 787

جنسیت:

تماس:

Re: مدل سازی یک بازی پیچیده

پست توسط You-See »

یه کتاب بود به نام P vs NP که حتی تو سریال سیمپسون ها هم ازش حرف زده شده بود.
فکر می کنم هر دو داریم یه چیز می گیم. درسته همه حالت ها رو بررسی نکردیم ولی جایی خونده بودم (فکر کنم) که در صورتی که در چنین بازیهایی همه حالتها رو داشته باشیم، شروع کننده بازنده نیست.
شاید هم اثبات نبود، باید بگردم دنبالش.
بحث خوبی شد، تجربیاتی اگه در زمینه تحلیل بازی داری بگو، من هم برم بگردم ببینم چی پیدا می کنم.
دوستای گلم حمایت کنید : https://cafebazaar.ir/app/com.nikanmehr.marmarxword/

Paradoxy

عضویت : دوشنبه ۱۳۹۳/۱۰/۲۲ - ۲۲:۱۷


پست: 2211

سپاس: 1012

Re: مدل سازی یک بازی پیچیده

پست توسط Paradoxy »

بازی که نمیشه گفت، اما یکی از NP Hard هایی که باهاش سر و کار داشتم مسئله جا کردن N توپ توی یک ظرف با شکل دلخواه، به شکلی که توپا overlap (نمیدونم ترجمش چی میشه، یعنی توپا نرن تو هم دیگه) نکنن و در عین حال بیشترین فضا رو اشغال کنند بودش. یعنی شما نه میدونی مرکز کره ها کجا باید باشه و نه میدونی شعاعشون چقدره، اما حجم ظرف رو میدونی، حالا باید بگی توپا رو با چه شعاعی کجا بزاریم بیشترین حجم رو بگیرن. انصافا مسئله دشواری بودش و یک هفته ای وقت گرفت ازم. جواب تحلیلی این مسئله برای وقتی که حجم ظرف بینهایته رو داریم، دو حالت چینش hexogonal و fcc بیشترین حجم رو میگیرن، اما وقتی حجم ظرف محدود میشه مسئله به شدت دشواری میشه، به خصوص که مجبور باشی با سیستم خونگی جواب بگیری. الگوریتم های زیادی هم براش هست، مثل بیلیارد یا کمپرسر و ... اما هیچ کدوم یک جواب درست حسابی نمیدن، همش در حالت های لوکال میمونن و سیستم باید خیلی قوی باشه تا بشه حلشون کرد. یا این که ایده بزنی کلا الگوریتم جدیدی بدی که شاید جواب بده، مثلا من این کارو کردم. گرچه مسئله خیلی ساده ایه! هرچند فکر میکنم توی بازی هم چنین چیزی کاربرد پیدا میکنه، یا ذخیره اطلاعات و .... باز مدل هایزنبرگ NP hard ه من مدل Isingش که صرفا NP complete هست رو حل کردم با چند روش ترکیبی، حالا دارم روی هایزنبرگ کار میکنم. اگه بتونی توی یکی ازینا یک روش به حد کافی سریع و دقیق پیدا کنی راحت نیچر رو شاخشه، نیچر نشد دیگه فیزیکال ریویو قطع یقین. اما خب خیلی سخته! مضحک سخته چون فضای نمونه رسما حاوی بینهایت حالته. میشه راجب این مسائل صحبت کنیم منم دوست دارم.

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

نمایه کاربر
You-See

نام: U30

محل اقامت: تهران

عضویت : یک‌شنبه ۱۳۹۳/۵/۱۹ - ۱۹:۰۵


پست: 1280

سپاس: 787

جنسیت:

تماس:

Re: مدل سازی یک بازی پیچیده

پست توسط You-See »

یه روش حل مساله دیده بودم جالب بود، مثلا برای حل مساله فروشنده دوره گرد اومده بود با استفاده از پروتئین اون رو حل کرده بود.
همون طور که می دونی حل این مساله بصورت غیر لوکال زمان وحشتناکی می بره و اوردر اون فکر می کنم n^2 یا یه همچین چیزیه.
حالا طرف اومده بوده هر نود رو یک پروتئین گرفته بود، بعد از هر پروتئین مثلا 1 گرم ریخته بود تو ظرف، هم زده بود و با استفاده از محلولی که زنجیره های بلند رو حل می کرد همه رو شسته بود به جز زنجیره های کوتاه، همین طور رفته بود با چند بار شستن تا فقط یک زنجیره مونده بود !!!
بعد هم دی کد و جواب !!!
خیلی خیلی راه باحالی بود.
من برای حل یک مساله که اونم تعداد جواب هاش خیلی خیلی زیاد بود، و من فقط یکی از جواب های ممکن رو می خواستم، چندین بار روش بازگشتی رفتم، ولی هم رمم پر شد هم سی پی یو فول شد هم بعد از دو ساعت هنوز جوابی نگرفته بودم، اون هم روی نمونه های نه چندان سختش، مجبور شدم مدل سازیش رو ببرم بدم اس کیو ال برام انجام بده، با استفاده از جوین و این داستانا، بی شرف اس کیو ال خیلی خیلی تو این زمینه های پارالل قوی کار کرده.
البته اینا دو تا روش حل مساله بود که منطقا به درد همه کیس ها نمی خوره. ولی فکر کردم جالب باشه بدونی.
از تجربه هات بگو برام جالبه
دوستای گلم حمایت کنید : https://cafebazaar.ir/app/com.nikanmehr.marmarxword/

Paradoxy

عضویت : دوشنبه ۱۳۹۳/۱۰/۲۲ - ۲۲:۱۷


پست: 2211

سپاس: 1012

Re: مدل سازی یک بازی پیچیده

پست توسط Paradoxy »

پروتوئین همون ژنتیکه؟ این مدلیش که خیلی جالب کار کرده. بدی ژنتیک فقط اینه که همه جا جواب خوبی نمیده، مثلا یک مسئله ای هست به نام Coloumb cluster، به این ترتیبه که ما n اتم با شکل دلخواه، مثلا کروی داریم می خوایم ببینیم این اتم ها اگر بهم بچسبند و تماس پیدا کنند، در چه حالتی هر اتم بیشترین تماس رو با اتمای اطراف خودش پیدا میکنه. به عبارتی یک کلاستر از اتم ها می سازیم. مثلا یک استاد دانشگاه که روی این مسئله کار کرده بود با همین ژنتیک حل کرده بود مسئله رو به این ترتیب که چند زنجیره از اتم ها رو به شکل تصادفی میساخت و بعد دوتا دوتا پیوند میزد تا این که بهترین جواب رو پیدا کنه. من برای همین کلومب کلاستر یه الگوریتم از خودم در آوردم حالا نمیدونم اسمی براش هست یا نه، اما روش کار به این ترتیبه که n تا اتم رو میریزیم در فضا، بعد همه رو به شکل تصادفی و همزمان به لرزه در میاریم، لرزش بسیار شدید. هر لرزشی که سبب افزایش انرژی پتانسیل سیستم یا نزدیک شدن اتم ها بشه رو می پذیریم و هر کدوم که انرژی رو به بره پایین قبول نمیکنیم، خب به تدریج اتم ها نزدیک میشن و شرط اینه که هیچ اتمی overlap نداشته باشه. برنامه میاد کند میکنه این لرزشو آروم آروم تا جایی که وقتی لرزش مثلا به حد یک میلیونیوم رسید برنامه متوقف میشه و جواب میگیریم. برای دو تا ده اتم با یک بار اجرا هم جواب های خوبی میگیریم (اگه عکساش رو هنوز داشته باشم میزارم اینجا) اما برای سیستم های پر اتمی باید مولتی استارت کرد و بهترین جواب رو پذیرفت. خیلیم سریع پنح دقیقه ای جواب میده تو سیستم خانگی!

اگه مشکل کمبود رم هست یا دیتابیسا کلان و سنگینن، پیشنهاد میکنم از tall array متلب استفاده کنی. هم پاراللش میشه کرد در سطح کلان یا خانگی، (خیلیم سادست، من توی یک روز دقیقا دستم اومد پارالل کردنش) هم به شدت سریعه و هم اینکه توابع از پیش تعریف شده زیادی برای محاسبات و پیدا کردن جوابای عددی هست که آدم رو از برنامه نویسی راحت میکنه. حتما حتما هم آخرین ورژنش 2018b رو بگیر، به شدت سریع تر از نسخه های قبلیش شده.

ارسال پست