RとGridDBを用いたチェスの不正行為者の捕捉

チェスは古くからあるゲームで、毎日何百万人もの人がプレイしています。チェスは、他の多くのゲームと同様に、技術の強化により、プレーヤーが互いに交流し、学び、アイデアを交換する機会を与える様々なプレイプラットフォームによるブームを見てきました。それでも、過去数十年の間にチェスが見た最も劇的な改善は、人工知能ベースのモデルの導入であり、世界で最も優れたプレーヤーでさえ、彼らに対抗できないほど優れたものになりました。

しかし、すべてのコインには両面があり、この場合、コンピュータは、多くのオンラインチェストーナメントでフェアプレーの問題を引き起こしている他の人間と対戦しながら不正行為を行う能力を偽者に与えてしまったのです。では、不正を発見することはできるのでしょうか？あるとすればどのような方法で不正を見破れるのでしょうか？

以下のセクションでは、**あからさまな**不正行為を検出するための簡単なアルゴリズムを構築する方法を探ります。

分析を始める前に、まずチェスの専門用語を理解することから始めましょう。まず、**センチポーン**値とは、チェスエンジンがチェスのポジションを評価するために使用する数値のことです。標準的には、ポーンのような最も単純な駒は100cpの価値があるとみなされます。同様に、最も価値のある駒であるクイーンは900cpの価値があるとされています。

次に、**イロレーティング**はチェスで使われる指標で、各チェスプレイヤーに強さの点数を割り当てるものです。分かりやすくするために、イロスコアは他のプレイヤーとの相対的なスコアと考えることができ、数値が高いほど優れたプレイヤーであることを意味します。

第三に、人の手の正確さを測るのに使える方法として、**センチポーン・ロス**があります。これは、チェスエンジンが提案する手と比較して、プレイヤーの手がどれだけ悪いかを評価する戦略です。さらに、最もよく使われる方法論は、実際のエンジンの最良の推奨からプレイヤーがどれだけ乖離しているかを意味する平均センチポーンロスを計算することです。

数学的には、次のように定義できます。

<script>
MathJax = {
  tex: {
    inlineMath: [['$', '$'], ['\\(', '\\)']]
  },
  svg: {
    fontCache: 'global'
  }
};
</script> <script type="text/javascript" id="MathJax-script" async
  src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-svg.js">
</script> 
$$acl =\frac{ \sum\limits_{i=1}^{n} |x - x_i|}{n}$$

ここで、$x$はエンジンの動きに従った後の評価であり、$x_i$はプレーヤーが手を打った後の実際の評価です。

最後に、分析を始める前にいくつかの仮定を定義しておく必要があります。あるプレイヤーの平均損失が$0$であれば、そのプレイヤーはエンジンが提案する手に100%従っていることになります。したがって、損失が大きいほど弱いプレイヤーです。この例では、平均値が$15$より低い場合は不正行為と見なすことにします。

## 分析

では、実際に比較をしてみましょう。

### 前提条件

始める前に、インストールが必要です。

*   [GridDB][1]

パッケージマネージャ経由でインストールした場合は、JDBCコネクタも一緒にインストールされます。他の方法でインストールする場合は、GridDB用のJDBCコネクタを必ずダウンロードしてください。[GridDB JDBC][2]

### R環境のセットアップ

[R][3]と[Stockfish][4]をパソコンにインストールするだけで、簡単にフォローすることができます。私はRバージョン4.2.2、Stockfishバージョン14.1を使っていますが、他のバージョンでも問題なく動作するはずです。このプロジェクトの完全なコードは[このリポジトリ][5]で見ることができます。次に、必要な R パッケージをロードします。

```r
library(dplyr)
library(magrittr)
library(stringr)
library(bigchess)
library(RJDBC)
```

### R解析

エンジン計算のプロセスにはある程度の時間がかかるので、常にアルゴリズムを再実行する必要がないように、結果をデータベースに保存しておくと良いでしょう。この他、自分たちでチェスゲームのデータベースを構築して、プレイしたゲームに関する情報を保存することも可能です。[GridDB][6]は軽量で高速なので、これを利用する予定です。このチュートリアルでは、バージョン5.0.0を使用しています。 また、RJDBC用のドライバとしてgridstore-jdbc-5.1.0を使用しています。RJDBC用のドライバは[こちら][7]からダウンロードすることができます。データベースに接続するために、以下のRコードを使用します。

```r
driver <- JDBC(
  driverClass = "com.toshiba.mwcloud.gs.sql.Driver",
  classPath = "/usr/share/java/gridstore-jdbc-5.1.0.jar"
)
conn <- dbConnect(driver, "jdbc:gs://127.0.0.1:20001/myCluster/public", "admin", "admin")
```

チェスゲームは通常、.pgn 形式で保存され、各プレイヤーのすべての手と、プレイヤーのレーティング、駒の色などの追加情報が格納されています。このプロジェクトでは4つのpgnゲームだけを使いますが、[このウェブサイト][8]では、現役と非役職者の大規模なチェスデータセットをダウンロードすることができます。その上、データを*Data*フォルダに置くだけで、*cheat_detector.R*スクリプトを実行すれば、大規模チェス・データベースのすべての統計と残りのpgn情報が計算されます。チュートリアルを単純化するために、*normal_game.pgn*という1つのマッチだけを取り上げることにします。データを読むには、`bigchess`というパッケージを利用します。

```r
game <- read.pgn(con = file("normal_game.pgn"), stat.moves = F, extract.moves = 0)
> str(game)
'data.frame':   1 obs. of  9 variables:
 $ Event   : chr "Rated Blitz game"
 $ Site    : chr "https://lichess.org/kOMi8fle"
 $ Date    : chr "2022.10.21"
 $ Round   : chr NA
 $ White   : chr "Krye_Kuzhinieri"
 $ Black   : chr "D1stknightmaster"
 $ Result  : Ord.factor w/ 1 level "1-0": 1
 $ Movetext: chr "1. e4 e5 2. g3 Nc6 3. Bg2 Bc5 4. Ne2 Nf6 5. O-O d6 6. c3 Bg4 7. d3 h6 8. Qc2 O-O 9. Nd2 Ne7 10. Nf3 c6 11. d4 B"| __truncated__
 $ NMoves  : num 51
```

さらに、チェスゲームでは、手を書くために様々な表記法を使います。しかし、StockfishはLong Algebraic Notation (LAN)しか受け付けないため、文字列を変換する必要があります。

```r
game_lan <- san2lan(game$Movetext[1])
> game_lan
[1] "e2e4 e7e5 g2g3 b8c6 f1g2 f8c5 g1e2 g8f6 e1g1 d7d6 c2c3 c8g4 d2d3 h7h6 d1c2 e8g8 b1d2 c6e7 d2f3 c7c6 
d3d4 g4f3 g2f3 c5b6 c1e3 e7g6 a1d1 d8c8 a2a4 a7a5 c3c4 f8e8 d4d5 b6e3 f2e3 c6d5 e4d5 e5e4 f3g2 f6g4 c2c3 
c8c5 e2d4 a8c8 b2b3 c5b4 c3b4 a5b4 d1e1 e8e5 d4b5 c8d8 h2h3 g4f6 b5d4 g6e7 g3g4 h6h5 d4f5 e7f5 f1f5 h5g4 
f5e5 d6e5 h3g4 f6g4 g2e4 g7g6 g1g2 f7f5 e4f3 g4f6 e1h1 g8g7 g2f2 e5e4 f3e2 b7b6 h1d1 g6g5 d5d6 f5f4 e3f4 
g5f4 d1d4 f4f3 e2f1 g7f7 f1h3 f7g6 a4a5 b6a5 c4c5 f6e8 d6d7 e8c7 c5c6 g6g5 d4e4 c7d5 e4d4"
```

次に、一手後の各値の点数を取得して、平均的なセンチポーンロスを計算してみましょう。例えば、白が手を打った後、エンジンの評価を得て、その値を記憶しておくのです。要するに、エンジンの深さが違えば、返ってくる評価も違うということです。つまり、エンジンの深さが高いほど、Stockfishが提供する評価はより正確なものになります。ここでは、engine_depthを20としています。

```r
all_moves <- str_split(lan, " ")[[1]]
for (i in seq_along(all_moves)) {
    notation <- trimws(paste(notation, all_moves[i]), which = "left")
    score <- uci_engine(engine_path) %>%
      uci_position(moves = notation) %>%
      uci_go(depth = engine_depth) %>%
      uci_quit() %>%
      uci_parse(filter = "score")

    score <- score * (-1)
    if (i %% 2 == 0) {
      black_scores <- c(black_scores, score)
    } else {
      white_scores <- c(white_scores, score)
    }
  }
```

点数を計算した後、それぞれの手の差を取る必要がある。例えば、白が手を打つ前と打った後の評価の差を求めます。これで損失が分かります。

<div class="clipboard">
  <pre><code class="language-R">black_difference = white_scores + black_scores
white_difference = white_scores + dplyr::lag(black_scores)</code></pre>
</div>

非常に稀ですが、エンジンがすべての可能性を考慮していないために、正の値が得られることもあります。ここでは、簡略化のため、0より大きい値、つまり、人がエンジンを上回った値を0として変換しています。

```r
white_difference = ifelse(white_difference > 0 | is.na(white_difference), 0, white_difference),
black_difference = ifelse(black_difference > 0 | is.na(black_difference), 0, black_difference)
```

最後に、各選手の最善手のパーセンテージを求めましょう。そのためには、目的の範囲を指定することで、データを切り口に分けることができます。このチュートリアルでは、0-25の範囲にある手を正確、25-75を平均、75以上を悪い手と呼ぶことにします。

```r
limit_ranges = c(0, 25, 75, Inf)
limit_names = c("Precise Move", "Average Move", "Bad Move")
white_cuts = cut(white_difference * -1, breaks = limit_ranges, include.lowest = T, labels = limit_names)
black_cuts = cut(black_difference * -1, breaks = limit_ranges, include.lowest = T, labels = limit_names)
```

そうすると、パーセンテージと損失は以下のように計算できます。

```r
# Percentages
white_percentages <- prop.table(table(game_results$white_cuts))
black_percentages <- prop.table(table(game_results$black_cuts))

# Loss
white_average_cp <- abs(mean(game_results$white_difference))
black_average_cp <- abs(mean(game_results$black_difference))
```

## 結果

上の解析は無事終了し、これでチェス・データベースが手に入りました。`SELECT * FROM chess_table_depth_20` を実行すると、プレイされた各ゲームについて、さまざまな情報を得ることができます。データベースには、イベントの名前、ゲームが行われた場所、日付、ラウンド、 プレイヤーの名前、そして各プレイヤーのセンチポーン統計などの情報が格納されています。以下は、データベースのサンプルです。

|          Event|Site|Date|Round|White|Black|Result|Movetext|NMoves|white_stats|black_stats|white_average_cp|black_average_cp|
|:----|:----|:----|:----|:----|:----|:----|:----|:----|:----|:----|:----|:----|
|          Champions Chess Tour Opera Euro Rapid - Prelims 2021|Chess.com|2021.02.07|10|Carlsen, Magnus|Nakamura, Hikaru|1-0|1. d4 Nf6 2. c4 e6...|33|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.7...|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0....|19.3030303030303|31.2727272727273|
|          Sinquefield Cup 2022|Chess.com|2022.09.04|03|Carlsen, Magnus|Niemann, Hans Moke|0-1|1. d4 Nf6 2. c4 e6 3. Nc3 Bb4 4. g3 O-O 5....|57|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.6....|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.7894736....|28.0175438596491|20.4736842105263|
|          Rated Blitz game|[<span style="color:#905">https://lichess.org/kOMi8fle</span>](https://lichess.org/kOMi8fle)|2022.10.21|NA|Krye_Kuzhinieri|D1stknightmaster|1-0|1. e4 e5 2. g3 Nc6 3...|51|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.54....|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.....|213.039215686275|223.56862745098|
|          Casual Correspondence game|[<span style="color:#905">https://lichess.org/gwhvMXUI</span>](https://lichess.org/gwhvMXUI)|2022.10.25|NA|Krye_Kuzhinieri|lichess AI level 8|0-1|1. e4 e5 2....|23|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.52....|c(<span style="color:#905;background-color:#ddd">`Precise Move`</span> = 0.826....|61.0434782608696|13|

では、データを解析して、モデルの性能をテストしてみましょう。以下は、私がLichessでオンラインプレイしたゲームです。私と対戦相手が不正をしていないことは分かっているので、これを使ってモデルをテストできます。

<iframe src="https://lichess.org/embed/game/kOMi8fle?theme=auto&bg=auto" width=600 height=397 frameborder=0></iframe>

`SELECT * FROM chess_table_depth_20 WHERE Black == 'D1stknightmaster'` を実行して、GridDBからゲームを取得することで、データのスコアをフィルタリングすることができます。この結果、以下のような結果が得られます。

|<span style="font-weight:var(--base-text-weight-semibold, 600)">Player</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Precise Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Bad Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Loss</span>|
|:----|:----|:----|:----|:----|
|        White|55%|8%|37%|<span style="font-weight:var(--base-text-weight-semibold, 600)">213.0</span>|
|        Black|43%|26%|31%|<span style="font-weight:var(--base-text-weight-semibold, 600)">223.5</span>|

第二試合は、チャンピオンシップ・チェス・ツアー・オペラ・ユーロ・ラピッド・トーナメントで、世界最強のチェスプレイヤー二人が対戦した試合です。このゲームでは誰も不正をしていないことは分かっていますが、チェスのエリートの平均的なセンチポーンロスがどの程度なのかを知りたいのです。
<iframe src="https://lichess.org/embed/game/1gIiW0OQ?theme=auto&bg=auto#65" width=600 height=397 frameborder=0></iframe>

以下のクエリ`SELECT * FROM chess_table_depth_20 WHERE Black == 'Nakamura, Hikaru'`を実行することでデータをフィルタリングすることができます。

|<span style="font-weight:var(--base-text-weight-semibold, 600)">Player</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Precise Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Bad Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Loss</span>|
|:----|:----|:----|:----|:----|
|        White|79%|12%|9%|<span style="font-weight:var(--base-text-weight-semibold, 600)">19.30</span>|
|        Black|79%|12%|9%|<span style="font-weight:var(--base-text-weight-semibold, 600)">31.27</span>|

次の試合は、コンピュータと対戦した試合です。この場合、黒が不正をしたことを検出したいので、非常に低い**acl**を期待します。
<iframe src="https://lichess.org/embed/game/gwhvMXUI?theme=auto&bg=auto" width=600 height=397 frameborder=0></iframe>

SELECT * FROM chess_table_depth_20 WHERE Black == 'lichess AI level 8'`を実行して、データをフィルタリングしています。その結果、以下のようになります。

|<span style="font-weight:var(--base-text-weight-semibold, 600)">Player</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Precise Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Bad Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Loss</span>|
|:----|:----|:----|:----|:----|
|        White|52%|22%|26%|<span style="font-weight:var(--base-text-weight-semibold, 600)">61.04</span>|
|        Black|83%|13%|4%|<span style="font-weight:var(--base-text-weight-semibold, 600)">13.00</span>|

ここで、黒駒を使用しているプレイヤーは、損失の値が許容範囲より小さいので、明らかに不正をしたことがわかります。

最後に、世界チャンピオン、マンガ・カールセンとアメリカの若き天才、ハンス・ニーマンとの悪名高い一局を一緒に分析しましょう。この対局は、カールセンがニーマンの不正を告発したことで特に重要な意味を持ちます。この話題はいろいろと言われていますが、Chess.comによるこの[レポート][9]は、まさにこのゲームでハンスが不正を働いたとは考えていません。しかし、せっかくモデルを構築したので、それをテストしてみましょう。`SELECT * FROM chess_table_depth_20 WHERE Black == 'Niemann, Hans Moke'`を実行して、データをフィルタリングします。
<iframe src="https://lichess.org/embed/game/jMaLMDvn?theme=auto&bg=auto" width=600 height=397 frameborder=0></iframe>

|<span style="font-weight:var(--base-text-weight-semibold, 600)">Player</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Precise Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Bad Move</span>|<span style="font-weight:var(--base-text-weight-semibold, 600)">Average Loss</span>|
|:----|:----|:----|:----|:----|
|        White|65%|23%|12%|<span style="font-weight:var(--base-text-weight-semibold, 600)">28.01</span>|
|        Black|79%|14%|7%|<span style="font-weight:var(--base-text-weight-semibold, 600)">20.47</span>|

したがって、カールセンは全体的に良い一日ではなかったし、ニーマンのパフォーマンスも並大抵のものではなかったと主張できます。しかし、このテクニックは選択的不正行為にはうまく機能しません。このモデルを改善するために、この記事の結論部分でいくつかの有用なアイデアを見つけることができます。

最後に、すべてのプレーヤーが互いにどのように比較しているかを表示したいと思います。下の図は、エンジンが世界チャンピオンを明らかに上回っていることが分かります。しかし、最大の違いは、常に最善の手を打つということではなく、単純なオンラインエンジンがいかに稀にしかミスをしないかということです。しかも、私のようなアマチュア・プレイヤーは、平均して40％の確率で悪い手を打っているのです。

[<img src="https://griddb.net/en/wp-content/uploads/2022/12/comparision.png" alt="" width="791" height="362" class="aligncenter size-full wp-image-29012" />][10]

## 結論

今回は、チェスにおけるあからさまな不正行為の検出に焦点を当てました。我々が作成した統計モデルは単純ですが、プレイヤーがエンジンの動きのほとんどに従うような場合には、良い結果を得ることができます。しかし、このモデルは、選択的な不正行為や賢い不正行為にはうまく機能しません。なぜなら、優れたプレイヤーは、すべてのエンジンの動きをコピーする必要はなく、重要な瞬間にそのうちのいくつかの動きをコピーする必要があるからです。このモデルを改善するために、次のようなことができます。

*   2000-2100、2100-2200、...といった異なるバケットの **acl** スコアのグループを作成し、類似したプレーヤーを比較します
*   複数のゲームにおけるプレーヤーの **acl** スコアを作成し、異常値を観察するために比較します
*   **acl** の閾値を最適化します。この実験では15を使用したが、値は変更可能です。値が小さければ小さいほど、より高い信頼性で不正行為者を捕まえることができ、逆に値が大きいと誤検出（実際には不正行為をしていないのに、不正行為をしていると非難すること）を引き起こす可能性があります

最後に、統計からは逃げられないので、不正は避け、自分の力で人と競い合うことを楽しんでください。

 [1]: https://docs.griddb.net/latest/gettingstarted/using-apt/
 [2]: https://github.com/griddb/jdbc
 [3]: https://cran.r-project.org/
 [4]: https://stockfishchess.org/download/
 [5]: https://github.com/KryeKuzhinieri/Catching-a-Chess-Cheater-Using-R-and-GridDB
 [6]: https://docs.griddb.net/gettingstarted/using-apt/
 [7]: https://search.maven.org/search?q=a:gridstore-jdbc
 [8]: https://www.pgnmentor.com/files.html
 [9]: https://www.chess.com/blog/CHESScom/hans-niemann-report
 [10]: https://griddb.net/en/wp-content/uploads/2022/12/comparision.png