Mon compte

connexion

inscription

   Publicité R▼


 » 
allemand anglais arabe bulgare chinois coréen croate danois espagnol espéranto estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien
allemand anglais arabe bulgare chinois coréen croate danois espagnol espéranto estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien

Significations et usages de ミニマックス法

Définition

⇨ voir la définition de Wikipedia

   Publicité ▼

Wikipedia

ミニマックス法

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ミニマックス法(minimax)は、想定される最大の損害が最小になるように決断を行う戦略のこと。将棋チェスなどといった完全情報ゲームをコンピュータに思考させるためのアルゴリズムの一つであり、それらの中で最も基礎となるものである。これに対し、想定される最小の利益が最大になるように決断を行う戦略はマクシミン戦略という。

目次

ゲーム木

詳細は「ゲーム木」を参照

完全情報ゲームは、お互いがどの手を打ったかによってどのような局面が出現するかを場合分けしていくことでゲーム展開を樹形図にできる。このように現在の局面から出現するすべての局面の関係をゲーム木と呼ぶ。

ゲーム木は各段階で枝分かれてしていくが、枝分かれの数はプレーヤーの選択肢の数だけあり、ゲーム木を下にたどる(より先を読む)につれ局面(節点)の数は爆発的に増加する。

ゲームの思考をすることは、ゲーム木を読み解くことに他ならない。

思考プログラムの基本的な考え方

思考プログラムの基本は、局面がどの程度自分にとって有利か点数を付ける(評価する)ことである。局面の有利度を適切に評価することができれば、自分の打てる手のうち、最も評価の高い局面を出現させるような手を選択すればよいことになる。

局面に置かれている駒の位置・数などだけから算出した評価値を静的評価値、算出する関数を静的評価関数と呼ぶ。「静的」とはここでは先読みをしていないことを意味する。通常、静的評価関数だけで適切な局面評価を行うことは困難である。そのため、先読みを実現するのがこのミニマックス法である。

先読み

先を読んだ上で、ある局面がどの程度有利であるかを評価するには、以下の考え方を用いればよい。

  1. 読みたい局面が相手の番であれば、その局面の次に出現するすべての局面のうち最も悪い(不利な)、つまり相手にとって最も有利な(評価値が最小)手を相手は打ってくるはずである。そこで、次に出現するすべての局面の評価値の最小値を局面の評価値にすればよい
  2. 読みたい局面が自分の番であれば、その局面の次に出現するすべての局面のうち最も良い評価(評価値が最大)の手を打つことができる。そこで、次に出現するすべての局面の評価値の最大値を局面の評価値にすればよい

相手番の局面の評価値を求めるには、次に出現するすべての局面(自分番)の評価値を求めればいいので、その自分番の評価値を求めるには・・・、と再帰的にゲーム木を展開していくことで求めることができる。

何手先まで読むかによって、その深さまで展開したところでは静的評価関数を用いることで探索を打ち切ることができる。前述したように、ゲーム木は深くなるにつれ局面数が爆発的に増える。そのため、ある程度以上の深さまで先読みをしようとすると、実用的な時間では難しくなってくる。

通常は有限の深さまで読むことで打ち切るが、ゲーム終了まで読めばゲームの勝敗を完全に読み切った上で、最善の手を打つことができる。終盤の読みや詰め将棋の解答などは完全読みが行われる(長手数の詰め将棋の解答では完全読みを行わないこともある)。オセロのように勝敗だけでなく石差も問題となるゲームでは、勝敗のみを読み切ることを必勝読み、石差まで読み切ることを完全読みと区別する。

必勝読みでは、各局面の評価値は「勝ち」か「負け」の2通りに限定される。この場合、自分の手番の局面は、次の局面に「一つでも勝ち」があれば(自分はその局面を選択すればよいので)勝ちが決定し、相手の手番の局面は、次の局面が「すべて勝ち」なら(相手には負けを阻止する選択肢がないので)勝ちが決定する。これらは各局面の評価値の論理和(OR)、論理積(AND)とったものであることから、それぞれORノード、ANDノードと呼ばれる。このように評価値が勝敗のみで表されるゲーム木は、特にAND/OR木と呼ばれる。

擬似プログラム

以上のアルゴリズムを擬似コードで記述すると以下のようになる。

function MIN_MAX(position:局面, depth:integer): integerbegin  if depth=0 then return STATIC_VALUE(position); {読み深さに達した}  positionを展開→すべての子ノードをchildren[]に。子ノードの数をwに。  if w=0 then return STATIC_VALUE(position); {終局}    if positionは自分の局面 then begin    max := -∞;    for i:=1 to w do begin      score = MIN_MAX( children[i], depth-1);      if(score>max) max := score;    end;    return max;  end else begin{positionは相手の局面}    min := ∞;    for i:=1 to w do begin      score = MIN_MAX( children[i], depth-1);      if(score<min) min := score;    end;    return min;  end;end;

ネガマックス法

零和ゲームでは、自分にとっての得はそのまま相手にとっての損であり、逆もまたしかりである。

パスのあるオセロなどと違い将棋などパスのないゲームでは、必ず一手ごとに番が変わる。これを利用すると、ノードごとに評価値の正負を逆転させることで「相手は自分にとって損な手を探索する」のではなく「相手は相手にとって得な手を探索する」ように書き換えることができる。これをネガマックス(negamax)法と呼び、ミニマックス法よりもシンプルな記述が可能となる。

function NEGA_MAX(position:局面, depth:integer): integerbegin  if depth=0 then return STATIC_VALUE(position); {読み深さに達した}  positionを展開→すべての子ノードをchildren[]に。子ノードの数をwに。  if w=0 then return STATIC_VALUE(position); {終局}    max := -∞;  for i:=1 to w do begin    score = -NEGA_MAX( children[i], depth-1);    if(score>max) max := score;  end;  return max;end;

応用アルゴリズム

ミニマックス法はすべての局面に対してしらみつぶしに探索を行うため、実際には読む必要のない(評価しなくても支障がない)手も読むことになり探索効率が悪い。これを改善したアルゴリズムとしてα-β法がある。α-β法は、読む必要のない手を打ち切ることで高速化を図っている。

実際のゲームプログラムではα-β法をさらに応用したアルゴリズムが用いられることが多い。

 

Toutes les traductions de ミニマックス法


Contenu de sensagent

  • définitions
  • synonymes
  • antonymes
  • encyclopédie

dictionnaire et traducteur pour sites web

Alexandria

Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !

Essayer ici, télécharger le code;

SensagentBox

Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.

Solution commerce électronique

Augmenter le contenu de votre site

Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.

Parcourir les produits et les annonces

Obtenir des informations en XML pour filtrer le meilleur contenu.

Indexer des images et définir des méta-données

Fixer la signification de chaque méta-donnée (multilingue).


Renseignements suite à un email de description de votre projet.

Jeux de lettres

Les jeux de lettre français sont :
○   Anagrammes
○   jokers, mots-croisés
○   Lettris
○   Boggle.

Lettris

Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.

boggle

Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer

Dictionnaire de la langue française
Principales Références

La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).

Copyright

Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.

Traduction

Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.

 

8730 visiteurs en ligne

calculé en 0,031s


Je voudrais signaler :
section :
une faute d'orthographe ou de grammaire
un contenu abusif (raciste, pornographique, diffamatoire)
une violation de copyright
une erreur
un manque
autre
merci de préciser :