مسئله های اسباب بازی در هوش مصنوعی AI

مسئله های اسباب بازی در هوش مصنوعی AI

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

مسئله های اسباب بازی

اولین مسئله ای که در این مورد در نظر میگیریم، دنیای جاروبرقی است. این دنیا را میتوان بصورت یک مسئله فرموله کرد:

• حالت ها (States) : حالت بوسیله مکان عامل و مکانهای کثیف تعیین میشود. عامل در یکی از دو مکان است که هر کدام ممکن است کثیف باشند یا نباشند. لذا 8=2²*2 حالت در این دنیا وجود دارد. محیط بزرگی با n  مکان دارای   ⁿ2.n حالت است.

•حالت شروع (Initial state) : هر حالتی میتواند بعنوان حالت شروع طراحی شود..

• فعالیت ها (Actions) : در این محیط ساده، هر حالت فقط سه فعالیت انجام میدهد: Left (چپ)، Right (راست)، و Suck (مکش). محیط های بزرگتر ممکن است عملیات های Up  و Down نیز داشته باشند.

• مدل گذار یا تغییر حالت (Transition model) : هر یک از فعالیت ها، آثار مورد انتظار خودشان را دارند، اما حرکت به چپ در سمت چپ ترین مربع، حرکت به راست در سمت راست ترین مربع و مکش در مربع تمیز هیچ اثری ندارد.

• آزمون هدف (Goal test) : بررسی میکند که آیا تمام مربع ها تمیز هستند یا خیر؟

• هزینه مسیر (Path cost) : هزینه هر مسیر یک است. و در نتیجه هزینه مسیر برابر با تعداد مراحل موجود در مسیر است.

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

 

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

• حالت ها (States) : هر ترکیبی از صفر تا هشت وزیردر صفحه شطرنج، یک حالت است.

• حالت شروع (Initial state) : هیچ وزیری در صفحه شطرنج نیست.

• فعالیت ها (Actions) : اضافه کردن وزیر به مربع خالی.

• مدل گذار یا تغییر حالت (Transition model) : صفحه شطرنجی را برمیگرداند که وزیری در خانه ی خالی قرار داده شده است.

• آزمون هدف (Goal test) : هشت وزیردر صفحه شطرنج هستند که هیچ وزیری، وزیر دیگر را گارد نمی دهد.

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

• حالت ها (States) : تمام ترکیبات n  وزیر (n بین صفر و 8) ،که در هر ستون یک وزیر قرار دارد، بطوریکه هیچ وزیری وزیر دیگری را گارد نمیدهد  .

 

• فعالیت ها (Actions) : یک وزیر را به خانه ای در سمت چپ ترین ستون خالی اضافه کنید ، بطوریکه توسط هیچ وزیر دیگری گارد داده نشود.

این فرموله کردن فضای حالت هشت وزیر را از 10¹³*1.8 به 2057 کاهش میدهد و در نتیجه به راحتی میتوان جوابها را پیدا کرد.