計算機に遊戯王を理解させる

さて、コンピュータと遊戯王その２です。

ADSのコードは順調に解読できていて、メインフレームやコア、イベント管理など把握はできました。

どうやらADSはソケット通信でサーバーとクライアント間のイベントをやり取りして、それをサーバー側のコアが処理しているようなのですが、クライアントからサーバー側にどんな情報を送れば良いのかで詰まってしまい解析は中断中です。
~~（誰か知ってたら教えてください...）~~※追記:解決済み※

ADSと繋げなくてもAI開発はできるんですけど、やはり人間をぶっ潰してこそAIの価値があると思うので何とかホスト・クライアント通信を実現させたいです。

今日の話題は「計算機に遊戯王を理解させる」ということで、頭に浮かびつつあるアルゴリズムを書き起こして問題点を洗い出してみようと思います。

前回の案
今回の案
終わりに

前回の案

https://nnt339es.hatenablog.com/entry/2020/09/27/020625nnt339es.hatenablog.com
前回の案は環境が変わろうとも永久に学習を続けていくため手堅いアルゴリズムだと考えていたのですが、やはり探索空間の広さがネックです。

グラフ理論を使って、デュエル状況をノード、タグをエッジとすればエッジによって連結空間が作成されるため、UnionFindアルゴリズムを使えばある程度高速化できるかもしれませんね。
ただ、その場合プログラム起動時にデータベースをすべてメモリに読み込むことになるので莫大なメモリ空間が必要になるでしょう。

~~私の環境では12GB積んでるんで不可能でもないかもしれませんが、複数のプログラムを立ち上げるのは無理そうです。~~
データベースにクエリ投げるだけですね。レスポンスは結構速く感じますが、100万データとかだとどれくらいなんでしょう？

そして、このアルゴリズムのもう一つの弱点は同じ名前のカードしか検索できないということです！

今回の案

単語の分散表現

先日「PythonでB’zの歌詞を機械学習させる」（うろ覚え）のようなブログを見つけて、単語の分散表現というのを知りました。

単語の分散表現(distributed representation)とは簡単に説明すると、単語を意味空間の成分にベクトル分解します。

単語を意味空間ベクトルで表現することで、"king" - "man" + "woman" = "queen"のように単語の意味演算が可能となります。

遊戯王への応用

実装アルゴリズムは置いておいて、私のやりたいこととしては
"エアーマン" - "HERO" + "光天使" = "セプター"　です。

つまり、遊戯王の効果を分散表現してコンピュータに理解させたいわけです。

そこで先ほどの単語分散表現のアルゴリズムを参考にしますと、単語の周りの単語を入力として元の単語の予測させるという方法で学習させるそうです。
データセットの文書それ自体が教師となるわけです。

しかし、遊戯王カード名を使った文書なんて数が知れてますし、そもそもそのアルゴリズムでは"エアーマン" - "HERO" + "光天使" = "セプター"は実現できないと思うのですよ。
効果テキストを教師として学習させても効果の意味までは理解できないのがまた。

と、そのままでは使い物にはならないのです。

発想の整理

改めて私の目標を書きますと、"エアーマン" - "HERO" + "光天使" = "セプター"、です。

つまり、効果テキストを意味空間にベクトル分解してその演算を行いたいのです。
いや、もはや "エアーマン"＝"セプター" ができればもう良いです。

単なる効果分けではダメなのか？

私はこれはダメだと考えています。
理由を以下に述べます。

次元数が膨大

デッキから手札を加える
フィールドのモンスターを1体破壊する
...

と効果を列挙した場合、細かな違いも1次元とカウントされるため次元数が膨れ上がります。

また、この列挙は人為的なものなので漏れがないことを証明するのにコストがかかります。

抽象的な概念を抽出できない
例えば、「ドロー」と「サーチ」は同じ「デッキから手札に加える」操作ですが、単純分けした場合この二つは全く異なるものとして扱うため関連性は失われます。

「ドロー」と「サーチ」、「ドロー」と「破壊」の違いを等価に扱うのは人間の思考とはかけ離れていると思いませんか？

新効果に対応できない
かつて「裏側除外」という処理を行うカードは存在しませんでした。

しかし、「裏側表示」と「除外する」というワードはプレイヤーの中にあったため、我々人間は公式に問い合わせることなくカードを使用することができました。

ところが効果分けの場合、新たに「裏側で除外する」の次元を設けなければなりません。

デュエルの状況

どうやって効果のベクトル表示を得るかは置いておいて、ベクトル表示によって得られる展望を述べたいと思います

効果のベクトル表示が強力なのは盤面の全てのカードについてベクトルの和を取ることで、デュエルの状況を効果空間（結果空間？）上に配置できるということです！

例えば、相手フィールド上に効果未使用の《サイバードラゴン・インフィニティ》または《召喚獣メルカバー》がいる状況は共通点があります。
これらの状況は効果空間上の同じ方向に配置されるはずなので、類似状況として検出可能です。

また、デュエル状況をベクトル空間に配置するとK平均クラスタリングによってカテゴリ分けができるため、探索空間を大幅に削ることができます。

効果空間の問題点

ステータスの扱い

《神の宣告》と《神の警告》が似ていると感じるのは、効果ベクトルの類似性はその一因でしょうが、それ以前にどちらもカウンター罠だからというのがあると思います。
《神の警告》と《エヴォルカイザー・ラギア》のどちらがより《神の宣告》に似ていると感じるでしょうか。

問題点はステータスを効果ベクトルの成分と同等に扱ってよいのかどうかです。

同等に扱うというのは同じだけ類似度に寄与するということです。
《エアーマン》と《セプター》が似ていると感じるのは、そのステータスもよく似ているからだと思います。
しかし、同じ光属性・レベル４・天使族の《オネスト》は《セプター》に似ているでしょうか？
光属性・レベル４・戦士族・サーチ効果持ちの《星輝士デネブ》は《エアーマン》に似ているでしょうか？

ステータスの一致不一致は０か１で白黒はっきり出ます。
ところが《エアーマン》と《セプター》の守備力100の違いは0と1の間にある気がします。

このように重みが異なるようなステータスのパラメータを効果ベクトルと同等に扱って良いのでしょうか？
もし分別するのならばその重みは何によって決定すれば良いでしょうか？