論文の概要: Fast constraint satisfaction problem and learning-based algorithm for solving Minesweeper

• arxiv url: http://arxiv.org/abs/2105.04120v1
• Date: Mon, 10 May 2021 05:27:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-11 15:00:23.861268
• Title: Fast constraint satisfaction problem and learning-based algorithm for solving Minesweeper
• Title（参考訳）: 制約満足度問題の高速解法と学習ベースアルゴリズム
• Authors: Yash Pratyush Sinha, Pranshu Malviya, Rupaj Kumar Nayak
• Abstract要約: 現在の作品は、このゲームを制約満足問題(CSP)とマルコフ決定プロセス(MDP)としてモデル化します。 CSP ベースの Minesweeper ゲームのすべての解を高速に列挙するために、決定論的解探索 (DSScsp) を用いて独立集合から従属として命名された新しい方法を提案する。 また,Minesweeperゲームにおいて,改良された深層Q-ラーニングを精度良く,多目的学習に応用するための新たな報奨手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minesweeper is a popular spatial-based decision-making game that works with incomplete information. As an exemplary NP-complete problem, it is a major area of research employing various artificial intelligence paradigms. The present work models this game as Constraint Satisfaction Problem (CSP) and Markov Decision Process (MDP). We propose a new method named as dependents from the independent set using deterministic solution search (DSScsp) for the faster enumeration of all solutions of a CSP based Minesweeper game and improve the results by introducing heuristics. Using MDP, we implement machine learning methods on these heuristics. We train the classification model on sparse data with results from CSP formulation. We also propose a new rewarding method for applying a modified deep Q-learning for better accuracy and versatile learning in the Minesweeper game. The overall results have been analyzed for different kinds of Minesweeper games and their accuracies have been recorded. Results from these experiments show that the proposed method of MDP based classification model and deep Q-learning overall is the best methods in terms of accuracy for games with given mine densities.
• Abstract（参考訳）: minesweeperは不完全な情報を扱う一般的な空間ベースの意思決定ゲームだ。 模範的なnp完全問題として、様々な人工知能パラダイムを用いた研究の主要な分野である。 本研究は,このゲームを,制約満足度問題 (CSP) とマルコフ決定プロセス (MDP) としてモデル化する。 決定論的解探索(DSScsp)を用いて,CSPベースのMinesweeperゲームの全解を高速に列挙し,ヒューリスティックスを導入して結果を改善する手法を提案する。 MDPを用いてこれらのヒューリスティックスに機械学習手法を実装した。 CSPの定式化の結果を用いてスパースデータに基づく分類モデルを訓練する。 また,Minesweeperゲームにおいて,改良された深層Q-ラーニングを精度良く多目的学習に応用するための新たな報奨手法を提案する。 総合的な結果は異なる種類のミネズウィーパーゲームで分析され、その精度が記録されている。 これらの結果から, MDP を用いた分類モデルと深層Q-ラーニングの手法が, 与えられたマイニング密度を持つゲームに最適な手法であることが示唆された。

関連論文リスト

• Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference [55.150117654242706]
  我々は、1.8万のデータポイントでトレーニングされた計算対応GPのモデル選択が、1つのGPU上で数時間以内に可能であることを示す。 この研究の結果、ガウス過程は、不確実性を定量化する能力を著しく妥協することなく、大規模なデータセットで訓練することができる。
  論文  参考訳（メタデータ） (2024-11-01T21:11:48Z)
• Blending gradient boosted trees and neural networks for point and probabilistic forecasting of hierarchical time series [0.0]
  本稿では、勾配木やニューラルネットワークファミリーに属する機械学習モデルのブレンディング手法について述べる。 これらの原則は、最近のM5コンペティションにおいて、正確性と不確実性の両方のトラックでうまく適用された。
  論文  参考訳（メタデータ） (2023-10-19T09:42:02Z)
• A Survey on the Integration of Machine Learning with Sampling-based Motion Planning [9.264471872135623]
  本調査は、サンプリングベースモーションプランナー(SBMP)の計算効率と適用性を改善するための機械学習の取り組みを概観する。 まず、ノードサンプリング、衝突検出、距離または最も近い隣人、ローカルプランニング、終了条件など、SBMPのキーコンポーネントの強化に学習がどのように使われているかについて論じる。 また、機械学習を用いてロボットのデータ駆動モデルを提供し、それをSBMPで使用する方法についても論じている。
  論文  参考訳（メタデータ） (2022-11-15T18:13:49Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。 オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。 我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
  論文  参考訳（メタデータ） (2022-08-26T04:28:01Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• Learning the Markov Decision Process in the Sparse Gaussian Elimination [0.0]
  スパースガウス除去のための学習に基づくアプローチを提案する。 スパースソルバの主モジュールに対するQ-Learningアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T08:56:39Z)
• Memory-Based Optimization Methods for Model-Agnostic Meta-Learning and Personalized Federated Learning [56.17603785248675]
  モデルに依存しないメタラーニング (MAML) が人気のある研究分野となっている。 既存のMAMLアルゴリズムは、イテレーション毎にメタモデルを更新するためにいくつかのタスクとデータポイントをサンプリングすることで、エピソードのアイデアに依存している。 本稿では,MAMLのメモリベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-09T08:47:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。 ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
  論文  参考訳（メタデータ） (2020-07-07T17:03:02Z)
• Reinforced Data Sampling for Model Diversification [15.547681142342846]
  本稿では,データを適切にサンプリングする方法を学ぶための新しいReinforced Data Smpling (RDS)法を提案する。 モデルダイバーシフィケーションの最適化問題である$delta-div$をデータサンプリングで定式化し,モデルダイバーシフィケーションを注入することで学習ポテンシャルと最適アロケーションを最大化する。 モデル多様化のためのトレーニング可能なサンプリングは,各種機械学習タスクの潜在能力を追求する競技組織,研究者,さらには開始者にとって有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-12T11:46:13Z)

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

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