alfa Beta snoeien in AI

Alpha beta snoeien is een optimalisatie techniek voor het minimax algoritme. In de loop van deze blog zullen we bespreken wat alpha beta snoeien betekent, we zullen minimax algoritme bespreken, regels om goede bestelling te vinden, en meer.

1. Inleiding
2. Minimaxalgoritme
3. sleutelpunten in alfa-beta snoeien
4. werking van alfa-beta snoeien
5. volgorde verplaatsen in snoeien
6. regels om een goede volgorde te vinden
7. Codes in Python

Inleiding

het woord “snoeien”: het afsnijden van takken en bladeren. In data science snoeien is een veel gebruikte term die verwijst naar post en pre-snoeien in Besluit bomen en willekeurig bos. Alpha-beta snoeien is niets anders dan het snoeien van nutteloze takken in beslissingsbomen. Dit alfa-beta snoeialgoritme werd onafhankelijk ontdekt door onderzoekers in de jaren 1900.

alfa-beta snoei is een optimalisatietechniek voor het minimax-algoritme, die in de volgende sectie wordt besproken. De behoefte aan snoeien kwam voort uit het feit dat in sommige gevallen beslissingsbomen zeer complex worden. In die boom verhogen enkele nutteloze takken de complexiteit van het model. Dus, om dit te voorkomen, komt Alpha-Beta snoeien om te spelen, zodat de computer niet hoeft te kijken naar de hele boom. Deze ongewone knooppunten maken het algoritme traag. Vandaar door het verwijderen van deze knooppunten algoritme wordt snel.

meer informatie over een * – algoritme.

MiniMax algoritme

Minimax is een klassieke diepte-Eerste zoek techniek voor een sequentiële twee-speler spel. De twee spelers heten MAX en MIN. De Minimax algoritme is ontworpen voor het vinden van de optimale zet voor MAX, de speler op de root node. De zoekboom wordt gemaakt door recursief alle nodes uit te breiden vanaf de root in een diepte-eerste manier tot het einde van het spel of de maximale zoekdiepte is bereikt. Laten we dit algoritme in detail onderzoeken.

zoals reeds vermeld, zijn er twee spelers in het spel, namelijk Max en Min. Max speelt de eerste stap. Max ’s taak is om zijn beloning te maximaliseren, terwijl Min’ s taak is om Max ‘ s beloning te minimaliseren, het verhogen van zijn eigen beloning op hetzelfde moment. Stel dat Max a, b of c kan doen. Wie van hen zal Max de beste beloning geven als het spel eindigt? Om deze vraag te beantwoorden, moeten we de game tree voldoende diep verkennen en ervan uitgaan dat Min optimaal speelt om de beloning van Max te minimaliseren.

hier is een voorbeeld. Vier munten zijn op een rij en elke speler kan pick – up een munt of twee munten op zijn/haar beurt. De speler die de laatste munt pakt wint. Aangenomen dat Max als eerste speelt, welke zet moet Max maken om te winnen?

als Max twee munten kiest, blijven er slechts twee munten over en kan Min twee munten kiezen en winnen. Dus het oppakken van 1 munt zal maximaliseren beloning Max ‘ s.

zoals u misschien hebt gemerkt, hebben de knooppunten van de boom in de onderstaande figuur enkele waarden erop gegraveerd, deze worden minimaxwaarde genoemd. De minimale waarde van een knooppunt is het nut van het knooppunt als het een terminalknooppunt is.

als het knooppunt een niet-terminaal Max-knooppunt is, is de minimaxwaarde van het knooppunt het maximum van de minimaxwaarden van alle opvolgers van het knooppunt. Aan de andere kant, als het knooppunt een niet-terminaal min knooppunt is, is de minimaxwaarde van het knooppunt het minimum van de minimaxwaarden van alle opvolgers van het knooppunt.

nu bespreken we het idee achter de alpha beta snoei. Als we alpha-beta snoeien toepassen op de standaard minimax algoritme geeft het dezelfde beslissing als die van standaard algoritme, maar het snoeit of snijdt de knooppunten die ongebruikelijk zijn in besluit boom dat wil zeggen die niet van invloed zijn op de uiteindelijke beslissing van het algoritme. Dit zal helpen om de complexiteit in de interpretatie van complexe bomen te voorkomen.

zie hoe KNN-algoritme werkt.

laten we nu de intuïtie achter deze techniek bespreken. Laten we proberen om minimax beslissing te vinden in de onderstaande boom :

In dit geval,

hier in het bovenstaande resultaat moet je een twijfel in je hoofd hebben dat hoe kunnen we het maximale uit ontbrekende waarde vinden. Dus, hier is de oplossing van uw twijfel ook:

in het tweede knooppunt kiezen we de minimumwaarde als c die kleiner is dan of gelijk is aan 2 dat wil zeggen c < = 2. Nu als c < = 3 en we moeten kiezen voor de max van 3, c, 2 De maximale waarde is 3.

we hebben een besluit genomen zonder naar die knooppunten te kijken. En dit is waar alfa-beta snoeien in het spel komt.

belangrijke punten in alfa-beta snoeien

• alfa: alfa is de beste keuze of de hoogste waarde die we hebben gevonden op elk moment langs het pad van Maximizer. De beginwaarde voor Alfa is -∞.

• Beta: Beta is de beste keuze of de laagste waarde die we hebben gevonden op elk geval langs het pad van Minimizer. De beginwaarde voor Alfa is+∞.

• de voorwaarde voor alfa-beta snoeien is dat α > = β.

• elk knooppunt moet zijn alfa-en bètawaarden bijhouden. Alpha kan alleen worden bijgewerkt wanneer het MAX ’s beurt is en, op dezelfde manier, beta kan alleen worden bijgewerkt wanneer het Min’ s kans.

• MAX werkt alleen alpha-waarden bij en MIN player werkt alleen beta-waarden bij.

• de knooppunt waarden worden doorgegeven aan de bovenste knooppunten in plaats van de waarden van alpha en beta tijdens gaan in omgekeerde boom.

• Alfa-en Bètawaarden worden alleen doorgegeven aan onderliggende knooppunten.

werking van alfa-beta snoeien

1. we beginnen eerst met de eerste zet. We zullen in eerste instantie de alfa-en bètawaarden definiëren als het slechtste geval, d.w.z. α = – ∞ En β=+∞. We snoeien de knoop alleen als Alfa groter wordt dan of gelijk is aan beta.

2. Omdat de beginwaarde van Alfa kleiner is dan beta, hebben we het niet gesnoeid. Nu is het aan de beurt voor MAX. Dus bij knooppunt D wordt de waarde van Alfa berekend. De waarde van Alfa op knooppunt D is max (2, 3). Dus de waarde van Alfa op knooppunt D is 3.

3. Nu is de volgende zet op knooppunt B en zijn beurt voor MIN nu. Dus, bij knoop B, zal de waarde van alpha beta min (3,∞) zijn. Dus bij knooppunt B zijn de waarden alpha= – ∞ en beta 3.

in de volgende stap doorkruisen algoritmen de volgende opvolger van Knoop B, die knoop E is, en de waarden van α= -∞, En β= 3 zullen ook worden doorgegeven.

4. Nu is het aan de beurt voor MAX. Bij node E gaan we op zoek naar MAX. De huidige waarde van alfa bij E is – ∞ en wordt vergeleken met 5. Dus, MAX ( – ∞ , 5) zal 5 zijn. Dus, bij knoop E, alpha = 5, Beta = 5. Nu kunnen we zien dat alfa groter is dan beta die voldoet aan de snoeiconditie, zodat we de juiste opvolger van knooppunt E kunnen snoeien en algoritme zal niet worden doorkruist en de waarde bij knooppunt E zal 5 zijn.

6. In de volgende stap komt het algoritme weer bij knooppunt A van knooppunt B. Bij knooppunt A wordt een alfa veranderd in maximale waarde als MAX ( – ∞ , 3). Dus nu zal de waarde van alfa en beta op knoop A respectievelijk (3, + ∞) zijn en worden overgedragen aan knoop C. Deze zelfde waarden zullen worden overgedragen aan knoop F.

7. Op knooppunt F wordt de waarde van alpha vergeleken met de linker tak die 0 is. Dus, MAX (0, 3) zal 3 zijn en dan vergeleken met het juiste kind dat 1 is, en MAX (3,1) = 3 blijft nog steeds α 3, maar de knooppuntwaarde van F wordt 1.

8. Nu zal knooppunt F de knooppuntwaarde 1 retourneren naar C en zal vergelijken met de bètawaarde bij C. Nu is het aan de beurt voor MIN. Dus MIN ( + ∞ , 1) zal 1 zijn. Nu bij knoop C, α = 3, en β = 1 en alfa is groter dan beta die opnieuw voldoet aan de snoeiconditie. Dus, de volgende opvolger van node C d.w.z. G zal worden gesnoeid en het algoritme heeft niet de hele subtree g berekend.

nu retourneert C de knooppuntwaarde naar A en de beste waarde van A is MAX (1, 3) is 3.

de hierboven weergegeven boom is de laatste boom die de knooppunten toont die berekend zijn en de knooppunten die niet berekend zijn. Dus, voor dit voorbeeld is de optimale waarde van de maximizer 3.

Kijk naar open source Python-bibliotheken.

volgorde van Verplaatsen bij snoeien

de effectiviteit van alfa – beta snoeien is gebaseerd op de volgorde waarin knooppunt wordt onderzocht. Verplaatsen volgorde speelt een belangrijke rol in alpha beta snoeien.

er zijn twee soorten verplaatsingsvolgorde in Alpha beta snoeien:

1. slechtste volgorde: in sommige gevallen van alpha beta snoeien geen van de knooppunt gesnoeid door het algoritme en werkt als standaard minimax algoritme. Dit verbruikt veel tijd als gevolg van alfa en beta factoren en geeft ook geen effectieve resultaten. Dit wordt de slechtste volgorde in het snoeien genoemd. In dit geval vindt de beste zet plaats aan de rechterkant van de boom.
2. ideale volgorde: in sommige gevallen van alpha beta snoei partij van de knooppunten gesnoeid door het algoritme. Dit wordt Ideal ordering in snoeien genoemd. In dit geval vindt de beste zet plaats aan de linkerkant van de boom. We passen DFS dus het eerst zoeken links van de boom en gaan diep twee keer als minimax algoritme in dezelfde hoeveelheid tijd.

regels om een goede volgorde te vinden

• de beste zet vindt plaats vanaf het laagste knooppunt
• gebruik domeinkennis terwijl het vinden van de beste zet
• volgorde van knooppunten moet zo zijn dat de beste knooppunten eerst worden berekend

bekijk deze Python Tutorial voor Beginners

Codes in Python

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

in dit document hebben we een belangrijk onderdeel van de speltheorie gezien. Hoewel de prestaties van het minimax-algoritme goed zijn, is het algoritme traag. Dus om het snel te maken gebruiken we alfa-beta snoei algoritme dat de ongebruikelijke knooppunten van de beslissingsboom zal knippen om de prestaties te verbeteren. Tegenwoordig snel en goed uitgevoerd algoritme wordt veel gebruikt.

bekijk deze Artificial Intelligence en Machine Learning cursussen van geweldig leren tot upskill in het domein en master Alpha Beta snoeien en andere dergelijke algoritmen.

verder lezen

1. A * zoekalgoritme in kunstmatige intelligentie (AI)
2. Beslissingsboomalgoritme uitgelegd met voorbeelden
3. beste eerste zoekalgoritme in AI | Concept, implementatie, voor-en nadelen
4. Wat is kunstmatige intelligentie? Hoe werkt AI, soorten en toekomst van IT?