* Pluribus is the first AI bot capable of beating human experts in six-player no-limit Hold’em, the most widely played poker format in the world. This is the first time an AI bot has beaten top human players in a complex game with more than two players or two teams.
* We tested Pluribus against professional poker players, including two winners of the World Series of Poker Main Event. Pluribus won decisively.
* Pluribus succeeds because it can very efficiently handle the challenges of a game with both hidden information and more than two players. It uses self-play to teach itself how to win, with no examples or guidance on strategy.
* Pluribus uses far fewer computing resources than the bots that have defeated humans in other games.
* The bot’s success will advance AI research, because many important AI challenges involve many players and hidden information.
Ниже есть продолжение.
...In recent years, new AI methods have been able to beat top humans in poker if there is only one opponent. But developing an AI system capable of defeating elite players in full-scale poker with multiple opponents at the table was widely recognized as the key remaining milestone...https://ai.facebook.com/blog/pluribus-first-ai-to-beat-pros-in-6-player-poker/
Pluribus incorporates a new online search algorithm that can efficiently evaluate its options by searching just a few moves ahead rather than only to the end of the game. Pluribus also uses new, faster self-play algorithms for games with hidden information. Combined, these advances made it possible to train Pluribus using very little processing power and memory — the equivalent of less than $$$150 worth of cloud computing resources. This efficiency stands in stark contrast to other recent AI milestone projects, which required the equivalent of millions of dollars’ worth of computing resources to train.
...Multi-player interactions pose serious theoretical and practical challenges to past AI techniques. Our results nevertheless show that a carefully constructed AI algorithm can reach superhuman performance outside of two-player zero-sum games...
...The core of Pluribus's strategy was computed via self-play, in which the AI plays against copies of itself, without any human gameplay data used as input. The AI starts from scratch by playing randomly and gradually improves as it determines which actions, and which probability distribution over those actions, lead to better outcomes against earlier versions of its strategy. The version of self-play used in Pluribus is an improved variant of the iterative Monte Carlo CFR (MCCFR) algorithm.
On each iteration of the algorithm, MCCFR designates one player as the “traverser” whose current strategy is updated on the iteration. At the start of the iteration, MCCFR simulates a hand of poker based on the current strategy of all players (which is initially completely random). Once the simulated hand is completed, the algorithm reviews each decision the traverser made and investigates how much better or worse it would have done by choosing the other available actions instead. Next, the AI assesses the merits of each hypothetical decision that would have been made following those other available actions, and so on...
...Exploring other hypothetical outcomes is possible because the AI is playing against copies of itself. If the AI wants to know what would have happened if some other action had been chosen, then it need only ask itself what it would have done in response to that action.
The difference between what the traverser would have received for choosing an action versus what the traverser actually achieved (in expectation) on the iteration is added to the counterfactual regret for the action. At the end of the iteration, the traverser's strategy is updated so that actions with higher counterfactual regret are chosen with higher probability.
Maintaining counterfactual regrets for each action in each decision point in a game such as no-limit Texas Hold’em would require more bytes than the number of atoms in the universe. To reduce the complexity of the game, we ignore some actions and also bucket similar decision points together in a process called abstraction. After abstraction, the bucketed decision points are treated as identical.
Pluribus's self-play outputs what we refer to as the blueprint strategy for the entire game. During actual play, Pluribus improves upon this blueprint strategy using its search algorithm. But Pluribus does not adapt its strategy to the observed tendencies of its opponents...
The blueprint strategy is necessarily coarse-grained because of the size and complexity of no-limit Texas Hold'em. During actual play, Pluribus improves upon the blueprint strategy by conducting real-time search to determine a better, finer-grained strategy for its particular situation.
AI bots have used real-time search in many perfect-information games, including backgammon (two-ply search), chess (alpha-beta pruning search), and Go (Monte Carlo tree search). For example, when determining their next move, chess AIs commonly look some number of moves ahead until a leaf node is reached at the depth limit of the algorithm's lookahead.
Those search methods, however, don’t work with imperfect-information games because they do not consider the opponents’ ability to shift to different strategies beyond the leaf nodes. This weakness leads the search algorithms to produce brittle, unbalanced strategies that the opponents can easily exploit. AI bots were previously unable to solve this challenge in a way that can scale to six-player poker.
Pluribus instead uses an approach in which the searcher explicitly considers that any or all players may shift to different strategies beyond the leaf nodes of a subgame. Specifically, rather than assuming all players play according to a single fixed strategy beyond the leaf nodes (which results in the leaf nodes having a single fixed value), we instead assume that each player may choose among four different strategies to play for the remainder of the game when a leaf node is reached. One of the four continuation strategies we use in Pluribus is the precomputed blueprint strategy; another is a modified form of the blueprint strategy in which the strategy is biased toward folding; another is the blueprint strategy biased toward calling; and the final option is the blueprint strategy biased toward raising.
This technique results in the searcher finding a more balanced strategy that produces stronger overall performance, because choosing an unbalanced strategy (e.g., always playing rock in rock-paper-scissors) would be punished by an opponent shifting to one of the other continuation strategies (e.g., always playing paper).
As we’ve noted, another major challenge of search in imperfect-information games is that a player's optimal strategy for a particular situation depends on how her opponents perceive her gameplay. If a player never bluffs, her opponents would know to always fold in response to a big bet.
To cope, Pluribus tracks the probability it would have reached the current situation with each possible hand according to its strategy. Regardless of which hand Pluribus is actually holding, it will first calculate how it would act with every possible hand — being careful to balance its strategy across all the hands so it remains unpredictable to the opponent. Once this balanced strategy across all hands is computed, Pluribus then executes an action for the hand it is actually holding...
וד מחסום נפרץ! הפעם המכונות מנצחות אותנו בפוקר.
כבר ראינו בעבר מכונות שמשחקות פוקר לא רע בכלל, אבל תמיד היה מדובר בשני שחקנים בלבד, או בגרסאות מוחלשות יותר של פוקר. הפעם זה הדבר האמיתי: האלגוריתם החדש (של שני מדענים מפייסבוק וקרנגי-מלון) ישב בשולחן עם עוד 5 שחקנים אנושיים מקצוענים, שיחק נו-לימיט טקסס הולדאם, ורוקן אותם לגמרי.
אז קודם כל, מה כל כך מסובך למכונה לשחק פוקר?
הבעייה כאן שלאף אחד מהשחקנים אין מידע מלא על המשחק. שלא כמו במשחק שחמט, שבו הלוח גלוי לכולם, כאן הקלפים חבויים. כל שחקן מכיר את היד שלו, אבל צריך לנחש מה יש לאחרים.
אפשר לבלף, ולהעמיד פנים כאילו יש לי יד מעולה. אבל אם אשקר כל הזמן (או לחילופין אשחק כל הזמן בדיוק לפי הקלפים שלי), מהר מאוד השחקנים האחרים יקלטו אותי, ויתקנו את האסטרטגיה שלהם בהתאם.
כדי לנצח, האלגוריתם משתמש ברעיון שנקרא "מיזעור הצער" (counterfactual regret minimization). הוא משחק נגד עצמו ואז מסתכל אחורה על המשחק ואומר: "יא אללה איזה מטומטם אני, אם הייתי מעלה את ההימור קודם, הייתי מפרק את כל השולחן" (זה החלק של הצער). ואז הוא מתקן לעצמו את האסטרטגיה, כך שבפעם הבאה, במקרה דומה, הוא באמת יעלה את ההימור (זה החלק של מיזעור הצער).
עכשיו, הטריק הזה כבר ידוע הרבה זמן. הבעייה איתו שזה סבבה כשמשחקים 1-על-1. אבל נגד 5 שחקנים זה נהיה יותר מידי מסובך לחשב. אז האלגוריתם החדש משתמש בכל מיני טריקים. למשל, הוא יודע לקבץ ביחד ידיים שהן די דומות מבחינת אסטרטגיה (סטרייט עם 9 או עם 10 זה כמעט אותו הדבר) כדי לצמצם באופן משמעותי את החישובים שלו. הוא גם מנסה לשחק רק 4 תורות קדימה (במקום את כל המשחק עד הסוף), ואז בודק מה כל שחקן היה עושה אם הוא היה שחקן מאוזן, או שחקן שנוטה להתקפל, או שחקן שנוטה להעלות או להשוות.
בנוסף הוא שואל את עצמו: מה הייתי אני עושה, אם היתה לי יד גרועה בהרבה? או יד טובה בהרבה?
התוצאה היא שהוא בוחר באופן מקרי אם הוא עומד לבלף או לשחק כהלכה. באופן כה מקרי, עד שהשחקנים שמולו לא מצליחים לאתר שום דפוס משחק. פרצוף הפוקר המושלם.
וכך הוא משחק לו עוד תור ועוד תור, ולא טועה אף פעם. השחקנים האנושיים כן טועים פה ושם, כך שאלמנט המזל הולך ונמוג, והמחשב מנצח אותם באופן עקבי.
דארן אליאס, 4 פעמים אלוף העולם, אמר בעצב: כל מה שאני עושה מאז גיל 16 זה לשחק פוקר. הקדשתי את חיי למשחק הזה. זה די מכאיב להפסיד למכונה. הפעם הראשונה שבינה מלאכותית מנצחת היא גם הפעם האחרונה שבן אנוש ינצח.
אפשר להניח שלא יעבור זמן רב עד שהאלגוריתם ימצא את דרכו לזירות המשחקים באינטרנט, ומישהו יגרוף לא-מעט כסף עד שייחשף (אם בכלל).
ברעיונות שפותחו עכשיו אפשר גם להשתמש לתמחור חכם, למשא ומתן, תפיסת רמאים, השתלבות בתנועה, ועוד מליון דברים, חלקם לא נחמדים ולא מלבבים בכלל.
בקיצור, רק התחלנו
...More information is available in this newly published paper in Science...
https://www.facebook.com/groups/1742464739390368/permalink/2097888333848005/
No comments:
Post a Comment