الگوریتم‌های مهم هوش مصنوعی را اینجا زنده ببینید و با آن‌ها کار کنید: الگوریتم ژنتیکی که نسل به نسل جواب مسئله N وزیر را تکامل می‌دهد، الگوریتمی که گروه‌های پنهان یک شبکه اجتماعی را کشف می‌کند، الگوریتم‌های جستجویی که راه خروج از ماز را می‌یابند، و شطرنج با هوش مصنوعی‌ای که با جستجوی تخاصمی (مینیمکس و آلفا-بتا) فکر می‌کند و فکرش را به شما نشان می‌دهد. همه‌چیز در مرورگر شما اجرا می‌شود.
برازندگی بهترین فرد میانگین جمعیت هدف
الگوریتم ژنتیک از تکامل طبیعی الهام گرفته است: جمعیتی از راه‌حل‌های تصادفی ساخته می‌شود، بهترین‌ها انتخاب می‌شوند، با هم ترکیب می‌شوند (تقاطع) و کمی به‌طور تصادفی تغییر می‌کنند (جهش)، و این چرخه نسل به نسل تکرار می‌شود. در مسئله N وزیر باید N وزیر را روی صفحه N×N طوری چید که هیچ دو وزیری همدیگر را تهدید نکنند. برازندگی هر فرد، تعداد جفت وزیرهایی است که یکدیگر را تهدید نمی‌کنند؛ خطوط قرمز تهدیدهای باقی‌مانده را نشان می‌دهند.
این همان مثال کلاسیک کتاب راسل و نورویگ است که در درس هوش مصنوعی تدریس می‌کنم. نرخ جهش را صفر کنید و ببینید چطور جمعیت تنوعش را از دست می‌دهد و ممکن است نزدیک جواب گیر کند. منابع درس هوش مصنوعی
گره‌ها را با ماوس یا انگشت جابه‌جا کنید
در شبکه‌های اجتماعی، گروه‌هایی از افراد بیشتر با هم در ارتباط‌اند تا با بقیه؛ به این گروه‌ها «اجتماع» می‌گویند. این شبکه چند اجتماع پنهان دارد و الگوریتم «انتشار برچسب» تلاش می‌کند بدون هیچ اطلاع قبلی آن‌ها را کشف کند: هر گره بارها برچسبِ رایج‌ترین همسایه‌هایش را می‌گیرد.
کیفیت نتیجه با «پیمانگی» و «اطلاعات متقابل نرمال‌شده» (NMI) سنجیده می‌شود؛ همان معیارهایی که در مقاله ۲۰۲۵ خود برای ارزیابی الگوریتم ترکیبی فراابتکاری تشخیص اجتماع به کار برده‌ام. با افزایش «آمیختگی»، مرز اجتماع‌ها محوتر و کشف آن‌ها سخت‌تر می‌شود. مشاهده مقاله
برای کشیدن دیوار بکشید · نقطه شروع ● و هدف ★ را جابه‌جا کنید
| الگوریتم | بررسی‌شده | مسیر |
|---|
الگوریتم‌های جستجو از پایه‌های درس هوش مصنوعی‌اند. جستجوی سطح‌اول (BFS) کوتاه‌ترین مسیر را تضمین می‌کند ولی خانه‌های زیادی را می‌گردد؛ عمق‌اول (DFS) سریع جلو می‌رود ولی مسیرش لزوماً کوتاه نیست؛ حریصانه فقط به فاصله تا هدف نگاه می‌کند؛ و A* با ترکیب هزینه طی‌شده و تخمین فاصله باقی‌مانده، هم بهینه است و هم کم‌هزینه. چند الگوریتم را روی یک جدول اجرا و مقایسه کنید. منابع درس هوش مصنوعی
گسترش‌یافته در هر عمقاز سمت هدف (دوطرفه)
| الگوریتم | گسترش | مرز | حرکت | ثانیه |
|---|
جستجوی ناآگاهانه (کور) هیچ اطلاعی از فاصله هر وضعیت تا هدف ندارد: فقط وقتی هدف را ببیند آن را می‌شناسد و تفاوت الگوریتم‌ها تنها در ترتیب گسترش گره‌هاست. سطح‌اول لایه‌به‌لایه جلو می‌رود و کوتاه‌ترین جواب را پیدا می‌کند ولی مرزش مثل b^d بزرگ می‌شود. عمق‌اول در یک شاخه شیرجه می‌زند؛ حافظه بسیار کمی می‌خواهد ولی جوابش ممکن است بسیار طولانی باشد. عمق محدود در عمق مشخصی می‌ایستد و عمیق‌شونده تکراری حدهای ۰، ۱، ۲ و … را امتحان می‌کند و بهترینِ هر دو را دارد: کوتاه‌ترین جواب با حافظه عمق‌اول، به بهای گسترش دوباره لایه‌های کم‌عمق (در نمودار ببینید). هزینه یکنواخت ارزان‌ترین مسیر را زودتر گسترش می‌دهد و وقتی هزینه حرکت‌ها متفاوت است بهینه می‌ماند. دوطرفه از دو سر جستجو می‌کند و در وسط به هم می‌رسد: حدود ۲·b^(d/2) گره به‌جای b^d.
معمای ۸ دارای ۹!/۲ = ۱۸۱٬۴۴۰ وضعیت قابل‌دسترس است و نیمه دیگر هرگز در دسترس نیست، چون هیچ حرکتی زوجیت وارونگی‌ها را عوض نمی‌کند. «حالت حل‌نشدنی» را بزنید و ببینید کدام الگوریتم‌ها می‌توانند بفهمند جوابی نیست (کامل بودن). با A* در تب «الگوریتم‌های جستجو» مقایسه کنید که از تابع ابتکاری استفاده می‌کند. منابع درس هوش مصنوعی
در حال مرور وضعیت‌های قبلی هستید؛ برای بازگشت به بازی ⏭ را بزنید.
بازیکنان
مهره‌های شما (بازی تازه شروع می‌شود)
حرکت‌ها
نمودار ارزیابی در طول بازی
خط اصلی (ادامهای که انتظار دارد)
—
حرکتهای نامزد در ریشه درخت
ارزشها به واحد پیاده و از دید بازیکن نوبت است. «≤» یعنی آلفا-بتا ثابت کرده آن حرکت بهتر از این نیست و دیگر آن را نگشته؛ این همان هرس است. پیکان طلایی: بهترین حرکت فعلی؛ آبی: حرکتهایی که بعد از آن انتظار دارد.
الگوریتم جستجو
تابع ارزیابی
برای وضعیت روی صفحه: هر حرکت بازیکن نوبت (MAX) و پاسخ‌های حریف (MIN). MIN بدترین پاسخ برای MAX را برمی‌گزیند و MAX حرکتی را که بدترین حالتش از همه بهتر است. آلفا-بتا به محض اینکه یک پاسخ نشان دهد حرکتی از حرکت پیداشده بهتر نمی‌شود، بقیه پاسخ‌های آن را نمی‌گردد.
هر سه، همین وضعیت را تا یک عمق می‌گردند. آلفا-بتا همیشه همان مقدار مینیمکس را برمی‌گرداند و فقط شاخه‌هایی را نمی‌گردد که در نتیجه اثری ندارند. هر کدام چند وضعیت را بررسی می‌کند؟
| الگوریتم | وضعیتها | ثانیه | حرکت |
|---|
شطرنج یک بازی دو نفره، «جمع‌صفر» و با «اطلاعات کامل» است: سود یکی دقیقاً زیان دیگری است و هر دو همه‌چیز را می‌بینند. قضیه مینیمکس فون نویمان (۱۹۲۸) می‌گوید چنین بازی‌ای «مقدار» دارد: MAX نتیجه را بیشینه می‌کند با این فرض که MIN با حرکتی پاسخ می‌دهد که آن را کمینه کند. الگوریتم مینیمکس این مقدار را با جستجوی درخت بازی محاسبه می‌کند؛ اما چون در هر وضعیت حدود ۳۵ حرکت ممکن است، درخت با نرخ ۳۵ به توان d رشد می‌کند و هیچ رایانه‌ای نمی‌تواند آن را تا پایان بگردد.
…در عمق مشخصی می‌ایستد و وضعیت را با یک «تابع ارزیابی» ابتکاری (ارزش مهره‌ها، جای آن‌ها، امنیت شاه) تخمین می‌زند؛ با آلفا-بتا هرس می‌کند که با ترتیب کامل حرکت‌ها به‌جای ۳۵ به توان d حدود ۳۵ به توان d/۲ وضعیت را می‌گردد و در همان زمان به دو برابر عمق می‌رسد؛ عمق را گام‌به‌گام افزایش می‌دهد و وضعیت‌های دیده‌شده را به خاطر می‌سپارد (جدول جابه‌جایی)؛ و تبادل‌ها را بعد از افق جستجو ادامه می‌دهد (جستجوی سکون) تا وسط یک معاوضه متوقف نشود. اسلایدر «خطای عمدی» آن را مثل انسانی با «عقلانیت محدود» ضعیف می‌کند: یک خطای تصادفی ثابت در هر ارزیابی. منابع درس هوش مصنوعی
برای افزودن نقطه کلیک کنید · Shift یا کلیک راست برای دسته دیگر
هر نورون جمع وزن‌دار ورودی‌هایش را از یک «تابع فعال‌سازی» می‌گذراند (tanh در لایه‌های پنهان و سیگموید در خروجی که احتمال دسته آبی را می‌دهد). یادگیری یعنی تنظیم وزن‌ها برای کم کردن خطا: «پس‌انتشار خطا» سهم هر وزن در خطا را لایه به لایه از خروجی به عقب حساب می‌کند و «گرادیان کاهشی» آن را کمی در جهت مخالف جابه‌جا می‌کند.
پرسپترون را روی XOR امتحان کنید: یک نورون فقط خط راست می‌کشد و موفق نمی‌شود؛ همان نکته‌ای (مینسکی و پیپرت، ۱۹۶۹) که لایه‌های پنهان پاسخ آن‌اند. نرخ یادگیری زیاد خطا را بالا و پایین می‌برد و نرخ کم، یادگیری را کند می‌کند. منابع درس هوش مصنوعی
روی خانه بزنید: خالی ← دیوار ← تله
به عامل نمی‌گویند هدف کجاست: فقط پاداش می‌گیرد (۱۰+ در هدف، ۱۰− در تله و هزینه کوچکی برای هر گام) و برای هر خانه و هر حرکت، تخمینی از کل پاداش آینده (Q) نگه می‌دارد. بعد از هر حرکت آن را کمی اصلاح می‌کند: Q(s,a) ← Q(s,a) + α[r + γ·max Q(s′) − Q(s,a)]. پاداش هدف خانه به خانه به عقب پخش می‌شود و پیکان‌ها کم‌کم راه را نشان می‌دهند.
ε دوراهی «اکتشاف یا بهره‌برداری» است: با ε = ۰ عامل فقط همان را که بلد است تکرار می‌کند و شاید هرگز راه بهتری پیدا نکند و با ε = ۱ فقط پرسه می‌زند. γ میزان صبر است: پاداش بعدی امروز چقدر ارزش دارد. منابع درس هوش مصنوعی
برای افزودن نقطه کلیک کنید
| K | SSE | کاهش |
|---|
K-means به برچسب نیازی ندارد (یادگیری بدون نظارت). دو گام را تکرار می‌کند: هر نقطه را به نزدیک‌ترین مرکز نسبت می‌دهد و هر مرکز را به میانگین نقطه‌هایش می‌برد. هر دور مجموع مربع فاصله‌ها (SSE) را کم می‌کند، پس حتماً متوقف می‌شود؛ ولی شاید در کمینه محلی، و برای همین شروع مهم است: k-means++ مراکز را دور از هم انتخاب می‌کند.
«دو حلقه» را امتحان کنید: K-means دنبال گروه‌های گرد و فشرده است و حلقه‌ها را نصف می‌کند. جدول آرنج به انتخاب K کمک می‌کند: جایی که خوشه بیشتر، خطا را دیگر زیاد کم نمی‌کند. منابع درس هوش مصنوعی
