論文の概要: Completeness of Unbounded Best-First Minimax and Descent Minimax

• arxiv url: http://arxiv.org/abs/2603.24572v1
• Date: Wed, 25 Mar 2026 17:50:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-26 21:06:11.420748
• Title: Completeness of Unbounded Best-First Minimax and Descent Minimax
• Title（参考訳）: 非有界Best-First MinimaxとDescent Minimaxの完全性
• Authors: Quentin Cohen-Solal,
• Abstract要約: 本稿では,2プレイヤー完全情報ゲームを対象とした検索アルゴリズムについて述べる。 このクラスのアルゴリズムが最良戦略を計算していることを示す。 実験により, 完成技術が勝利性能を向上させることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this article, we focus on search algorithms for two-player perfect information games, whose objective is to determine the best possible strategy, and ideally a winning strategy. Unfortunately, some search algorithms for games in the literature are not able to always determine a winning strategy, even with an infinite search time. This is the case, for example, of the following algorithms: Unbounded Best-First Minimax and Descent Minimax, which are core algorithms in state-of-the-art knowledge-free reinforcement learning. They were then improved with the so-called completion technique. However, whether this technique sufficiently improves these algorithms to allow them to always determine a winning strategy remained an open question until now. To answer this question, we generalize the two algorithms (their versions using the completion technique), and we show that any algorithm of this class of algorithms computes the best strategy. Finally, we experimentally show that the completion technique improves winning performance.
• Abstract（参考訳）: 本稿では,最適な戦略を決定することを目的とした2プレイヤー完全情報ゲームの探索アルゴリズムと,理想的には勝利戦略に焦点をあてる。 残念ながら、文学におけるゲームのためのいくつかの検索アルゴリズムは、無限の検索時間であっても、常に勝利戦略を決定することはできない。 Unbounded Best-First Minimax と Descent Minimax は、最先端の知識のない強化学習におけるコアアルゴリズムである。 その後、いわゆる完成技術によって改良された。 しかし、この手法がこれらのアルゴリズムを十分に改良し、勝利戦略を常に決定できるようにするかどうかは、これまでは未解決のままであった。 この疑問に答えるために、我々は2つのアルゴリズムを一般化し(補完手法を用いたバージョン)、このクラスのアルゴリズムが最良戦略を計算していることを示す。 最後に,本手法が勝利性能を向上させることを実験的に示す。

関連論文リスト

• Who is the Winning Algorithm? Rank Aggregation for Comparative Studies [4.501091570166657]
  本稿では,各mアルゴリズムの勝利確率を推定するための新しい概念的枠組みを提案する。 提案手法は,現在知られている合成実例と実例において,大幅に改善されている。
  論文  参考訳（メタデータ） (2026-01-04T20:52:47Z)
• Study and improvement of search algorithms in two-players perfect information games [0.0]
  完全情報を持つ2プレイヤーゼロサムゲームの新しい探索アルゴリズムを提案する。 短い検索期間で、この大規模な実験では、すべてのゲームで研究対象のアルゴリズムを上回ります。 また,中程度の検索時間では,22ゲーム中17ゲームにおいて,すべての学習アルゴリズムを上回ります。
  論文  参考訳（メタデータ） (2025-05-06T19:29:59Z)
• Research Re: search & Re-search [0.0]
  本研究では,深度優先アルゴリズムのABと最良優先アルゴリズムのSSSについて詳しく検討する。 これらのアルゴリズムの一般的な意見は、SSSはより効率的な探索の可能性をもっているが、その複雑な定式化と指数記憶の要求はそれを非現実的にしている。
  論文  参考訳（メタデータ） (2024-03-20T16:08:57Z)
• The Update-Equivalence Framework for Decision-Time Planning [78.44953498421854]
  本稿では,サブゲームの解決ではなく,更新等価性に基づく意思決定時計画のための代替フレームワークを提案する。 ミラー降下に基づく完全協調型ゲームに対する有効音声探索アルゴリズムと、磁気ミラー降下に基づく対戦型ゲームに対する探索アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-25T20:28:55Z)
• Learning to Play Stochastic Two-player Perfect-Information Games without Knowledge [5.071342645033634]
  我々はDescentフレームワークを拡張し、完全な情報を持つ2人プレイヤゲームのコンテキストにおける学習と計画を可能にする。 我々は、最先端のアルゴリズムに対してEin wurfelt!で評価する。 最良の結果を得るのはDescentの一般化である。
  論文  参考訳（メタデータ） (2023-02-08T20:27:45Z)
• The Information Geometry of Unsupervised Reinforcement Learning [133.20816939521941]
  教師なしスキル発見(英語: Unsupervised skill discovery)とは、報酬関数にアクセスせずに一連のポリシーを学ぶアルゴリズムのクラスである。 教師なしのスキル発見アルゴリズムは、あらゆる報酬関数に最適なスキルを学習しないことを示す。
  論文  参考訳（メタデータ） (2021-10-06T13:08:36Z)
• Completeness of Unbounded Best-First Game Algorithms [0.0]
  2つのゲーム検索アルゴリズムの完全性を証明する。 完全情報マルチプレイヤーゲームにおいて,これらのアルゴリズムを一般化する。
  論文  参考訳（メタデータ） (2021-09-11T23:13:52Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。 本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
  論文  参考訳（メタデータ） (2021-07-20T11:23:21Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds [48.312484940846]
  睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。 各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。 我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-03-07T02:13:21Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  ゲームプレイを通じて,ゲームの記述を明示せず,託宣のみにアクセス可能な,重要で一般的なゲーム解決環境について検討する。 限られたデュレーション学習フェーズにおいて、アルゴリズムは両方のプレイヤーのアクションを制御し、ゲームを学習し、それをうまくプレイする方法を学習する。 私たちのモチベーションは、クエリされた戦略プロファイルの支払いを評価するのにコストがかかる状況において、利用可能性の低い戦略を迅速に学習することにあります。
  論文  参考訳（メタデータ） (2020-02-24T20:30:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。