Search, Heuristics, and Game Playing
هوش مصنوعی برای همه: هوش مصنوعی چطور باهوش شد؟
- Representing a puzzle using states, legal actions, and a goal.
- Search trees and the rapid growth of possible action sequences.
- Breadth-first search and depth-first search through small diagrams.
- A heuristic as an estimate that guides exploration rather than guarantees correctness.
- Game trees and choosing moves while accounting for an opponent's possible responses.
- Why search produced important early successes in structured tasks but struggles with huge spaces and poor representations.
از هزارتو تا درخت جستوجو
```svg
<svg viewBox="0 0 800 450" xmlns="http://www.w3.org/2000/svg"><defs><marker id="arrow" markerWidth="10" markerHeight="10" refX="9" refY="5" orient="auto"><path d="M0 0 L10 5 L0 10 Z" class="tm-arrow"/></marker></defs><text x="400" y="30" text-anchor="middle" class="tm-text" font-size="19" direction="rtl">وضعیت: اتاق فعلی</text><text x="400" y="65" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">شروع</text><path d="M378 123 L262 202 M422 123 L538 202" class="tm-line" fill="none" stroke-width="2" marker-end="url(#arrow)"/><circle cx="400" cy="105" r="27" class="tm-accent"/><text x="400" y="112" text-anchor="middle" class="tm-text" font-size="22">A</text><text x="690" y="80" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">هدف</text><rect x="660" y="95" width="60" height="48" rx="12" class="tm-green"/><text x="690" y="126" text-anchor="middle" class="tm-text" font-size="22">F</text><path d="M225 243 L175 317 M255 243 L305 317 M545 243 L495 317 M575 243 L625 317" class="tm-line" fill="none" stroke-width="2" marker-end="url(#arrow)"/><path d="M422 123 L538 202 M545 243 L495 317" class="tm-line-accent tm-flow" fill="none" stroke-width="5" marker-end="url(#arrow)"/><circle cx="240" cy="220" r="27" class="tm-soft"/><circle cx="560" cy="220" r="27" class="tm-accent"/><text x="240" y="227" text-anchor="middle" class="tm-text" font-size="22">B</text><text x="560" y="227" text-anchor="middle" class="tm-text" font-size="22">C</text><circle cx="160" cy="340" r="27" class="tm-soft"/><circle cx="320" cy="340" r="27" class="tm-soft"/><circle cx="480" cy="340" r="27" class="tm-green"/><circle cx="640" cy="340" r="27" class="tm-soft"/><text x="160" y="347" text-anchor="middle" class="tm-text" font-size="22">D</text><text x="320" y="347" text-anchor="middle" class="tm-text" font-size="22">E</text><text x="480" y="347" text-anchor="middle" class="tm-text" font-size="22">F</text><text x="640" y="347" text-anchor="middle" class="tm-text" font-size="22">G</text><text x="400" y="420" text-anchor="middle" class="tm-text2" font-size="18" direction="rtl">حرکت مجاز: عبور از راهروی خروجی</text><text x="610" y="290" text-anchor="middle" class="tm-text-accent" font-size="16" direction="rtl">مسیر هدف</text></svg>
```
یک درخت، دو ترتیب بررسی
```svg
<svg viewBox="0 0 800 450" xmlns="http://www.w3.org/2000/svg"><text x="200" y="30" class="tm-text" font-size="21" text-anchor="middle">breadth-first search</text><text x="600" y="30" class="tm-text" font-size="21" text-anchor="middle">depth-first search</text><text x="400" y="62" class="tm-muted" font-size="16" text-anchor="middle" direction="rtl">هدف: F؛ انتخاب از چپ به راست</text><path d="M200 100L120 180M200 100L280 180M120 180L70 260M120 180L170 260M280 180L230 260M280 180L330 260M600 100L520 180M600 100L680 180M520 180L470 260M520 180L570 260M680 180L630 260M680 180L730 260" class="tm-line" fill="none"/><path d="M600 100L520 180L470 260M520 180L570 260M600 100L680 180L630 260" class="tm-line-accent" stroke-width="4" fill="none"/><g class="tm-surface"><circle cx="200" cy="100" r="23"/><circle cx="120" cy="180" r="23"/><circle cx="280" cy="180" r="23"/><circle cx="70" cy="260" r="23"/><circle cx="170" cy="260" r="23"/><circle cx="330" cy="260" r="23"/><circle cx="600" cy="100" r="23"/><circle cx="520" cy="180" r="23"/><circle cx="680" cy="180" r="23"/><circle cx="470" cy="260" r="23"/><circle cx="570" cy="260" r="23"/><circle cx="730" cy="260" r="23"/></g><circle cx="230" cy="260" r="23" class="tm-green"/><circle cx="630" cy="260" r="23" class="tm-green"/><g font-size="21" text-anchor="middle"><text x="200" y="107" class="tm-text">A</text><text x="120" y="187" class="tm-text">B</text><text x="280" y="187" class="tm-text">C</text><text x="70" y="267" class="tm-text">D</text><text x="170" y="267" class="tm-text">E</text><text x="230" y="267" class="tm-text">F</text><text x="330" y="267" class="tm-text">G</text><text x="600" y="107" class="tm-text">A</text><text x="520" y="187" class="tm-text">B</text><text x="680" y="187" class="tm-text">C</text><text x="470" y="267" class="tm-text">D</text><text x="570" y="267" class="tm-text">E</text><text x="630" y="267" class="tm-text">F</text><text x="730" y="267" class="tm-text">G</text></g><path d="M160 132H240M87 212H313M43 292H254" class="tm-line-accent" stroke-width="4" fill="none"/><text x="200" y="330" class="tm-text-accent" font-size="21" text-anchor="middle">A → B → C → D → E → F</text><text x="200" y="360" class="tm-muted" font-size="17" text-anchor="middle" direction="rtl">همسطحها، پیش از سطح بعد</text><text x="600" y="330" class="tm-text-accent" font-size="21" text-anchor="middle">A → B → D → E → C → F</text><text x="600" y="360" class="tm-muted" font-size="17" text-anchor="middle" direction="rtl">شاخهٔ چپ، پیش از شاخهٔ راست</text><text x="200" y="393" class="tm-text-green" font-size="16" text-anchor="middle" direction="rtl">هزینههای برابر: کمترین تعداد حرکت</text><text x="200" y="423" class="tm-text2" font-size="16" text-anchor="middle" direction="rtl">نگهداری گزینههای منتظر زیاد</text><text x="600" y="393" class="tm-text2" font-size="16" text-anchor="middle" direction="rtl">بدون تضمین کوتاهترین مسیر</text><text x="600" y="423" class="tm-text2" font-size="16" text-anchor="middle" direction="rtl">شاخهٔ بلند: تأخیر در بررسی بقیه</text></svg>
```
heuristic: راهنما، نه تضمین
```svg
<svg viewBox="0 0 800 450" xmlns="http://www.w3.org/2000/svg"><text x="400" y="35" class="tm-text" font-size="22" text-anchor="middle" direction="rtl">کدام شاخه را زودتر بررسی کنیم؟</text><path d="M400 105 L220 175 M400 105 L580 175" class="tm-line" fill="none" stroke-width="3"/><circle cx="400" cy="85" r="30" class="tm-surface"/><circle cx="220" cy="195" r="30" class="tm-surface"/><circle cx="580" cy="195" r="30" class="tm-surface"/><g font-size="23" text-anchor="middle"><text x="400" y="93" class="tm-text">A</text><text x="220" y="203" class="tm-text">B</text><text x="580" y="203" class="tm-text">C</text></g><text x="400" y="390" class="tm-muted" font-size="19" text-anchor="middle" direction="rtl">heuristic: تخمین حرکتهای باقیمانده تا هدف</text><rect x="125" y="240" width="190" height="48" rx="12" class="tm-soft"/><rect x="485" y="240" width="190" height="48" rx="12" class="tm-accent"/><text x="220" y="271" class="tm-text" font-size="22" text-anchor="middle">\(h(B)=3\)</text><text x="580" y="271" class="tm-text" font-size="22" text-anchor="middle">\(h(C)=1\)</text><path d="M610 213 L725 305 M550 215 L420 305" class="tm-line" fill="none" stroke-width="3"/><circle cx="405" cy="325" r="27" class="tm-green"/><circle cx="740" cy="325" r="27" class="tm-surface"/><text x="405" y="333" class="tm-text" font-size="22" text-anchor="middle">F</text><text x="740" y="333" class="tm-text" font-size="22" text-anchor="middle">G</text><text x="260" y="335" class="tm-text-green" font-size="18" text-anchor="middle">\(h(F)=0\)</text><text x="405" y="365" class="tm-text-green" font-size="17" text-anchor="middle" direction="rtl">آزمون هدف: تأیید</text><text x="400" y="429" class="tm-text-green" font-size="21" text-anchor="middle" direction="rtl">مسیر جواب: \(A\to C\to F\)</text><rect x="40" y="63" width="260" height="95" rx="12" class="tm-gold tm-enter"/><text x="170" y="94" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">تخمین صفر، اثبات هدف نیست</text><text x="170" y="128" class="tm-text" font-size="18" text-anchor="middle" direction="rtl">تأیید رسیدن با آزمون هدف</text></svg>
```
انتخاب حرکت با منطق minimax
دو حرکت: چپ و راست؛ پس از هر حرکت، دو پاسخ حریف.
امتیاز بیشتر برای تو بهتر است؛ حریف امتیاز تو را کمتر میکند.
**امتیازهای پایان بازی پس از چپ**
\[ (3,\;1) \]
**امتیازهای پایان بازی پس از راست**
\[ (2,\;2) \]
**پاسخ حریف در شاخهٔ چپ**
\[ \min(3,1)=1 \]
وجود امتیاز \(3\) کافی نیست؛ پاسخ را حریف انتخاب میکند.
**پاسخ حریف در شاخهٔ راست**
\[ \min(2,2)=2 \]
**انتخاب تو: راست**
\[ \max\bigl(\underbrace{\min(3,1)}_{1},\underbrace{\min(2,2)}_{2}\bigr)=\max(1,2)=2 \]
با فرض بهترین پاسخ حریف علیه تو و دانستن دقیق امتیازهای پایان بازی.
توان و محدودیتهای جستوجو
**حل مسئله با قواعد روشن**
تعریف دقیق مسئله ← ساخت حرکتهای مجاز ← جستوجوی جواب
دستکاری منظم نمادها، حتی بدون یادگیری از مثالها
**پس از حرکت اول**
از هر وضعیت \(10\) حرکت ممکن؛ بدون حذف یا ادغام مسیرها.
\[N_1=10\]
**پس از حرکت دوم**
هر دنباله، \(10\) ادامه دارد.
\[N_2=10\times10=100\]
**پس از حرکت سوم**
هر یک از \(100\) دنباله، \(10\) ادامه دارد.
\[N_3=100\times10=1000\]
تعداد دنبالهها در همان عمق؛ نه مجموع بررسیها.
**بازنمایی باید اطلاعات لازم را نگه دارد**
بدون وابستگی به کلید: نام اتاق
با درِ وابسته به کلید: نام اتاق + داشتن یا نداشتن کلید
حذف وضعیت کلید ← تشخیص اشتباه حرکتهای ممکن
**موفقیت محدود، نه اثبات توانایی عمومی**
بردن در بازی با قواعد مشخص، بهتنهایی فهم و توانایی عمومی را ثابت نمیکند.
کیفیت نتیجه به قواعد، ترتیب بررسی و heuristic بستگی دارد.
Back to course