Chapterبەش 6 · Lectureوانە 6.3

Alpha-Beta Pruningبڕینی ئەلفا-بێتا

Make minimax much faster without changing its answer: what alpha and beta mean, when a branch can be cut (α ≥ β), a worked example on a small tree, and the course's tic-tac-toe program with its hidden bug fixed so that the pruning really cuts (549,945 → 48,382 → 18,296 positions).

زۆر خێراتر بکە بەبێ ئەوەی وەڵامەکەی بگۆڕێت: ئەلفا و بێتا چین، کەی دەتوانرێت لقێک ببڕدرێت (α ≥ β)، نموونەیەکی کارپێکراو لەسەر دارێکی بچووک و بەرنامەی کۆرسەکە، لەگەڵ چاککردنی هەڵەیەکی شاراوە بۆ ئەوەی بڕینەکە بەڕاستی ببڕێت (⁦549,945⁩ ← ⁦48,382⁩ ← ⁦18,296⁩ پێگە).

26 min read25 خولەک خوێندنەوە · 18 stepsهەنگاو

What you will learnچی فێر دەبیت

Explain what alpha-beta pruning does and why it always chooses the same move as minimax.
Say what α and β mean, where they start, and when a cut happens (α ≥ β).
Run alpha-beta by hand on a small game tree and name the branches that are pruned.
Read the tic-tac-toe alpha-beta program and explain what each function does.
Find and fix the break that leaves only the inner loop, and measure the difference.

ڕوونی بکەیتەوە چی دەکات و بۆچی هەمیشە هەمان جووڵەی هەڵدەبژێرێت.
بڵێیت α و β چین، لە کوێوە دەست پێدەکەن و کەی بڕین ڕوو دەدات (α ≥ β).
بە دەست ئەلفا-بێتا لەسەر بچووک جێبەجێ بکەیت و ئەو لقانە دیاری بکەیت کە دەبڕدرێن.
بەرنامەی بە ئەلفا-بێتا بخوێنیتەوە و ڕوونی بکەیتەوە هەر چی دەکات.
ئەو breakـە بدۆزیتەوە کە تەنیا لە ناوەوە دەردەچێت، چاکی بکەیت و جیاوازییەکە بپێویت.

Why minimax needs a shortcutبۆچی Minimax پێویستی بە کورتەڕێیەکە

In the minimax lesson the computer looks at every possible future move before it plays, even the moves that are clearly bad. The answer is correct, but the work is huge. On an empty tic-tac-toe board, the course's minimax program examines 549,945 board positions before it makes its first move. In a bigger game such as chess, looking at every move is impossible.

لە وانەی Minimaxدا، کۆمپیوتەر پێش ئەوەی یاری بکات سەیری هەموو جووڵەیەکی داهاتوو دەکات، تەنانەت ئەو جووڵانەش کە بە ئاشکرا خراپن. وەڵامەکە دروستە، بەڵام کارەکە زۆر زۆرە. لەسەر تەختەیەکی بەتاڵی ، بەرنامەی کۆرسەکە پێش ئەوەی یەکەم جووڵە بکات، ⁦549,945⁩ پێگەی تەختە دەپشکنێت. لە یارییەکی گەورەتردا وەک شەترەنج، سەیرکردنی هەموو جووڵەکان مەحاڵە.

Definitionپێناسە

A faster form of minimax that skips branches that cannot change the final decision. It keeps α (the best score MAX can already guarantee) and β (the best score MIN can guarantee) and stops exploring a branch when α ≥ β; it always chooses the same move as minimax.

شێوەیەکی خێراترە لە کە ئەو لقانە پشتگوێ دەخات کە ناتوانن بڕیاری کۆتایی بگۆڕن. α (باشترین نمرە کە پێشتر گەرەنتی دەکات) و β (باشترین نمرە کە گەرەنتی دەکات) هەڵدەگرێت و کاتێک α ≥ β بوو گەڕان لەو لقەدا دەوەستێنێت؛ هەمیشە هەمان جووڵەی هەڵدەبژێرێت.

Alpha-beta pruning is a faster form of minimax. When it finds out that a move is bad, it stops exploring the other continuations of that move, so it saves a lot of time. The idea is simple: if you already know that a move cannot beat a move you have found before, you do not need to know exactly how bad it is.

شێوەیەکی خێراتری . کاتێک بۆی دەردەکەوێت جووڵەیەک خراپە، واز لە پشکنینی ڕێگەکانی دیکەی ئەو جووڵەیە دەهێنێت، بۆیە کاتێکی زۆر پاشەکەوت دەکات. بیرۆکەکە سادەیە: ئەگەر پێشتر دەزانیت جووڵەیەک ناتوانێت لە جووڵەیەکی دیکە باشتر بێت کە پێشتر دۆزیوتەتەوە، پێویست ناکات بزانیت تا چ ڕادەیەک خراپە.

Not "only the best moves"نەک «تەنیا باشترین جووڵەکان»

The course's article says that alpha-beta "looks only at the best moves and leaves the bad ones". That is not exact. Alpha-beta does not guess which moves are good. It gives exactly the same value and the same move as minimax; it only skips branches that, as it can prove, cannot change the decision. We checked this: in all 2,423 tic-tac-toe positions where x is to move, minimax and alpha-beta choose the same move.

وتارەکەی کۆرسەکە دەڵێت ئەلفا-بێتا «تەنیا سەیری باشترین جووڵەکان دەکات و واز لە خراپەکان دەهێنێت». ئەمە ورد نییە. ئەلفا-بێتا مەزەندە ناکات کام جووڵە باشە. ڕێک هەمان نرخ و هەمان جووڵەی دەدات؛ تەنیا ئەو لقانە پشتگوێ دەخات کە دەتوانێت بیسەلمێنێت ناتوانن بڕیارەکە بگۆڕن. ئەمەمان تاقی کردەوە: لە هەموو ئەو ⁦2,423⁩ پێگەیەی کە سەرەی xـە، و ئەلفا-بێتا هەمان جووڵە هەڵدەبژێرن.

Quick checkپشکنینی خێراWhat does alpha-beta pruning change, compared with minimax? چی دەگۆڕێت بە بەراورد لەگەڵ ؟The scores of the finished gamesنمرەکانی یارییە تەواوبووەکانThe rules of the gameیاساکانی یارییەکەHow many positions the computer examinesژمارەی ئەو پێگانەی کۆمپیوتەر دەیانپشکنێتThe move that the computer choosesئەو جووڵەیەی کۆمپیوتەر هەڵیدەبژێرێت

Why it is called "alpha-beta pruning"بۆچی ناوی نراوە «بڕینی ئەلفا-بێتا»

The name has two parts. Alpha (α) and beta (β) are the first two letters of the Greek alphabet; in Kurdish they are read «ئەلفا» and «بێتا». The algorithm keeps two numbers with these names. Prune means "cut": the algorithm decides when a path in the tree is not needed, and cuts it so that it is never searched.

ناوەکە دوو بەشی هەیە. ئەلفا (α) و بێتا (β) دوو پیتی یەکەمی ئەلفوبێی گریکین؛ بە کوردی «ئەلفا» و «بێتا» دەخوێنرێنەوە. دوو ژمارە بەم ناوانەوە هەڵدەگرێت. وشەی Prune هاوواتای «Cut»ـە و بە واتای «بڕین» دێت: بڕیار دەدات کەی ڕێگەیەک لە پێویست نییە و دەیبڕێت تاکو هەرگیز نەپشکنرێت.

Pruning a vineبڕینەوەی لقی مێو

At the end of winter, before the buds open, farmers in the villages around Halabja cut back the branches of their grape vines. A branch that will not give fruit only takes the plant's strength, so it is cut, and the vine puts its energy into the useful branches. Alpha-beta does the same with the game tree: it cuts branches that cannot give a better result.

لە کۆتایی زستاندا، پێش ئەوەی چرۆ بکەنەوە، جووتیارانی گوندەکانی دەوروبەری هەڵەبجە لقی مێوەکانیان دەبڕنەوە. ئەو لقەی بەر نەگرێت تەنیا هێزی ڕووەکەکە دەبات، بۆیە دەبڕدرێت و مێوەکە هێزی خۆی دەخاتە ناو لقە بەسوودەکانەوە. ئەلفا-بێتا هەمان کار لەگەڵ دەکات: ئەو لقانە دەبڕێت کە ناتوانن ئەنجامێکی باشتر بدەن.

Where the analogy stops workingسنووری ئەم نموونەیە

A farmer cuts from experience and can be wrong. Alpha-beta cuts a branch only when it is certain that the branch cannot change the decision, so it never loses the best move.

جووتیار لە ئەزموونەوە دەبڕێت و دەکرێت هەڵە بکات. ئەلفا-بێتا تەنیا کاتێک لقێک دەبڕێت کە دڵنیایە ئەو لقە ناتوانێت بڕیارەکە بگۆڕێت، بۆیە هەرگیز باشترین جووڵە لەدەست نادات.

Alpha and beta: two guaranteed scoresئەلفا و بێتا: دوو نمرەی گەرەنتیکراو

While the search goes down the game tree, it carries two numbers:

کاتێک گەڕانەکە بە دادەبەزێت، دوو ژمارە لەگەڵ خۆی دەبات:

α (alpha) is the highest score that the maximizing player (MAX, the AI) can already guarantee on the path searched so far.
β (beta) is the lowest score that the minimizing player (MIN, the opponent) can already guarantee: MIN can hold MAX to β or less.

α (ئەلفا) ئەو نمرە بەرزەیە کە (MAX، واتە ) تا ئێستا لەو ڕێگەیەی پشکنراوە گەرەنتی دەکات.
β (بێتا) ئەو نمرە نزمەیە کە (MIN، واتە دژەکە) تا ئێستا گەرەنتی دەکات: MIN دەتوانێت نمرەی MAX لە β یان کەمتردا ڕابگرێت.

At the start nothing is known yet, so alpha starts at negative infinity (−∞) and beta at positive infinity (+∞). In Python these are -float('inf') and float('inf').

لە سەرەتادا هێشتا هیچ شتێک نازانرێت کە چ جووڵەیەک دەکرێت، بۆیە ئەلفا لە سالب (−∞) دەست پێدەکات و بێتا لە بێسنووری موجەب (⁦+⁩∞). لە ئەمانە -float('inf') و float('inf')ن.

Any score that is better for the AI than −∞ replaces it. Think of a number line: alpha only moves to the right (up). Beta does the opposite: the opponent tries to block the AI and lower its score, so beta only moves to the left (down). The scores between α and β are the only ones that can still change the decision.

هەر نمرەیەک کە بۆ لە −∞ باشتر بێت، جێگەی دەگرێتەوە. هێڵێکی ژمارەیی بهێنە بەرچاوی خۆت: ئەلفا تەنیا بەرەو ڕاست (بەرەو سەرەوە) دەجووڵێت. بێتا بە پێچەوانەوەیە: دژەکە هەوڵ دەدات ڕێی بگرێت و نمرەکەی کەم بکاتەوە، بۆیە بێتا تەنیا بەرەو چەپ (بەرەو خوارەوە) دەجووڵێت. تەنیا ئەو نمرانەی نێوان α و β دەتوانن هێشتا بڕیارەکە بگۆڕن.

α only goes up, β only goes down. When they meet or cross (α ≥ β), the rest of that position can be cut.α تەنیا بەرز دەبێتەوە و β تەنیا نزم دەبێتەوە. کاتێک بەیەک دەگەن یان لە یەکتر تێدەپەڕن (α ≥ β)، ئەوەی ماوە لەو پێگەیە دەتوانرێت ببڕدرێت.CêIT

α and β are scores, not playersα و β نمرەن، نەک یاریزان

To keep it simple, the article also says that "alpha means the AI and beta means the opponent (maybe you)". Remember the exact meaning: α and β are numbers (guaranteed scores), not players. MAX's moves can raise α, MIN's moves can lower β, and both numbers are passed down to every position below.

وتارەکە بۆ سادەکردن دەڵێت «ئەلفا مەبەست لە و بێتا مەبەست لە دژەکەیە (کە دەکرێت تۆ بیت)». واتا وردەکە لە بیر بێت: α و β ژمارەن (نمرەی گەرەنتیکراو)، نەک یاریزان. جووڵەکانی MAX دەتوانن α بەرز بکەنەوە و جووڵەکانی MIN دەتوانن β نزم بکەنەوە؛ هەردوو ژمارەکەش بۆ هەموو پێگەکانی خوارەوە دەنێردرێن.

Alpha and beta: two guaranteed scoresئەلفا و بێتا: دوو نمرەی گەرەنتیکراو

The cut rule: α ≥ βیاسای بڕین: α ≥ β

When alpha is greater than or equal to beta (α ≥ β), we stop looking at the other moves of this position. Why? The opponent can already choose a move here that gives β or less. But the AI already has another move with a guaranteed score of α, which is at least as good. So the AI will never let the game come to this position. Searching it further cannot improve the result: this is the moment of pruning.

کاتێک ئەلفا گەورەتر یان یەکسان بێت بە بێتا (α ≥ β)، واز لە سەیرکردنی جووڵەکانی دیکەی ئەم پێگەیە دەهێنین. بۆچی؟ دژەکە لێرەدا دەتوانێت جووڵەیەک هەڵبژێرێت کە β یان کەمتر دەدات. بەڵام خۆی جووڵەیەکی دیکەی هەیە بە نمرەی گەرەنتیکراوی α، کە لانیکەم بە هەمان ئەندازە باشە. بۆیە هەرگیز ناهێڵێت یارییەکە بگاتە ئەم پێگەیە. پشکنینی زیاتری ناتوانێت ئەنجامەکە باشتر بکات: ئەمە ئەو کاتەیە کە بڕین ڕوو دەدات.

Beta cut-off: at MAX's position, α has risen to β or more. MIN, one level up, will avoid this position.
Alpha cut-off: at MIN's position, β has fallen to α or less. MAX, one level up, will avoid this position.

بڕینی بێتا: لە پێگەی MAXدا، α بەرز بووەتەوە بۆ β یان زیاتر. MIN، لە ئاستی سەرەوە، خۆی لەم پێگەیە لادەدات.
بڕینی ئەلفا: لە پێگەی MINدا، β دابەزیوە بۆ α یان کەمتر. MAX، لە ئاستی سەرەوە، خۆی لەم پێگەیە لادەدات.

The course's code writes the same test the other way round: if beta <= alpha:. beta <= alpha and alpha >= beta mean exactly the same thing.

کۆدی کۆرسەکە هەمان پشکنین بە پێچەوانەوە دەنووسێت: if beta <= alpha:. beta <= alpha و alpha >= beta ڕێک هەمان واتایان هەیە.

Quick checkپشکنینی خێراAt MIN's position, α = 5. The newest move makes β = 3. What happens?لە پێگەی MINدا، α = 5ـە. دوایین جووڵە β دەکات بە 3. چی ڕوو دەدات؟Nothing: search the remaining moves as usualهیچ: جووڵەکانی ماوە وەک هەمیشە بپشکنەRestart the search with α = 3گەڕان لە سەرەتاوە دەست پێبکەرەوە بە α = 3Cut: skip the remaining moves of this positionبڕین: جووڵەکانی ماوەی ئەم پێگەیە پشتگوێ بخەMAX must now choose this positionئێستا MAX دەبێت ئەم پێگەیە هەڵبژێرێت

The stubborn friend and the restaurantsدۆستە کەللەڕەقەکە و چێشتخانەکان

Choosing a restaurant with a stubborn friendهەڵبژاردنی چێشتخانە لەگەڵ دۆستێکی کەللەڕەق

You and a stubborn friend want to eat out. You play the AI: you want the best restaurant. Your friend plays the opponent: from your choices, he always picks the worst one. You look around and find a restaurant with reviews of 9. Then your friend finds one on the same street with bad food: 2. You realise that your friend is stubborn: whatever you do on this street, he will pick the bad one. So you stop looking at the other restaurants there and cut those paths.

وەهای دابنێ کە لەگەڵ دۆستە کەللەڕەقەکەتدایت و دەتانەوێت بچنە چێشتخانەیەک. تۆ ڕۆڵی دەبینیت: باشترین چێشتخانە هەڵدەبژێریت. دۆستەکەت ڕۆڵی دژەکە دەبینێت: لەنێو بژاردەکانتدا هەمیشە خراپترینیان هەڵدەبژێرێت. کاتێک چاو بە چێشتخانەکاندا دەگێڕیت، دانەیەکیان بە هەڵسەنگاندنی 9ـەوە دەبینیت. پاشان دۆستەکەت لە هەمان شەقامدا چێشتخانەیەک بە خواردنی خراپەوە دەدۆزێتەوە: 2. بۆت دەردەکەوێت کە دۆستەکەت کەللەڕەقە و هەرچییەک بکەیت لەم شەقامەدا خراپەکە هەڵدەبژێرێت. بۆیە چیدی بەدوای چێشتخانەکانی دیکەی ئەوێدا ناگەڕێیت و ئەو ڕێگانە دەبڕیت.

Where the analogy stops workingسنووری ئەم نموونەیە

The story works only because you already have a better choice elsewhere: on the first street the worst restaurant was still a 4. Without that guaranteed 4 (your α), seeing a 2 would not be a reason to stop.

چیرۆکەکە تەنیا لەبەر ئەوە کار دەکات کە پێشتر لە شوێنێکی دیکە بژاردەیەکی باشترت هەیە: لە شەقامی یەکەمدا خراپترین چێشتخانە هێشتا 4 بوو. بەبێ ئەو 4ـە گەرەنتیکراوە (αـەکەت)، بینینی 2 هۆکار نییە بۆ وەستان.

The analogy and the treeنموونەکە و
Storyچیرۆکەکە	Game tree
You choose a streetتۆ شەقامێک هەڵدەبژێریت	MAX chooses a move (the root)MAX جووڵەیەک هەڵدەبژێرێت ()
Your friend chooses a restaurant on that streetدۆستەکەت چێشتخانەیەک لەو شەقامەدا هەڵدەبژێرێت	MIN chooses a replyMIN وەڵامێک هەڵدەبژێرێت
The review of a restaurantهەڵسەنگاندنی چێشتخانەیەک	The score of a leaf (a finished game) (یارییەکی تەواوبوو)
The worst restaurant of the first street: 4خراپترین چێشتخانەی شەقامی یەکەم: 4	α = 4
Your friend finds a 2 on the second streetدۆستەکەت لە شەقامی دووەمدا 2 دەدۆزێتەوە	β = 2 ≤ α: cutβ = 2 ≤ α: بڕین

Quick checkپشکنینی خێراIn the restaurant story, why can you stop looking at the second street?لە چیرۆکی چێشتخانەکاندا، بۆچی دەتوانیت واز لە سەیرکردنی شەقامی دووەم بهێنیت؟Because 9 is a very good reviewچونکە 9 هەڵسەنگاندنێکی زۆر باشەBecause you are tiredچونکە ماندوویتBecause your friend will pick 2 or worse there, and you already have 4 on the first streetچونکە دۆستەکەت لەوێ 2 یان خراپتر هەڵدەبژێرێت و تۆ پێشتر لە شەقامی یەکەم 4ـت هەیەBecause the second street has fewer restaurantsچونکە شەقامی دووەم چێشتخانەی کەمترە

A worked example on a small treeنموونەیەکی کارپێکراو لەسەر دارێکی بچووک

Here is a small game tree with the numbers of the restaurant story. MAX moves first and has three moves: A, B and C. After each move, MIN has three replies. The leaves are the final scores (high is good for MAX). We search from left to right, like the program does.

ئەمە بچووکە بە ژمارەکانی چیرۆکی چێشتخانەکان. MAX یەکەمجار دەجووڵێت و سێ جووڵەی هەیە: A، B و C. دوای هەر جووڵەیەک، MIN سێ وەڵامی هەیە. کۆتایین (بەرز بۆ MAX باشە). وەک بەرنامەکە، لە چەپەوە بەرەو ڕاست دەگەڕێین.

Alpha-beta on a small tree: the greyed leaves are never looked at. لەسەر دارێکی بچووک: خۆڵەمێشییەکان هەرگیز سەیر ناکرێن.CêIT

Move Aجووڵەی A
MIN looks at 4, 7 and 5 and would choose 4. So A is worth 4. Back at the root, MAX can now guarantee 4: α = 4.
MIN سەیری 4، 7 و 5 دەکات و 4 هەڵدەبژێرێت. کەواتە A نرخەکەی 4ـە. لە ، MAX ئێستا دەتوانێت 4 گەرەنتی بکات: α = 4.
Move Bجووڵەی B
The first reply is 9 (β = 9, still above α). The second reply is 2: now β = 2 ≤ α = 4. MIN can hold MAX to 2 or less after B, and MAX already has 4 from A. Cut: the last reply (6) is never looked at.
یەکەم وەڵام 9ـە (β = 9، هێشتا لە α بەرزترە). وەڵامی دووەم 2ـە: ئێستا β = 2 ≤ α = 4. دوای B، MIN دەتوانێت MAX لە 2 یان کەمتردا ڕابگرێت و MAX پێشتر لە Aـەوە 4ـی هەیە. بڕین: سەیری دوایین وەڵام ⁦(6)⁩ هەرگیز ناکرێت.
Move Cجووڵەی C
The first reply is 3: β = 3 ≤ α = 4. Cut at once: 8 and 5 are skipped.
یەکەم وەڵام 3ـە: β = 3 ≤ α = 4. دەستبەجێ بڕین: 8 و 5 پشتگوێ دەخرێن.
The decisionبڕیارەکە
The root's value is max(4, ≤2, ≤3) = 4, so MAX plays A. Only 6 of the 9 leaves were looked at. Minimax would look at all 9 and reach the same 4.
نرخی ⁦max(4, ≤2, ≤3) = 4⁩ـە، بۆیە MAX جووڵەی A دەکات. تەنیا سەیری 6 لە 9 کرا. سەیری هەر 9 دەکات و دەگاتە هەمان 4.

Quick checkپشکنینی خێراIn this tree, why is the value of B written as "≤ 2" and not as an exact number?لەم دارەدا، بۆچی نرخی B بە «≤ 2» نووسراوە و نەک بە ژمارەیەکی ورد؟Because 2 is the largest leaf of Bچونکە 2 گەورەترین نۆدی گەڵای BـەBecause MAX always chooses Bچونکە MAX هەمیشە B هەڵدەبژێرێتBecause the search stopped before the last leaf of B; its exact value was not neededچونکە گەڕان پێش دوایین نۆدی گەڵای B ڕاوەستا؛ نرخە وردەکەی پێویست نەبووBecause B has no leavesچونکە B هیچ نۆدێکی گەڵای نییە

Minimax with Alpha Beta PruningJohn Levine · Englishئینگلیزی · 457K viewsبینین · 8.1K likesلایک · Partبەشی 4:33–13:43 (ofلە 13:43)
A lecturer works through alpha-beta pruning on a small tree, writing v, α and β at every node and cutting when α ≥ β.
مامۆستایەک لەسەر بچووک هەنگاو بە هەنگاو جێبەجێ دەکات: لە هەر `v`، `α` و `β` دەنووسێت و کاتێک `α ≥ β` بێت لقەکە دەبڕێت.
Plays 4:33 to the end (13:43): one tree worked node by node with v, α and β. From 10:22 ('example 2') it does the right half of the same tree, where a MIN node is cut because its value 2 ≤ α = 8.
لە ⁦4:33⁩ تا کۆتایی ⁦(13:43)⁩ لێدەدرێت: یەک بە لەگەڵ `v`، `α` و `β` چارەسەر دەکرێت. لە ⁦10:22⁩ـەوە («⁦example 2⁩») نیوەی ڕاستی هەمان چارەسەر دەکات، کە تێیدا MIN دەبڕدرێت، چونکە بەهاکەی ⁦(2)⁩ لە `α = 8` زیاتر نییە.

A worked example on a small treeنموونەیەکی کارپێکراو لەسەر دارێکی بچووک

The same example in Pythonهەمان نموونە بە Python

This short program runs alpha-beta on the same tree and prints α and β after every step. A number is a leaf; a list is a position with moves.

ئەم بەرنامە کورتە ئەلفا-بێتا لەسەر هەمان دار جێبەجێ دەکات و دوای هەر هەنگاوێک α و β چاپ دەکات. ژمارە ؛ پێگەیەکە کە جووڵەی تێدایە.

small_tree.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import math

# A small game tree. A number is a leaf (the final score of a game).
# A list is a position with moves. The root is MAX's turn,
# the three lists inside it are MIN's turn.
tree = [[4, 7, 5],   # move A
        [9, 2, 6],   # move B
        [3, 8, 5]]   # move C

looked_at = []       # the leaves we really visited


def alpha_beta(node, alpha, beta, maximizing, name, pad=""):
    if not isinstance(node, list):           # a leaf: the game is over
        looked_at.append(node)
        return node
    print(f"{pad}{name}: alpha={alpha}, beta={beta}")
    best = -math.inf if maximizing else math.inf
    for i, child in enumerate(node):
        score = alpha_beta(child, alpha, beta, not maximizing, "ABC"[i], pad + "  ")
        if maximizing:
            best = max(best, score)
            alpha = max(alpha, best)
        else:
            best = min(best, score)
            beta = min(beta, best)
        print(f"{pad}  after {score}: alpha={alpha}, beta={beta}")
        if alpha >= beta:
            skipped = len(node) - i - 1
            print(f"{pad}  alpha >= beta -> cut! {skipped} move(s) skipped")
            break
    return best


value = alpha_beta(tree, -math.inf, math.inf, True, "root")
print("Value of the root:", value)
total = sum(len(move) for move in tree)
print("Leaves looked at:", looked_at, "->", len(looked_at), "of", total)

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 6-8

The tree: three moves for MAX, three replies for MIN after each.

دارەکە: سێ جووڵە بۆ MAX و دوای هەر یەکێکیان سێ وەڵام بۆ MIN.

Lineدێڕی 14-16

A leaf: remember that we looked at it, and return its score.

: لە بیرمان بێت کە سەیرمان کردووە و بگەڕێنەرەوە.

Lineدێڕی 21-26

MAX can only raise α; MIN can only lower β.

MAX تەنیا دەتوانێت α بەرز بکاتەوە؛ MIN تەنیا دەتوانێت β نزم بکاتەوە.

Lineدێڕی 28-31

The cut rule. break leaves the only loop, so the remaining moves are skipped.

یاسای بڕین. break لە تاکە دەردەچێت، بۆیە جووڵەکانی ماوە پشتگوێ دەخرێن.

The tic-tac-toe program, function by functionبەرنامەی یاریی ئێکس‌وئۆ، کردار بە کردار

The course's article explains its Python program (MinmaxAlphaBetaPruning.py) function by function. It has the same structure as the course's minimax file (Minimax.py), with two functions renamed: can_move (called make_move there) and is_player_won (called check_move there). In the tic-tac-toe lesson the same two jobs are done by can_insert and player_won. Here is what each function does:

وتارەکەی کۆرسەکە بەرنامە (MinmaxAlphaBetaPruning.py) بە ڕوون دەکاتەوە. هەمان پێکهاتەی کۆرسەکەی (Minimax.py) هەیە و تەنیا ناوی دوو گۆڕاوە: can_move (لەوێ ناوی make_moveـە) و is_player_won (لەوێ ناوی check_moveـە). لە وانەی یاریی ئێکس‌وئۆدا هەمان دوو کار بە can_insert و player_won دەکرێن. ئەمە کاری هەر :

The functions of the alpha-beta tic-tac-toe program بەرنامەی بە ئەلفا-بێتا
Function	What it doesچی دەکات
`print_board`	Shows the board on the screen: goes through the rows and columns (each cell holds 'x', 'o' or is empty) and prints divider lines between the rows so that the board looks nicer.تەختەی ئێستای یارییەکە لەسەر شاشە پیشان دەدات: بەنێو ڕیز و ستوونەکاندا دەگەڕێت (هەر خانەیەک 'x' یان 'o'ـی تێدایە یان بەتاڵە) و هێڵی جیاکەرەوە لە نێوان ڕیزەکاندا چاپ دەکات تاکو تەختەکە جوانتر دەربکەوێت.
`can_move`	Checks whether the player may move into a cell. If the cell is empty (`' '`), it puts the player's symbol there and returns `True`; otherwise it returns `False`: the move is not allowed.دەپشکنێت ئایا یاریزانەکە دەتوانێت بچێتە خانەیەکەوە. ئەگەر خانەکە بەتاڵ بێت (`' '`)، نیشانەی یاریزانەکە تێیدا دادەنێت و `True` دەگەڕێنێتەوە؛ ئەگەرنا `False` دەگەڕێنێتەوە: جووڵەکە ڕێگەپێدراو نییە.
`is_player_won`	Checks all rows, columns and both diagonals. If one of them is full of the player's symbol, it returns `True` (the player has won), otherwise `False`.هەموو ڕیز، ستوون و هەردوو هێڵە لارەکە دەپشکنێت. ئەگەر یەکێکیان پڕ بێت لە نیشانەی یاریزانەکە، `True` دەگەڕێنێتەوە (یاریزانەکە بردوویەتییەوە)، ئەگەرنا `False`.
`check_draw`	Returns `True` if the board is full and nobody has won (a draw), otherwise `False`.ئەگەر تەختەکە پڕ بێت و کەس نەیبردبێتەوە (یەکسانبوون) `True` دەگەڕێنێتەوە، ئەگەرنا `False`.
`evaluate_board`	Gives the board a score: positive if x (the AI) has won, negative if o has won, and 0 for a draw or an unfinished game. The AI uses this number every time it decides on the best move. دەدات بە تەختەکە: موجەب ئەگەر x () بردبێتیەوە، سالب ئەگەر o بردبێتیەوە و 0 بۆ یەکسانبوون یان یارییەکی تەواونەبوو. هەموو جارێک ئەم ژمارەیە بەکار دەهێنێت بۆ بڕیاردان لەسەر باشترین جووڵە.
`alpha_beta`	Checks the future moves and rates them with `evaluate_board`. On the AI's turn it raises the score (maximizes: the best move for x); on the player's turn it lowers the score (minimizes: the best move for o, maybe you). It cuts branches when α ≥ β.جووڵەکانی داهاتوو دەپشکنێت و بە `evaluate_board` هەڵیاندەسەنگێنێت. لە سەرەی نمرەکە بەرز دەکاتەوە (Maximize: باشترین جووڵە بۆ x)؛ لە سەرەی یاریزانەکەدا نمرەکە نزم دەکاتەوە (Minimize: باشترین جووڵە بۆ o، کە ڕەنگە تۆ بیت). کاتێک α ≥ β بوو، لقەکان دەبڕێت.
`find_best_move`	As the name says, finds the best move for the AI by calling `alpha_beta` for every empty cell.وەک لە ناوەکەیدا دیارە، باشترین جووڵە بۆ دەدۆزێتەوە بە بانگکردنی `alpha_beta` بۆ هەر خانەیەکی بەتاڵ.
`main`	Starts the game, runs the loop and gives each player their turn. On every turn it prints the board and checks whether someone has won. If a player (especially you, the human) makes a wrong move, it asks again. The game goes on until there is a winner or a draw.یارییەکە دەست پێدەکات، بەڕێوە دەبات و سەرەی هەردوو یاریزان دیاری دەکات. لە هەر سەرەیەکدا تەختەکە چاپ دەکات و دەپشکنێت کە داخۆ کەس بردوویەتییەوە. ئەگەر یاریزانێک (بەتایبەت تۆی مرۆڤ) جووڵەیەکی هەڵە بکات، دووبارە داوای جووڵە دەکاتەوە. یارییەکە بەردەوام دەبێت تا براوەیەک یان یەکسانبوونێک هەبێت.

On the next three screens you see the corrected program in three parts. Put the three parts one after another in one file, tictactoe_alphabeta.py. The board functions are explained in the tic-tac-toe lesson; here we focus on the search.

لە سێ شاشەی داهاتوودا بەرنامە چاککراوەکە لە سێ بەشدا دەبینیت. سێ بەشەکە یەک لە دوای یەک لە یەک دابنێ، tictactoe_alphabeta.py. تەختە لە وانەی یاریی ئێکس‌وئۆ ڕوون کراونەتەوە؛ لێرەدا سەرنج دەخەینە سەر گەڕانەکە.

The tic-tac-toe program, function by functionبەرنامەی یاریی ئێکس‌وئۆ، کردار بە کردار

Part 1: the boardبەشی ١: تەختەکە

Part 1 of 3: board, moves, winner and scoreبەشی ١ لە ٣: تەختە، جووڵە، براوە و نمرەtictactoe_alphabeta.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

# Tic-tac-toe against an AI that uses minimax with alpha-beta pruning.
# AI    plays 'x' = the maximizing player
# Human plays 'o' = the minimizing player

board = [
    [' ', ' ', ' '],
    [' ', ' ', ' '],
    [' ', ' ', ' '],
]


def print_board(board):
    for i, row in enumerate(board):
        print("   |".join(row))
        if i < 2:
            print("-" * 15)
    print()


def can_move(board, row, col, player):
    if board[row][col] == ' ':
        board[row][col] = player
        return True
    return False


def is_player_won(board, player):
    for row in board:
        if all(cell == player for cell in row):
            return True
    for col in range(3):
        if all(board[row][col] == player for row in range(3)):
            return True
    if all(board[i][i] == player for i in range(3)):
        return True
    if all(board[i][2 - i] == player for i in range(3)):
        return True
    return False


def check_draw(board):
    full = all(cell != ' ' for row in board for cell in row)
    return full and not is_player_won(board, 'x') and not is_player_won(board, 'o')


def evaluate_board(board, depth):
    # x wins: positive, o wins: negative, draw: 0.
    # A win after fewer moves (smaller depth) is worth more.
    if is_player_won(board, 'x'):
        return 10 - depth
    if is_player_won(board, 'o'):
        return depth - 10
    return 0


def empty_cells(board):
    return [(row, col) for row in range(3) for col in range(3)
            if board[row][col] == ' ']

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2-3

x is the AI (MAX), o is the human (MIN).

x ⁦(MAX)⁩ و o مرۆڤەکەیە ⁦(MIN)⁩.

Lineدێڕی 28-33

all() is True when every cell in the row or column holds the player's symbol.

all() کاتێک Trueـە کە هەموو خانەکانی ڕیزەکە یان ستوونەکە نیشانەی یاریزانەکەیان تێدا بێت.

Lineدێڕی 46-53

The score. A win after fewer moves (smaller depth) is worth more, so the AI prefers the fastest win and the slowest loss.

. بردنەوە دوای جووڵەی کەمتر (depthی بچووکتر) نرخی زیاترە، بۆیە خێراترین بردنەوە و درەنگترین دۆڕانی پێ باشترە.

Lineدێڕی 56-58

All empty cells in one list, row by row. The search loops over this list once.

هەموو خانە بەتاڵەکان لە یەک ، ڕیز بە ڕیز. گەڕانەکە یەکجار بەسەر ئەم دەخولێتەوە.

The unused depthdepthـی بەکارنەهاتوو

The course's alpha_beta receives a depth parameter, adds 1 to it at every level, but never uses it. Its evaluate_board gives every win +1, however far away it is, so the AI sometimes plays a slower win when it could win at once. Here depth is finally used: a win is worth 10 - depth. Checked on all 2,423 positions: whenever an immediate win exists, this program takes it. (The minimax lesson explains these depth-aware scores; the same convention is used here: the AI's move is depth 1, so winning at once is worth 9.)

alpha_betaـی کۆرسەکە بە ناوی depth وەردەگرێت و لە هەر ئاستێکدا 1ـی بۆ زیاد دەکات، بەڵام هەرگیز بەکاری ناهێنێت. evaluate_boardـەکەی بە هەر بردنەوەیەک ⁦+1⁩ دەدات، هەرچەندە دوور بێت، بۆیە هەندێک جار بردنەوەیەکی خاوتر هەڵدەبژێرێت لە کاتێکدا دەتوانێت دەستبەجێ بیباتەوە. لێرەدا depth بەکار هاتووە: بردنەوە نرخەکەی 10 - depthـە. لەسەر هەموو ⁦2,423⁩ پێگەکە تاقی کرایەوە: هەر کاتێک بردنەوەی دەستبەجێ هەبێت، ئەم بەرنامەیە دەیباتەوە. (وانەی Minimax ئەم نمرانەی بەپێی قووڵایی ڕوون دەکاتەوە؛ لێرەش هەمان ڕێسا بەکار هاتووە: جووڵەی قووڵایی 1ـە، بۆیە بردنەوەی دەستبەجێ نرخەکەی 9ـە.)

The tic-tac-toe program, function by functionبەرنامەی یاریی ئێکس‌وئۆ، کردار بە کردار

Part 2: the search with alpha-betaبەشی ٢: گەڕان بە ئەلفا-بێتا

Part 2 of 3: alpha_beta and find_best_moveبەشی ٢ لە ٣: ⁦alpha_beta⁩ و ⁦find_best_move⁩tictactoe_alphabeta.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

count = [0]  # positions examined by alpha_beta


def alpha_beta(board, depth, alpha, beta, is_maximizing_player):
    count[0] += 1
    if is_player_won(board, 'x') or is_player_won(board, 'o') or check_draw(board):
        return evaluate_board(board, depth)

    if is_maximizing_player:
        best_score = -float('inf')
        for row, col in empty_cells(board):
            board[row][col] = 'x'
            score = alpha_beta(board, depth + 1, alpha, beta, False)
            board[row][col] = ' '
            best_score = max(best_score, score)
            alpha = max(alpha, best_score)
            if beta <= alpha:
                break  # Beta cut-off: leaves the ONLY loop
        return best_score
    else:
        best_score = float('inf')
        for row, col in empty_cells(board):
            board[row][col] = 'o'
            score = alpha_beta(board, depth + 1, alpha, beta, True)
            board[row][col] = ' '
            best_score = min(best_score, score)
            beta = min(beta, best_score)
            if beta <= alpha:
                break  # Alpha cut-off
        return best_score


def find_best_move(board):
    best_move = None
    best_score = -float('inf')
    alpha = -float('inf')
    beta = float('inf')
    for row, col in empty_cells(board):
        board[row][col] = 'x'
        score = alpha_beta(board, 1, alpha, beta, False)  # x's move = depth 1
        board[row][col] = ' '
        if score > best_score:
            best_score = score
            best_move = (row, col)
        alpha = max(alpha, best_score)
    return best_move

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1

A one-item list used as a counter that the functions can change: how many positions were examined.

بە یەک بڕگە کە وەک بەکار دێت و دەتوانن بیگۆڕن: چەند پێگە پشکنران.

Lineدێڕی 6-7

A finished game (win, loss or draw): return its score.

یارییەکی تەواوبوو (بردنەوە، دۆڕان یان یەکسانبوون): نمرەکەی بگەڕێنەرەوە.

Lineدێڕی 11-14

Try a move, score it with a recursive call, then undo the move.

جووڵەیەک تاقی بکەرەوە، بە هەڵیبسەنگێنە و پاشان جووڵەکە هەڵبوەشێنەرەوە.

Lineدێڕی 15-18

MAX raises α. If β ≤ α, break leaves the only loop: all remaining moves are skipped.

MAX α بەرز دەکاتەوە. ئەگەر β ≤ α بوو، break لە تاکە دەردەچێت: هەموو جووڵەکانی ماوە پشتگوێ دەخرێن.

Lineدێڕی 26-29

MIN lowers β and cuts in the same way.

MIN β نزم دەکاتەوە و بە هەمان شێوە دەبڕێت.

Lineدێڕی 33-46

The top level: score every empty cell for x (its move is depth 1) and keep the best. α is raised here too, so later moves can be cut sooner.

ئاستی سەرەوە: هەموو خانەیەکی بەتاڵ بۆ x هەڵبسەنگێنە (جووڵەکەی قووڵایی 1ـە) و باشترینیان ڕابگرە. α لێرەشدا بەرز دەکرێتەوە، بۆیە جووڵەکانی دواتر زووتر دەبڕدرێن.

Quick checkپشکنینی خێراIn alpha_beta, why is the move undone (board[row][col] = ' ') before the cut test?لە alpha_betaدا، بۆچی جووڵەکە پێش پشکنینی بڕین هەڵدەوەشێنرێتەوە (board[row][col] = ' ')؟To make the program print the boardبۆ ئەوەی بەرنامەکە تەختەکە چاپ بکاتSo that break leaves a clean board behindبۆ ئەوەی break تەختەیەکی پاک بەجێ بهێڵێتIt does not matter where it isگرنگ نییە لە کوێ بێتBecause Python needs it before max()چونکە Python پێش max() پێویستی پێیەتی

The tic-tac-toe program, function by functionبەرنامەی یاریی ئێکس‌وئۆ، کردار بە کردار

Part 3: playing the gameبەشی ٣: یاریکردن

Part 3 of 3: reading moves and the game loopبەشی ٣ لە ٣: خوێندنەوەی جووڵە و خولی یاریtictactoe_alphabeta.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def read_move(board, player):
    while True:
        parts = input(f"Player {player}, enter your move (row col): ").split()
        if len(parts) != 2:
            print("Type two numbers, for example: 1 2")
            continue
        try:
            row, col = int(parts[0]), int(parts[1])
        except ValueError:
            print("Only whole numbers, please.")
            continue
        if not (0 <= row <= 2 and 0 <= col <= 2):
            print("Row and column must be 0, 1 or 2.")
        elif board[row][col] != ' ':
            print("That cell is taken. Try again.")
        else:
            return row, col


def main():
    player = 'x'
    while True:
        print_board(board)
        if player == 'x':
            print("AI's turn:")
            count[0] = 0
            row, col = find_best_move(board)
            print(f"AI plays {row} {col} (positions examined: {count[0]})")
        else:
            row, col = read_move(board, player)
        can_move(board, row, col, player)

        if is_player_won(board, player):
            print_board(board)
            print(f"Player {player} wins!")
            break
        if check_draw(board):
            print_board(board)
            print("It's a draw!")
            break
        player = 'o' if player == 'x' else 'x'


if __name__ == "__main__":
    main()

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 1-17

Safe input, as in the tic-tac-toe lesson: exactly two whole numbers from 0 to 2, and only an empty cell. Letters, 3 3 or -1 -1 no longer crash or break the game.

پارێزراو، وەک لە وانەی یاریی ئێکس‌وئۆدا: ڕێک دوو لە 0 تا 2 و تەنیا خانەیەکی بەتاڵ. پیت، 3 3 یان -1 -1 چیتر یارییەکە تێک نادەن.

Lineدێڕی 26-28

The counter is reset before the AI thinks, and printed with a label after its move.

پێش بیرکردنەوەی سفر دەکرێتەوە و دوای جووڵەکەی بە ناونیشانێکەوە چاپ دەکرێت.

Correctionڕاستکردنەوە

The course's main reads a move with map(int, input().split()), so letters or a single number crash the program, 3 3 crashes with IndexError, and -1 -1 is silently accepted. The tic-tac-toe lesson explains these three bugs; read_move above is that lesson's fix plus a check for a taken cell. The course's program also printed the counter after every move, so after the human's move it printed a meaningless 0. Both problems are fixed above.

mainـی کۆرسەکە جووڵە بە map(int, input().split()) دەخوێنێتەوە، بۆیە پیت یان یەک ژمارە بەرنامەکە دەشکێنن، 3 3 بە IndexError دەشکێت و -1 -1 بە بێدەنگی وەردەگیرێت. وانەی یاریی ئێکس‌وئۆ ئەم سێ هەڵەیە ڕوون دەکاتەوە؛ read_moveـی سەرەوە چاککردنەکەی ئەو وانەیەیە لەگەڵ پشکنینی خانەی گیراو. بەرنامەکەی کۆرسەکە دوای هەموو جووڵەیەک چاپ دەکرد، بۆیە دوای جووڵەی مرۆڤەکە 0ـێکی بێواتای چاپ دەکرد. هەردوو کێشەکە لە سەرەوە چاک کراون.

The hidden bug: a break that cuts too littleهەڵە شاراوەکە: `break`ێک کە کەم دەبڕێت

The course's program gives the right moves, but it does not prune as much as it should. Look at its MAX part:

بەرنامەکەی کۆرسەکە جووڵەی دروست دەدات، بەڵام ئەوەندەی پێویستە نابڕێت. سەیری بەشی MAXـەکەی بکە:

The course's version (excerpt)وەشانەکەی کۆرسەکە (بەشێک)MinmaxAlphaBetaPruning.pyPYTHON

def alpha_beta(board, depth, alpha, beta, is_maximizing_player):
    count[0] += 1
    if is_player_won(board, 'x') or is_player_won(board, 'o') or check_draw(board):
        return evaluate_board(board)

    if is_maximizing_player:
        best_score = -float('inf')
        for row in range(3):
            for col in range(3):
                if board[row][col] == ' ':
                    board[row][col] = 'x'
                    score = alpha_beta(board, depth + 1, alpha, beta, False)
                    board[row][col] = ' '
                    best_score = max(best_score, score)
                    alpha = max(alpha, best_score)
                    if beta <= alpha:
                        break  # Beta cut-off
        return best_score
    else:
        ...  # the MIN part has the same two loops and the same break

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 8-9

Two nested loops: rows, then columns.

دوو : ڕیزەکان، پاشان ستوونەکان.

Lineدێڕی 16-17

break leaves only the inner for col loop. The outer for row loop goes on with the next row, so moves that should be cut are still searched.

break تەنیا لە ناوەوەی for col دەردەچێت. دەرەوەی for row بە ڕیزی داهاتوو بەردەوام دەبێت، بۆیە ئەو جووڵانەی دەبوو ببڕدرێن هێشتا دەپشکنرێن.

The break leaves only the inner loopbreak تەنیا لە خولی ناوەوە دەردەچێت

This is a real bug in the course's code: the cut-off break leaves only the inner loop. The moves are still correct (a missed cut only costs time), but the search is much slower than real alpha-beta. Two ways to fix it: (1) write return best_score instead of break: return leaves both loops and the function; or (2) put all empty cells in one list and loop over it once, as empty_cells does in our version. Then break leaves the only loop.

ئەمە هەڵەیەکی ڕاستەقینەیە لە کۆدی کۆرسەکەدا: breakـی بڕین تەنیا لە ناوەوە دەردەچێت. جووڵەکان هێشتا دروستن (بڕینێکی لەدەستچوو تەنیا کات دەبات)، بەڵام گەڕانەکە زۆر لە ئەلفا-بێتای ڕاستەقینە خاوترە. دوو ڕێگە بۆ چاککردنی: (١) لە جیاتی break بنووسە return best_score: return لە هەردوو و لە دەردەچێت؛ یان (٢) هەموو خانە بەتاڵەکان لە یەک دابنێ و یەکجار بەسەریدا بخولێوە، وەک empty_cells لە وەشانەکەی ئێمەدا دەیکات. ئەوکات break لە تاکە دەردەچێت.

How much does the bug cost? We played the same game with three programs (the human typed the same moves: the first free cell of 1 1, 0 0, 0 1, 0 2, 1 0, 1 2, 2 0, 2 1, 2 2). Each program prints how many positions it examined before each AI move:

ئەم هەڵەیە چەند دەکات؟ هەمان یاریمان بە سێ بەرنامە کرد (مرۆڤەکە هەمان جووڵەکانی نووسی: یەکەم خانەی بەتاڵ لە ⁦1 1⁩، ⁦0 0⁩، ⁦0 1⁩، ⁦0 2⁩، ⁦1 0⁩، ⁦1 2⁩، ⁦2 0⁩، ⁦2 1⁩، ⁦2 2⁩). هەر بەرنامەیەک پێش هەر جووڵەیەکی چاپ دەکات کە چەند پێگەی پشکنیوە:

Positions examined before each AI move (our runs with python3)ئەو پێگانەی پێش هەر جووڵەیەکی پشکنران (جێبەجێکردنی خۆمان بە ⁦python3⁩)
AI moveجووڵەی	Minimax (course) (کۆرسەکە)	Alpha-beta, course's breakئەلفا-بێتا، `break`ـی کۆرسەکە	Alpha-beta, break fixedئەلفا-بێتا، `break` چاککراو
1st (empty board)یەکەم (تەختەی بەتاڵ)	549,945	48,382	18,296
2ndدووەم	7,331	1,916	843
3rdسێیەم	197	86	63
4thچوارەم	13	13	9
Resultئەنجام	draw, same movesیەکسان، هەمان جووڵە	draw, same movesیەکسان، هەمان جووڵە	draw, same movesیەکسان، هەمان جووڵە

On the first move, the course's alpha-beta already saves a lot (48,382 instead of 549,945, about 11 times fewer), but with the cut fixed it examines only 18,296: 30 times fewer than minimax. Our final program, which also uses depth in the score, examines 20,865 positions on the first move (scores that differ more cut a little less), and it still chooses the same moves as a minimax with the same scores.

لە جووڵەی یەکەمدا، ئەلفا-بێتای کۆرسەکە پێشتریش کاتێکی زۆر پاشەکەوت دەکات (⁦48,382⁩ لە جیاتی ⁦549,945⁩، نزیکەی ⁦11⁩ جار کەمتر)، بەڵام کاتێک بڕینەکە چاک دەکرێت تەنیا ⁦18,296⁩ دەپشکنێت: ⁦30⁩ جار کەمتر لە . بەرنامە کۆتاییەکەی ئێمە، کە depthـیش لە نمرەکەدا بەکار دەهێنێت، لە جووڵەی یەکەمدا ⁦20,865⁩ پێگە دەپشکنێت (نمرەی جیاوازتر کەمێک کەمتر دەبڕێت) و هێشتا هەمان جووڵەکانی هەڵدەبژێرێت کە هەمان نمرەی هەبێت.

Quick checkپشکنینی خێراWhy did the course's program still play the right moves, even with the wrong break?بۆچی بەرنامەکەی کۆرسەکە هێشتا جووڵەی دروستی دەکرد، تەنانەت بە breakـە هەڵەکەشەوە؟Because a missed cut only means extra work, not a wrong valueچونکە بڕینێکی لەدەستچوو تەنیا واتای کاری زیاترە، نەک نرخێکی هەڵەBecause the human played badlyچونکە مرۆڤەکە خراپ یاری کردBecause break is ignored by Pythonچونکە Python break پشتگوێ دەخاتBecause tic-tac-toe is always a drawچونکە یاریی ئێکس‌وئۆ هەمیشە یەکسانە

Does alpha-beta stop at a winning move?ئایا ئەلفا-بێتا لە جووڵەیەکی براوەدا دەوەستێت؟

The article compares the two algorithms in a game against the computer. The computer looks at its next move and finds a move that wins at once. With minimax, it still looks at all the other moves and possibilities before it decides. With alpha-beta, says the article, it "stops immediately and picks the winning move without looking at the other moves".

وتارەکە دوو لە یارییەک لەگەڵ کۆمپیوتەردا بەراورد دەکات. کۆمپیوتەر سەیری جووڵەی داهاتووی دەکات و جووڵەیەک دەدۆزێتەوە کە ڕاستەوخۆ دەیباتەوە. ئەگەر بەکار هێنرابێت، پێش دوابڕیار هێشتا سەیری هەموو جووڵە و ئەگەرەکانی دیکە دەکات. ئەگەر ئەلفا-بێتا بەکار هێنرابێت، وتارەکە دەڵێت «دەستبەجێ ڕادەوەستێت و ئەو جووڵەیە هەڵدەبژێرێت کە دەیباتەوە بەبێ ئەوەی سەیری جووڵەکانی دیکە بکات».

It still checks the other moves, but cheaplyهێشتا جووڵەکانی دیکە دەپشکنێت، بەڵام بە هەرزانی

Plain alpha-beta does not know that a win is the best possible score, so at the top level it still scores every move. You can see this in the course's program (48,382 positions before the first move) and in our game above: before its winning move 0 2, the AI examined 9 positions. It did find the win first, but then it still checked the other 4 empty cells; each of them was cut after one reply (1 + 4 × 2 = 9). To make the article's sentence true, give the program one more fact: nothing beats winning now. Exercise 3 below does exactly that, and the count falls to 1.

ئەلفا-بێتای سادە نازانێت کە بردنەوە باشترین نمرەی گونجاوە، بۆیە لە ئاستی سەرەوەدا هێشتا هەموو جووڵەیەک هەڵدەسەنگێنێت. ئەمە لە بەرنامەکەی کۆرسەکەدا دەبینیت (پێش یەکەم جووڵە ⁦48,382⁩ پێگە) و لە یارییەکەی سەرەوەی ئێمەشدا: پێش جووڵە براوەکەی ⁦0 2⁩، 9 پێگەی پشکنی. یەکەمجار بردنەوەکەی دۆزییەوە، بەڵام پاشان هێشتا 4 خانە بەتاڵەکەی دیکەی پشکنی؛ هەریەکەیان دوای یەک وەڵام بڕدرا ⁦(1 + 4 × 2 = 9)⁩. بۆ ئەوەی ڕستەکەی وتارەکە ڕاست بێت، ڕاستییەکی دیکە بدە بە بەرنامەکە: هیچ شتێک لە بردنەوەی ئێستا باشتر نییە. ڕاهێنانی ٣ی خوارەوە ڕێک ئەمە دەکات و ژمارەکە دادەبەزێت بۆ 1.

Quick checkپشکنینی خێراThe AI finds a winning move first. With plain alpha-beta (no extra rule), what happens to the other moves at the top level? یەکەمجار جووڵەیەکی براوە دەدۆزێتەوە. بە ئەلفا-بێتای سادە (بێ یاسای زیادە)، چی بەسەر جووڵەکانی دیکەی ئاستی سەرەوەدا دێت؟They are still scored, but each is cut quicklyهێشتا هەڵدەسەنگێنرێن، بەڵام هەریەکەیان خێرا دەبڕدرێتThey are searched completely, as in minimaxبە تەواوی دەپشکنرێن، وەک MinimaxThey are never looked atهەرگیز سەیریان ناکرێتThe AI chooses one of them insteadژیریی دەستکرد لە جیاتی ئەوە یەکێکیان هەڵدەبژێرێت

Good move order means more cutsڕیزبەندیی باشی جووڵەکان واتە بڕینی زیاتر

Alpha-beta cuts more when it tries the best moves first: a good α (or β) is found early, and later moves are cut sooner. In tic-tac-toe the centre and the corners are usually the strongest cells. This small program, run next to tictactoe_alphabeta.py, changes only the order of the empty cells and counts the positions for the first move:

ئەلفا-بێتا کاتێک باشترین جووڵەکان یەکەمجار تاقی دەکاتەوە زیاتر دەبڕێت: زوو نرخێکی باش بۆ α (یان β) دەدۆزرێتەوە و جووڵەکانی دواتر زووتر دەبڕدرێن. لە ناوەڕاست و گۆشەکان زۆرجار بەهێزترین خانەن. ئەم بەرنامە بچووکە، لە تەنیشت tictactoe_alphabeta.py، تەنیا ڕیزبەندیی خانە بەتاڵەکان دەگۆڕێت و پێگەکانی جووڵەی یەکەم دەژمێرێت:

move_order.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

# Does the order of the moves change how much alpha-beta can cut?
# Run this file next to tictactoe_alphabeta.py.
import tictactoe_alphabeta as game

ORDER = [(1, 1),                          # centre first
         (0, 0), (0, 2), (2, 0), (2, 2),  # then the corners
         (0, 1), (1, 0), (1, 2), (2, 1)]  # then the edges


def centre_first(board):
    return [cell for cell in ORDER if board[cell[0]][cell[1]] == ' ']


empty = [[' '] * 3 for _ in range(3)]

game.count[0] = 0
move = game.find_best_move(empty)
print("row by row:   ", move, game.count[0], "positions")

game.empty_cells = centre_first          # use the new order everywhere
game.count[0] = 0
move = game.find_best_move(empty)
print("centre first: ", move, game.count[0], "positions")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 5-7

Centre first, then the corners, then the edges.

یەکەمجار ناوەڕاست، پاشان گۆشەکان، پاشان لێوارەکان.

Lineدێڕی 20

Replace empty_cells in the game module: alpha_beta now uses the new order everywhere.

empty_cells لە یارییەکەدا دەگۆڕین: alpha_beta ئێستا لە هەموو شوێنێک ڕیزبەندییە نوێیەکە بەکار دەهێنێت.

The same search, the same scores, but about 2.7 times fewer positions. The chosen first move changed to the centre because, with perfect play, every first move leads to a draw: the AI keeps the first best move it finds. With perfect ordering, alpha-beta examines about b^(m/2) positions instead of minimax's b^m (b moves per position, m moves deep), so in the same time it can look about twice as deep.

هەمان گەڕان و هەمان نمرە، بەڵام نزیکەی ⁦2.7⁩ جار پێگەی کەمتر. یەکەم جووڵەی هەڵبژێردراو گۆڕا بۆ ناوەڕاست، چونکە بە یاریکردنی بێ هەڵە هەموو جووڵەیەکی یەکەم بەرەو یەکسانبوون دەڕوات: یەکەم باشترین جووڵە دەهێڵێتەوە کە دەیدۆزێتەوە. بە ڕیزبەندییەکی تەواو، ئەلفا-بێتا نزیکەی b^⁦(m/2)⁩ پێگە دەپشکنێت لە جیاتی b^mـی (b جووڵە لە هەر پێگەیەکدا، m جووڵە قووڵ)، بۆیە لە هەمان کاتدا دەتوانێت نزیکەی دوو هێندە قووڵتر سەیر بکات.

Common mistakesهەڵە باوەکان

Mistakeهەڵە	What goes wrongچی تێک دەچێت	Fixچاککردن
`break` inside two nested loops`break` لەناو دوو	Only the inner loop stops; branches that should be cut are still searched.تەنیا ناوەوە دەوەستێت؛ ئەو لقانەی دەبوو ببڕدرێن هێشتا دەپشکنرێن.	`return best_score`, or one loop over a list of moves.`return best_score`، یان یەک بەسەر جووڵەدا.
Starting α and β again at −∞ and +∞ in every callدانانەوەی α و β بە −∞ و +∞ لە هەموو بانگکردنێکدا	The bounds from above are lost, so almost nothing is cut.سنوورەکانی سەرەوە لەدەست دەچن، بۆیە نزیکەی هیچ شتێک نابڕدرێت.	Pass the current α and β down as arguments.α و βـی ئێستا وەک بنێرە بۆ خوارەوە.
Changing α at MIN's turn or β at MAX's turnگۆڕینی α لە سەرەی MIN یان β لە سەرەی MAXدا	Wrong cuts and wrong moves.بڕینی هەڵە و جووڵەی هەڵە.	MAX updates only α; MIN updates only β.MAX تەنیا α نوێ دەکاتەوە؛ MIN تەنیا β.
Leaving the loop before undoing the moveدەرچوون لە پێش هەڵوەشاندنەوەی جووڵەکە	A stray 'x' or 'o' stays on the shared board.'x' یان 'o'یەکی زیادە لەسەر تەختە هاوبەشەکە دەمێنێتەوە.	Undo first, then test `beta <= alpha`.یەکەمجار هەڵیبوەشێنەرەوە، پاشان `beta <= alpha` بپشکنە.
Thinking α is the AI and β the humanوا بزانیت α و β مرۆڤەکە	You cannot follow the algorithm.ناتوانیت لە تێبگەیت.	α and β are guaranteed scores carried down the tree.α و β نمرەی گەرەنتیکراون کە بەرەو خوارەوەی دەبردرێن.
Expecting a better move than minimaxچاوەڕوانیی جووڵەیەکی باشتر لە	Alpha-beta never changes the decision.ئەلفا-بێتا هەرگیز بڕیارەکە ناگۆڕێت.	Use it to search faster or deeper, not differently.بۆ گەڕانی خێراتر یان قووڵتر بەکاری بهێنە، نەک جیاواز.

Exercisesڕاهێنانەکان

Exerciseڕاهێنان1. Prune by hand١. بە دەست ببڕە

MAX has three moves A, B and C; MIN has three replies after each. The leaves are A: 6, 3, 9; B: 8, 1, 4; C: 7, 7, 2. Run alpha-beta from left to right. What is the root's value, which move does MAX choose, and which leaves are never looked at? Then change C to 2, 7, 7: what changes?

MAX سێ جووڵەی هەیە A، B و C؛ MIN دوای هەر یەکێکیان سێ وەڵامی هەیە. ئەمانەن ⁦A: 6⁩، 3، 9؛ ⁦B: 8⁩، 1، 4؛ ⁦C: 7⁩، 7، 2. ئەلفا-بێتا لە چەپەوە بۆ ڕاست جێبەجێ بکە. نرخی چەندە، MAX کام جووڵە هەڵدەبژێرێت و سەیری کام هەرگیز ناکرێت؟ پاشان C بکە بە 2، 7، 7: چی دەگۆڕێت؟

Hintئاماژە

Write α and β next to each node as you go. Cut as soon as α ≥ β.

لە کاتی ڕۆیشتندا α و β لە تەنیشت هەر نۆدێک بنووسە. هەر کە α ≥ β بوو، ببڕە.

Show answerوەڵامەکە پیشان بدە

A = min(6, 3, 9) = 3, so α = 3. In B, 8 gives β = 8, then 1 gives β = 1 ≤ 3: cut, the leaf 4 is skipped. In C, 7, 7 and 2 give β = 2; the cut test is true only at the last leaf, so nothing is left to skip. The root is max(3, ≤1, 2) = 3: MAX plays A, after looking at 8 of the 9 leaves. With C = 2, 7, 7 the first leaf already gives β = 2 ≤ 3, so both 7s are skipped: only 6 leaves. The order of the moves decides how much is cut.

⁦A = min(6, 3, 9) = 3⁩، بۆیە α = 3. لە Bدا، 8 β = 8 دەدات، پاشان 1 β = ⁦1 ≤ 3⁩ دەدات: بڕین، 4 پشتگوێ دەخرێت. لە Cدا، 7، 7 و 2 β = 2 دەدەن؛ پشکنینی بڕین تەنیا لە دوایین ڕاستە، بۆیە هیچ شتێک نەماوە بۆ پشتگوێخستن. نرخی ⁦max(3, ≤1, 2) = 3⁩ـە: MAX جووڵەی A دەکات، دوای سەیرکردنی 8 لە 9 . بە ⁦C = 2⁩، 7، 7 یەکەم دەستبەجێ β = ⁦2 ≤ 3⁩ دەدات، بۆیە هەردوو 7ـەکە پشتگوێ دەخرێن: تەنیا 6 . ڕیزبەندیی جووڵەکان بڕیار دەدات چەند دەبڕدرێت.

Check it: change the tree in small_tree.pyبیپشکنە: دارەکە لە ⁦small_tree.py⁩ بگۆڕەsmall_tree.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

tree = [[6, 3, 9],   # move A
        [8, 1, 4],   # move B
        [7, 7, 2]]   # move C

With C = 2, 7, 7بە ⁦C = 2⁩، 7، 7small_tree.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

tree = [[6, 3, 9],   # move A
        [8, 1, 4],   # move B
        [2, 7, 7]]   # move C

Exerciseڕاهێنان2. Fix the course's break٢. breakـی کۆرسەکە چاک بکە

Take the course's program MinmaxAlphaBetaPruning.py and change only the two cut-off lines so that the cut leaves both loops. Play the same game as in the table (first free cell of 1 1, 0 0, 0 1, …). What numbers does the program print now?

بەرنامەی MinmaxAlphaBetaPruning.pyـی کۆرسەکە وەربگرە و تەنیا دوو دێڕەکەی بڕین بگۆڕە بۆ ئەوەی بڕینەکە لە هەردوو دەربچێت. هەمان یاریی ناو خشتەکە بکە (یەکەم خانەی بەتاڵ لە ⁦1 1⁩، ⁦0 0⁩، ⁦0 1⁩، …). بەرنامەکە ئێستا چ ژمارانێک چاپ دەکات؟

Hintئاماژە

break leaves one loop; return leaves the whole function.

break لە یەک دەردەچێت؛ return لە هەموو دەردەچێت.

Show answerوەڵامەکە پیشان بدە

Replace break with return best_score (twice)break بگۆڕە بە return best_score (دوو جار)MinmaxAlphaBetaPruning.pyPYTHON

                    if beta <= alpha:
                        return best_score  # Beta cut-off
...
                    if beta <= alpha:
                        return best_score  # Alpha cut-off

The numbers it prints (the boards are not shown)ئەو ژمارانەی چاپی دەکات (تەختەکان پیشان نەدراون)

18296
0
843
0
63
0
9
0
It's a draw!

Instead of 48382, 1916, 86 and 13. The 0 after each human move is the meaningless counter of the course's main (see Part 3). Same moves, same draw.

لە جیاتی ⁦48382⁩، ⁦1916⁩، ⁦86⁩ و ⁦13⁩. ئەو 0ـەی دوای هەر جووڵەیەکی مرۆڤ دێت بێواتاکەی mainـی کۆرسەکەیە (بڕوانە بەشی ٣). هەمان جووڵە و هەمان یەکسانبوون.

The same fix in our program (depth scores)هەمان چاککردن لە بەرنامەکەی ئێمەدا (نمرەی بەپێی قووڵایی)return_fix.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

# The other fix: keep the two loops, but RETURN at a cut-off.
import tictactoe_alphabeta as game
from tictactoe_alphabeta import is_player_won, check_draw, evaluate_board, count


def alpha_beta(board, depth, alpha, beta, is_maximizing_player):
    count[0] += 1
    if is_player_won(board, 'x') or is_player_won(board, 'o') or check_draw(board):
        return evaluate_board(board, depth)

    if is_maximizing_player:
        best_score = -float('inf')
        for row in range(3):
            for col in range(3):
                if board[row][col] == ' ':
                    board[row][col] = 'x'
                    score = alpha_beta(board, depth + 1, alpha, beta, False)
                    board[row][col] = ' '
                    best_score = max(best_score, score)
                    alpha = max(alpha, best_score)
                    if beta <= alpha:
                        return best_score  # leaves BOTH loops
        return best_score
    else:
        best_score = float('inf')
        for row in range(3):
            for col in range(3):
                if board[row][col] == ' ':
                    board[row][col] = 'o'
                    score = alpha_beta(board, depth + 1, alpha, beta, True)
                    board[row][col] = ' '
                    best_score = min(best_score, score)
                    beta = min(beta, best_score)
                    if beta <= alpha:
                        return best_score  # leaves BOTH loops
        return best_score


game.alpha_beta = alpha_beta       # find_best_move now uses this version
count[0] = 0
print(game.find_best_move([[' '] * 3 for _ in range(3)]), count[0])

Exerciseڕاهێنان3. Stop at once when you can win٣. کاتێک دەتوانیت بیبەیتەوە، دەستبەجێ بوەستە

Change find_best_move so that it stops looking as soon as it finds a move that wins immediately (score 9). Play the game from Part 3 again (1 1, 5 1, 0 0, 2 0). How many positions does the AI examine before its winning move now?

find_best_move بگۆڕە بۆ ئەوەی هەر کە جووڵەیەکی دۆزییەوە کە دەستبەجێ دەیباتەوە (نمرەی ⁦9⁩)، واز لە سەیرکردن بهێنێت. یارییەکەی بەشی ٣ دووبارە بکەرەوە (⁦1 1⁩، ⁦5 1⁩، ⁦0 0⁩، ⁦2 0⁩). ئێستا پێش جووڵە براوەکەی چەند پێگە دەپشکنێت؟

Hintئاماژە

The AI's own move is depth 1, so evaluate_board(board, 1) is 9 when x has just won. No score can be higher.

جووڵەی خۆی قووڵایی 1ـە، بۆیە evaluate_board(board, 1) 9ـە کاتێک x تازە بردوویەتییەوە. هیچ نمرەیەک لەوە بەرزتر نییە.

Show answerوەڵامەکە پیشان بدە

stop_at_win.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

# Exercise answer: stop as soon as the AI finds a move that wins NOW.
import tictactoe_alphabeta as game
from tictactoe_alphabeta import alpha_beta, empty_cells

WIN_NOW = 9             # evaluate_board(board, 1): x wins with this move


def find_best_move(board):
    best_move = None
    best_score = -float('inf')
    alpha = -float('inf')
    beta = float('inf')
    for row, col in empty_cells(board):
        board[row][col] = 'x'
        score = alpha_beta(board, 1, alpha, beta, False)
        board[row][col] = ' '
        if score > best_score:
            best_score = score
            best_move = (row, col)
        alpha = max(alpha, best_score)
        if best_score == WIN_NOW:
            break       # nothing can beat winning at once
    return best_move


game.find_best_move = find_best_move
game.main()

Quick checkپشکنینی خێراWhich statement about alpha-beta pruning is true?کام ڕستە دەربارەی ڕاستە؟α starts at +∞α لە +∞ دەست پێدەکاتIt can choose a different move from minimaxدەتوانێت جووڵەیەکی جیاواز لە Minimax هەڵبژێرێتIt cuts a branch when α ≥ βکاتێک α ≥ β بوو لقێک دەبڕێتIt works only for tic-tac-toeتەنیا بۆ یاریی ئێکس‌وئۆ کار دەکات

Summary and reviewپوختە و پێداچوونەوە

Alpha-beta pruning is minimax with cuts: the same value and the same move, with far less work.
α = the best score MAX can guarantee so far (starts at −∞, only goes up); β = the best score MIN can guarantee so far (starts at +∞, only goes down).
Cut the remaining moves of a position as soon as α ≥ β (in code: beta <= alpha).
In the course's program, break left only the inner loop: 48,382 positions instead of 18,296 for the first move (minimax: 549,945). Fix it with return or one loop.
Good move order (best moves first) gives more cuts.

لەگەڵ بڕین: هەمان نرخ و هەمان جووڵە، بە کارێکی زۆر کەمتر.
α = باشترین نمرە کە MAX تا ئێستا گەرەنتی دەکات (لە −∞ دەست پێدەکات و تەنیا بەرز دەبێتەوە)؛ β = باشترین نمرە کە MIN تا ئێستا گەرەنتی دەکات (لە +∞ دەست پێدەکات و تەنیا نزم دەبێتەوە).
هەر کە α ≥ β بوو، جووڵەکانی ماوەی پێگەکە ببڕە (لە کۆددا: beta <= alpha).
لە بەرنامەکەی کۆرسەکەدا break تەنیا لە ناوەوە دەردەچوو: بۆ جووڵەی یەکەم ⁦48,382⁩ پێگە لە جیاتی ⁦18,296⁩ (: ⁦549,945⁩). بە return یان بە یەک چاکی بکە.
ڕیزبەندیی باشی جووڵەکان (باشترینەکان یەکەمجار) بڕینی زیاتر دەدات.

Review questionsپرسیارەکانی پێداچوونەوە

Why is the algorithm called "alpha-beta pruning"?بۆچی ئەلگۆریزمەکە ناوی «بڕینی ئەلفا-بێتا»ـە؟

It keeps two numbers named after the Greek letters α and β, and it prunes (cuts) branches of the game tree that are not needed.

دوو ژمارە هەڵدەگرێت کە بە ناوی پیتە گریکییەکانی α و β ناونراون و ئەو لقانەی دەبڕێت ⁦(Prune)⁩ کە پێویست نین.

Why does α start at −∞ and β at +∞?بۆچی α لە −∞ و β لە +∞ دەست پێدەکەن؟

At the start we do not know any move yet, so any real score will be better than these starting values.

لە سەرەتادا هێشتا هیچ جووڵەیەک نازانین، بۆیە هەر نمرەیەکی ڕاستەقینە لەم نرخە سەرەتاییانە باشتر دەبێت.

At MAX's position α becomes 7 while β = 5. What happens and why?لە پێگەی MAXدا α دەبێت بە 7 لە کاتێکدا β = 5ـە. چی ڕوو دەدات و بۆچی؟

A beta cut-off: the remaining moves are skipped. MIN can already keep the score at 5 or less with another move higher up, so MIN will never allow this position.

بڕینی بێتا: جووڵەکانی ماوە پشتگوێ دەخرێن. MIN پێشتر بە جووڵەیەکی دیکە لە سەرەوە دەتوانێت نمرەکە لە 5 یان کەمتردا ڕابگرێت، بۆیە MIN هەرگیز ڕێگە بەم پێگەیە نادات.

Can alpha-beta pruning make the AI play worse than minimax?ئایا بڕینی ئەلفا-بێتا دەتوانێت وا بکات ژیریی دەستکرد لە Minimax خراپتر یاری بکات؟

No. It only skips branches that cannot change the decision; the chosen move is the same (checked on all 2,423 positions).

نەخێر. تەنیا ئەو لقانە پشتگوێ دەخات کە ناتوانن بڕیارەکە بگۆڕن؛ جووڵە هەڵبژێردراوەکە هەمان شتە (لەسەر هەموو ⁦2,423⁩ پێگەکە تاقی کرایەوە).

What was wrong with break in the course's code, and how much did it cost?break لە کۆدی کۆرسەکەدا چ هەڵەیەکی تێدا بوو و چەندی تێچوو؟

It left only the inner for col loop, so the outer loop kept searching other rows. The first move examined 48,382 positions instead of 18,296.

تەنیا لە ناوەوەی for col دەردەچوو، بۆیە دەرەوە بەردەوام ڕیزەکانی دیکەی دەپشکنی. جووڵەی یەکەم ⁦48,382⁩ پێگەی پشکنی لە جیاتی ⁦18,296⁩.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Algorithms Explained – minimax and alpha-beta pruningSebastian Lague · Englishئینگلیزی · 1.4M viewsبینین · 40K likesلایک · Partبەشی 5:13–11:01 (ofلە 11:01)
Animated tree shows when alpha-beta pruning can skip branches, and how two numbers, alpha and beta, are added to the minimax code.
جووڵاو پیشان دەدات کەی دەتوانێت لقەکان بپەڕێنێت و چۆن دوو ژمارە (α و β) دەخرێنە سەر کۆدی .
Starts at 5:13 (alpha-beta concept) and runs to the end (coding alpha-beta). 0:00–5:13 is a minimax review.
لە ⁦5:13⁩ (بیرۆکەی ) دەست پێدەکات تا کۆتایی (نووسینی کۆدەکەی). بەشی ⁦0:00⁩ تا ⁦5:13⁩ پێداچوونەوەیەکە بە .

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Propositional Logic and Knowledge Basesلۆجیکی گوزارەیی و بنکەکانی زانین

Related lecturesوانە پەیوەندیدارەکان

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.

Alpha-Beta Pruningبڕینی ئەلفا-بێتا

What you will learnچی فێر دەبیت

Why minimax needs a shortcutبۆچی Minimax پێویستی بە کورتەڕێیەکە

Why it is called "alpha-beta pruning"بۆچی ناوی نراوە «بڕینی ئەلفا-بێتا»

Alpha and beta: two guaranteed scoresئەلفا و بێتا: دوو نمرەی گەرەنتیکراو

The cut rule: α ≥ βیاسای بڕین: α ≥ β

The stubborn friend and the restaurantsدۆستە کەللەڕەقەکە و چێشتخانەکان

A worked example on a small treeنموونەیەکی کارپێکراو لەسەر دارێکی بچووک

The same example in Pythonهەمان نموونە بە Python

The tic-tac-toe program, function by functionبەرنامەی یاریی ئێکس‌وئۆ، کردار بە کردار

Part 1: the boardبەشی ١: تەختەکە

Part 2: the search with alpha-betaبەشی ٢: گەڕان بە ئەلفا-بێتا

Part 3: playing the gameبەشی ٣: یاریکردن

The hidden bug: a break that cuts too littleهەڵە شاراوەکە: breakێک کە کەم دەبڕێت

Does alpha-beta stop at a winning move?ئایا ئەلفا-بێتا لە جووڵەیەکی براوەدا دەوەستێت؟

Good move order means more cutsڕیزبەندیی باشی جووڵەکان واتە بڕینی زیاتر

Common mistakesهەڵە باوەکان

Exercisesڕاهێنانەکان

Summary and reviewپوختە و پێداچوونەوە

Watch a videoسەیری ڤیدیۆیەک بکە

Lesson complete!وانەکە تەواو بوو!

Key termsزاراوە سەرەکییەکان

Related lecturesوانە پەیوەندیدارەکان

The hidden bug: a break that cuts too littleهەڵە شاراوەکە: `break`ێک کە کەم دەبڕێت