پیاده سازی هوش مصنوعی شطرنج – قسمت صفر – تاریخچه

هیچ وقت به بازی‌های کامپیوتری علاقه‌ای نداشتم، اما در سال ۱۳۸۹ ورق برگشت! جناب مهندس کی‌نژاد مسابقه‌ای را طرحی کرده بودند که خیلی چیزها رو برای من تغییر داد. مسابقه که با همکاری سایت ECA اجرا شده بود. این مسابقه چالشی داشت که شاید یکی از خوشایندترین چالش‌هایی بوده که تا حالا باهاش دست و پنجه نرم کرده باشم. موضوع مسابقه به این بود که سخت افزار معینی، شامل یک میکروکنترلر atmgea32 و یک نمایشگر گرافیکی با رزولوشن ۱۲۸ در ۶۴ پیکسل کلید و … تعریف شده بود که می‌بایست بر روی آن یک بازی پیاده سازی می‌شد. آنچه برای من جذابیت داشت، اول محک زدن خودم بود و دوم این که کنجکاوی همیشگی‌ام در خصوص بازی‌های کامپیوتری. نه این که چطور بازی می‌شوند، بلکه چطور نوشته می‌شوند. حدود ۱۱ سال می‌گذرد و سؤالی داشتم که ذهنم را درگیر می‌کرد. اگر بازی به گونه‌ای باشد که در آن نیاز باشد با کامپیوتر بازی کنید، آنگاه چطور باید این کار را انجام داد؟ ماشین چطور فکر می‌کند؟ آیا هوش مصنوعی شطرنج را بازی می‌کند؟

همین سؤالات باعث شد که آن روزها من جزو آخرین نفراتی باشم که در این چالش شرکت می‌کنم و وقت زیادی برای پیاده سازی آنچه می‌خواستم انجام بدم نداشتم. هرچند، یک هفته به مدت مسابقه اضافه شد. اما فکر می‌کنم چیزی حدود ده روز یا پانزده روز درگیر طراحی بازی و پیاده سازی نرم افزاری آن بودم. ولی در این مسیر چالش‌هایی وجود داشت که هنوز از آن به نیکی یاد می‌کنم. جا داره همینجا از جناب مهندس کی‌نژاد برای تمام زحماتشان در خصوص جامعه الکترونیک تشکر کنم. برای آن مسابقه، اگر اشتباه نکنم ۳ بازی رو از صفر پیاده سازی کردم (فکر می‌کنم توی مجله نویز توضیحاتش موجود باشه). اما نکته‌ای که داشت این بود که شما با هوش مصنوعی بازی نمی‌کردید. بلکه معمایی که وجود داشت را حل می‌کردید. مثلاً بازی پازل یا بازی maze runer یا خانه سازی و.. هیچ کدام طرف مقابل شما برنامه‌ای کامپیوتری نیست، تنها روندی وجود دارد که باید آن را طی کنید تا برنده شوید.

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

چرا شطرنج

تقریباً همه چیز رو در مورد بازی‌های کامپیوتری فراموش کرده بودم تا فکر می‌کنم حدود سال ۲۰۱۶ بود که جناب آقای مبینی (EP3MIR) برنامه‌ای رو برام فرستاد! برنامه واقعاً عجیبی بود! همه چیز دوباره برام زنده شد. برنامه مربوط به مجله elektor بود که روی یک میکروکنترلر atmega88 پیاده سازی شده بود. برنامه شطرنج بازی می‌کرد! یه برنامه ۱۲۳۰ خطی، تازه آن هم روی یک میکروکنترلر ۸ بیتی، چطور میتونه شطرنج بازی کنه؟!

اولین چیزی که توی ذهنم شکل گرفت این بود که اصلاً چطور می‌فهمه حرکت کاربر درست است یا اشتباه! همین خودش به تنهایی کلی شرط و برنامه نویسی لازم داره! حالا این که بخواد حرکت متناسبی هم انجام بده که استراتژی داشته باشد و بازی رو به بره!‌

سعی کردم برنامه رو به خونم و ازش سر در به یارم. با این که به زبان سی هم نوشته شده بود، ولی این‌قدر بد نوشته شده بود که هیچی ازش نفهمیدم. البته این بد نوشتن برنامه دلیلش آینه که ظاهراً توی سال‌های دور، برنامه نویس اصلی این هوش مصنوعی سعی کرده برنامه رو توی ۲۰۴۸ کاراکتر خلاصه کنه برای همین به این روز افتاده. خلاصه که هیچی ازش متوجه نشدم ولی جرقه‌ای بود توی ذهنم که چطور این کار رو انجام داده!

تکه‌هایی از برنامه رو میذارم قضاوت با شما، آیا میشه چیزی ازش فهمید؟!

void D() /* iterative Negamax search */
{
D:if (--J<A) { /* stack pointer decrement and underrun check */
++J;DD=-l;goto R; /* simulated return */
}
q=Dq;l=Dl;e=De;E=DE;z=Dz;n=Dn; /* load arguments */
a=Da; /* load return address state*/

--q; /* adj. window: delay bonus */
k^=24; /* change sides */
d=X=Y=0; /* start iter. from scratch */
while(d++<n||d<3|| /* iterative deepening loop */
z&K==I&&(timer.w<0&d<98|| /* root: deepen upto time */
(K=X,L=Y&~M,d=3))) /* time's up: go do best */
{x=B=X; /* start scan at prev. best */
h=Y&S; /* request try noncastl. 1st*/
if(d<3)P=I;else
{*J=_;Dq=-l;Dl=1-l;De=-e;DE=S;Dz=0;Dn=d-3; /* save locals, arguments */
Da=0;goto D; /* Search null move */
R0:_=*J;P=DD; /* load locals, return value*/
}
m=-P<l|R>35?d>2?-I:e:-P; /* Prune or stand-pat */
#ifdef __unix__
++timer.w; /* node count (for timing) */
#endif // __unix__
do{u=b[x]; /* scan board looking for */
if(u&k) /* own piece (inefficient!)*/
{r=p=u&7; /* p = piece type (set r>0) */
j=o(p+16); /* first step vector f.piece*/
while(r=p>2&r<0?-r:-o(++j)) /* loop over directions o[] */
{A: /* resume normal after best */
y=x;F=G=S; /* (x,y)=move, (F,G)=castl.R*/
do{ /* y traverses ray, or: */
H=y=h?Y^h:y+r; /* sneak in prev. best move */
if(y&M)break; /* board edge hit */
m=E-S&b[E]&&y-E<2&E-y<2?I:m; /* bad castling */
if(p<3&y==E)H^=16; /* shift capt.sqr. H if e.p.*/
t=b[H];if(t&k|p<3&!(y-x&7)-!t)break; /* capt. own, bad pawn mode */
i=37*w(t&7)+(t&192); /* value of capt. piece t */
m=i<0?I:m; /* K capture */
if(m>=l&d>1)goto J; /* abort on fail high */

v=d-1?e:i-p; /* MVV/LVA scoring */
if(d-!t>1) /* remaining depth */
{v=p<6?b[x+8]-b[y+8]:0; /* center positional pts. */
b[G]=b[H]=b[x]=0;b[y]=u|32; /* do move, set non-virgin */
if(!(G&M))b[F]=k+6,v+=50; /* castling: put R & score */
v-=p-4|R>29?0:20; /* penalize mid-game K move */
if(p<3) /* pawns: */
{v-=9*((x-2&M||b[x-2]-u)+ /* structure, undefended */
(x+2&M||b[x+2]-u)-1 /* squares plus bias */
+(b[x^16]==k+36)) /* kling to non-virgin King */
-(R>>2); /* end-game Pawn-push bonus */
V=y+r+1&S?647-p:2*(u&y+16&32); /* promotion or 6/7th bonus */
b[y]+=V;i+=V; /* change piece, add score */
}

هوش مصنوعی شطرنج وجود داره

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

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

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

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

این توضیحات رو از این بابت دادم که بدونیم وقتی میگیم هوش مصنوعی شطرنج، یعنی واقعاً داریم از چی حرف می‌زنیم و منظورمون دقیقاً چیه.

کی اول به فکرش رسید شطرنج رو به ماشین یاد بده

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

تکه عجیب تاریخچه شطرنج اینجاست که اولین ماشینی که شطرنج بازی کرد، الکترونیکی نبود یا حتی کامپیوتر هم نبود، یک دستگاه الکترومکانیکی بود که توسط Torres y Quevedo در سال ۱۹۱۴ ساخته شده بود و از سیم کشی و رله و مکانیک اون هم فقط برای کنترل بخش کوچکی از بازی توسعه داده شده بود. تا قبل از سال ۱۹۵۱ هیچ کامپیوتری قادر نبود که شطرنج بازی کنه. منظور آینه که به اون حد از تکامل نرسیده بودند که قادر باشند چنین برنامه‌هایی رو اجرا کنند. تا این که پیشگامان کامپیوتر نظیر Shannon، Turing و Zuse الگوریتم‌های brute force و forward pruning را پایه گذاری کردند. اوج شکوفایی کامپیوترها بین سال‌های ۱۹۵۱ تا ۱۹۷۷ بود. کامپیوترهای آن دوران ابعاد خیلی بزرگی داشتند و قدرت پردازشی آنها در مقابل کامپیوترهای امروز به شوخی شباهت داشت. برای همین لازم بود که الگوریتم‌ها تا جای ممکن بهینه عمل کنند و از تک تک سیکل‌های ماشین بهترین استفاده رو به برن. برای همین الگوریتم forward pruning با هرس کردن درخت نتایج، امکان داشت تمام احتمال‌های ممکن رو بررسی نکنه و از ۳۵ حرکت ممکن فقط به ۸ حرکت اکتفا کنه. همین اصلاح‌ها باعث شد که برنامه‌ها تا حد خوبی قابل قبول باشند.

در سال ۱۹۴۷ برنامه‌نویس‌های روس برنامه‌ای به نام Kaissa معرفی کردند که فصل جدیدی در دنیای برنامه‌های شطرنج حساب می‌شد. الگوریتم Brute-Force که در برنامه Kaissa استفاده شده بود در واقع بررسی تمام حالات ممکن از درخت احتمال رو کنار گذاشته بود (این بحث رو زیاد بازش نمی‌کنم، چون باید الگوریتم‌های هرس آلفا بتا و خیلی چیزای دیگه حرف بزنیم که فکر می‌کنم باعث سردرگمی به شه). شاید بزرگ‌ترین دست آورد در زمینه هوش مصنوعی شطرنج، یکی هرس درخت احتمال بوده و یکی دیگه هش تیبل که کامپیوترها با قدرت محاسباتی محدود را قادر به اجرای بازی شطرنج کردند.

عکس فوق مربوط به اولین دوره مسابقات قهرمانی شطرنج رایانه‌ای جهان می‌باشد که در سال ۱۹۷۴ در استکهلم برگزار شد. استاد شطرنج شوروی و میشا دونسکوی، توسعه دهنده Kaissa در سمت راست و آلن بیسلی از تیم Tech2 در سمت چپ تصور. عملکرد Kaissa همه را شگفت زده کرد. دستگاه هر چهار بازی را برد!

دروان کامپیوترهای شخصی از ۱۹۷۶ شروع شد و هر روز با رقابت بین شرکت‌های تولید کننده قطعات قدرت پردازش و حجم حافظه کامپیوترها افزایش داشته است، از طرفی برنامه‌های هوش مصنوعی شطرنج با استفاده از این محبت هر روز هوشمندتر از روز پیش بوده‌اند. تا جایی که در سال ۲۰۰۶ یک کامپیوتر شخصی موجود در بازار قادر شد که قهرمان شطرنج جهان را شکست دهد.

اما واقعاً کی کامپیوترها قادر خواهند بود به خوبی انسان‌ها شطرنج بازی کنند سؤالی است که فکر نمی‌کنم هنوز جوابی براش وجود داشته باشه (شایدم وجود داشته باشد). الآن هوش مصنوعی ترجمه متون را از زبانی به زبان دیگر به خوبی انجام می‌دهند ولی همچنان مترجم انسانی خیلی بهتر این کار را انجام می‌دهد. فکر می‌کنم این مثال برای هوش مصنوعی شطرنج نیز صادق باشد.

Endspielautomat  1914

بذارید یه فلش بک بزنیم به ۱۹۱۴ و ماشین شطرنج Torres y Quevedo را ببینیم. در واقع این ماشین یک بازی کامل رو پوشش نمی‌داد و فقط بازی آخر (KRK) که شامل دو شاه و یک قلعه است را پوشش می‌داد. هر چند ممکنه به نظر ساده به رسه ولی واقعاً تصور پیاده سازی حرکات همین مهره‌های محدود، با استفاده از مکانیک واقعاً سخته:/

این ماشین با مقدار سیم کشی زیر برد و البته رله‌ها و قسمت‌های مکانیکی علاوه بر این که می‌توانست حرکت را پردازش کند، قادر به اجرای حرکت رو برد نیز بود. ظاهراً یک بازوی چنگال مانند داشته است که مهره مورد نظر را از روی برد بلند می‌کرده و در موقعیت جدید قرار می‌داده است. وقتی هم که حریف مهره خود را حرکت می‌دهد حرکت را به شکل خودکار درک می‌کند و رفتار مقتضی را انجام می‌دهد. نمونه اولیه در آزمایشگاه مکانیکی سوربن ساخته شد و البته Torres y Quevedo نمونه دوم این دستگاه را در سال ۱۹۲۲ ساخت که مهره‌ها با استفاده از مکانیسم‌های مکانیکی زیر برد جابجا می‌شدند. فیلم زیر نحوه بازی این ماشین فوق العاده رو نشان می‌دهد:

واقعاً مکانیک این ماشین تحسین بر انگیزه! در تصویر زیر الگوریتم Torres y Quevedo برای بازی KRK است که در محله ‌BYTE شماره سپتامبر ۱۹۷۸ چاپ شده.

Zuggenerator  1942

احتمالا اگر ما  رو دنبال کرده باشید، با آقای Konrad Zuse آشنایی دارید. کنراد در واقع اولین کسی بود که کامپیوتر دیجیتال را اول به شکل کاملا مکانیکی بعد با استفاده از رله پیاده سازی کرد. اگر تمایل دارید در مورد ایشون بیشتر بدانید، توصیه می کنم مقاله «اولین کامپیوتر با منطق دودویی الکترونیکی نبود!» را مطالعه کنید. بعد از این که Z3 ساخته شد، کنراد در مورد درخت احتمال و الگوریتم بازی KRK فکر کرد اما ایده اش را تا ۱۹۴۰ منتشر نکرد. کنراد در سال ۱۹۴۰ زبان برنامه نویسی Plankalkül را مطرح کرد که در واقع می‌توان گفت اولین زبان برنامه نویسی سطح بالا است. در کتاب Plankalkül مقاله ای راجب بازی شطرنج وجود دارد.

عکس فوق دست نوشته‌های کنراد در خصوص بازی KRK است که به زبان Plankalkül نوشته شده است.

منبع:سیسوگ