الگوریتم موتور بازی شطرنج

[hamed jalili]

سلام دوستان

من یه برنامه شطرنج نوشتم ، شامل قسمت های زیره :
1- محیط گرافیکی
2- موتور بازی
3- پایگاه داده مربوط به Opening ها

در مورد محیط گرافیکی و پایگاه داده که بحث خاصی نیست .
مهمترین قسمت این برنامه ، موتور بازی ه


موتوری که من نوشتم این ویژگی ها رو داره :

1- نحوه بازی : آنالیز Position از طریق درخت Min-Max
2- بهینه سازی درخت آنالیز از طریق حرص Alpha - Beta
3- عمق پیمایش : 4
4- ارزیابی هر Position به وسیله شمارش تعداد مهره ها و جمع برداری ارزش مهره ها
5- بهینه سازی استفاده از حافظه ( در هر لحظه فقط مسیر جاری در حافظه است ، و در پایان کار ، تنها بهترین مسیر در حافظه است . )

ضعف های اصلی این موتور در عمق پیمایش و نحوه ارزیابی هر Position ه
حل مشکل عمق پیمایش ساده است ، ولی همون طور که می دونید افزایش عمق پیمایش از 4 به 5 معادل افزایش زمان محاسبات به صورت تصاعدیه ( تصاعد هندسی ) . پس عملا نمیشه به همین سادگی عمق پیمایش رو افزایش داد .
ولی در مورد تابع evaluate که وظیفه Analysis هر Position رو بر عهده داره ، میشه کاری کرد که با Analysis بهتر ، نتیجه محاسبات موتور رو بهتر کنه .

بهترین روشی که میشه به کار برد (از نظر من ) ، اینه که از یه الگوریتم پیشگو برای تابع Evaluate در نظر گرفت که با یه آنالیز پیشگو هم در عمق ( نه به صورت درختی ) پیش بره و هم ارزیابی منطقی از Position رو بده . :متفکر:


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







.

[star_n]

تابع evaluate دقیقا چه جوری محاسبه می کنه؟
منظورتون از تابع پیشگویی چیه؟

[Daleeeeer]

سلام دوست من. دو تا سوال؟
1- تابع evaluate شما چه جوری کار می کنه؟ نحوه آنالیز اون چه جوریه؟
2- منظورت از تابع پیشگو همون تابع هیورستیک هست؟ در ضمن الان داری از این تابع پیشگو استفاده می کنی؟ چه جوری؟

ممنون می شم اینها رو بگی. شاید یه کاری با هم کردیم. یا علی

[hamed jalili]

1- این تابع به هیچ عنوان کارا نیست . باید یه تابع جدید نوشته بشه .

2- نه ، فکر نمی کنم اسم این تابع رو تابع هیوریستیک بشه گذاشت ، و من از هیچ تابع پیشگویی استفاده نمی کنم .

تابع پیشگو باید این طور عمل کنه :
1- Attack - Defence ها رو بدون اینکه از درخت استفاده کنه ، محاسبه کنه
2- Mate Attack Position رو باید بتونه بدون درخت شناسایی کنه
3- Mate Defence Position رو باید بدون درخت آنالیز کنه
4- King Safty رو بتونه بدونه استفاده از درخت آنالیز کنه
5- Relative Agressive position رو باید بتونه شناسایی کنه .





.

[محمدامین شریفی]

منم دارم روی این بازی (http://www.codeproject.com/KB/game/reversi.aspx)کار میکنم.اسمش هست reversi و بازی خیلی جالبی هست.تمام مطالب شما درباره بازی شطرنج در این بازی هم صدق می کند.شما در چه مرحله ای هستید؟
اینجا (http://www.barnamenevis.org/forum/showthread.php?p=728503) را هم ببینید.

[hamed jalili]

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




.

[محمدامین شریفی]

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

[hamed jalili]

راستش این یه برنامه خیلی پیچیده هست که هم توضیحش از حد وقت و حوصله من خارجه و هم خوندن توضیحات من از وقت و حوصله شما خارجه .

یه مثال خیلی کوچک رو از این موتور به صورت خیلی مختصر براتون توضیح میدم :

تابع تشخیص Mate Position
این تابع وقتی صدا زده میشه که موتور اعلان کیش رو دریافت میکنه ، این اعلان به ناظر اطلاع داده میشه ( ناظر یه تابع ه که روند بازی رو کنترل می کنه تا تمام قوانین شطرنج پیاده به درستی اجرا بشن ) ناظر Position و تعدادی اطلاعات کلیدی رو به تابع تشخیص مات ارجاع میده که این تابع به این صورت فرمان دریافتی رو برسی می کنه :

1- کیش توسط چه مهره ای انجام شده است ؟
2- کیش از چه نوعی است ؟ ( یک طرفه یا دو طرفه )

اگر کیش یک طرفه است :
بررسی راه های ممکنه برای فرار شاه ، دفاع شاه و حذف مهره کیش کننده

اگر کیش دو طرفه است :
بررسی راه های ممکنه برای فرار شاه

و در نهایت اعلام می کنه که این Position مات هست یا خیر ؟!


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

این موتور برای جستجو از روش تجزیه درختی استفاده می کنه و برای بهینه سازی از روش حرص Alpha - Beta استفاده میکنه . عمق پیمایش 5 ه و متوسط Node های ساخته شده بدون حرص برای Position های نیمه پیچیده وسط بازی حدود 40^40^40^40^40 ه . حداکثر زمان پاسخ برای یک Position پیچیده وسط بازی با اعمال حرص ، حدود 5 ثانیه است . ( Processor: Core 2 Duo E4500 )





نه موتور و نه واسط اون تجاری ه؛ ولی چون فعلا به امنیت فایل های exe و dll در حفاظت از کد ها ایمان ندارم متاسفانه ...
اگه screenshot به دردتوم می خوره می تونم چند تا براتون upload کنم یا چند تا از بازی های موتور رو براتون بنویسم .


.

[محمدامین شریفی]

این موتور برای جستجو از روش تجزیه درختی استفاده می کنه و برای بهینه سازی از روش حرص Alpha - Beta استفاده میکنه . عمق پیمایش 5 ه و متوسط Node های ساخته شده .
کد پروژه reversi رو اینجا (http://www.4shared.com/file/110378937/44accf73/source_reversi.html) گذاشتم.توضیحات فارسیش هم بعدا گذاشته می شود.
پروژه اصلیش در اینجاست (http://www.codeproject.com/KB/game/reversi.aspx)،که در واقع 50 درصد کدهاش رو کم کردم،و یک کلاس هم بهش اضافه کردم.


تابع تشخیص Mate Position
این تابع وقتی صدا زده میشه که موتور اعلان کیش رو دریافت میکنه ، این اعلان به ناظر اطلاع داده میشه ( ناظر یه تابع ه که روند بازی رو کنترل می کنه تا تمام قوانین شطرنج پیاده به درستی اجرا بشن ) ناظر Position و تعدادی اطلاعات کلیدی رو به تابع تشخیص مات ارجاع میده که این تابع به این صورت فرمان دریافتی رو برسی می کنه :

1- کیش توسط چه مهره ای انجام شده است ؟
2- کیش از چه نوعی است ؟ ( یک طرفه یا دو طرفه )

اگر کیش یک طرفه است :
بررسی راه های ممکنه برای فرار شاه ، دفاع شاه و حذف مهره کیش کننده

اگر کیش دو طرفه است :
بررسی راه های ممکنه برای فرار شاه

و در نهایت اعلام می کنه که این Position مات هست یا خیر ؟!
.
هر وقت که از امنیت کدهایتان اطمینان حاصل کردید، خوشحال می شویم کد این تابع را ببینیم.

پیروز باشید.