【ボードゲーム】X目並べは先手必勝!?

公開日: : 最終更新日:2018/06/07 ボードゲーム , , , ,

ゲームにおける「Fairness」という考え方があります。

これは、ある程度スキルがあるプレイヤーが勝つようにする「公正さ」と、先手必勝ではなくお互いに最善手を指し続けたとときに、いかに引き分けに近づくことができるかという「公平さ」がゲームにおいては重要であるという考え方です。

先手必勝、後手必勝のゲームはあまり面白くないですよね。

ということで、今回は、以下の様々なボードゲームについて、先後どちらが必勝なのか?引き分けか?あるいは、分からないかということを調べてみました。

tic-tac-toe(三目並べ)

tic-tac-toe は、日本語で三目並べのことです。アメリカでは tic-tac-toe と呼ばれています。

2006年に Aaron Gordon によって「A general algorithm for tic-tac-toe board evaluation」という論文の中で、tic-tac-toe は先手必勝(引き分け以上)になるように解くことができるアルゴリズムが報告されている。

論文(PDFファイル)はこちらです。

https://dl.acm.org/citation.cfm?id=1089188

Connect Four(四目並べ)

Connect Four は、日本語で四目並べのことです。

三目並べより複雑になりましたが、これも1988年の L.V.Allis による「A Knowledge-Based Approach of Connect Four: The Game is Over, White to Move Wins」という論文の中で、Connect Four は先手必勝であることが書かれています。

論文(PDFファイル)はこちらです。

http://www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf

Connect 4

GO-MOKU(五目並べ)

次は五目並べです。こちらも、1996年の L.V.Allis による「GO‐MOKU SOLVED BY NEW SEARCH TECHNIQUES」というタイトルの論文で、先手必勝であることが証明されました。ただし、盤の広さが15×15以上の場合という条件があって、13×13だと必ず先手必勝とは限りません

本手法では、強制探索(threat-space search)証明数探索(proof-number search)を用います。強制探索とは、強制手(将棋の王手みたいなもので、五目並べだと3つ連続で並んだら片側は抑えないといけない、といったものです)をもって探索することです。

論文はこちらになります。

https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8640.1996.tb00250.x

アブストラクトです。

Many decades ago, Japanese professional Go‐Moku players stated that Go‐Moku (five‐in‐a‐row on a horizontally placed 15×15 board) is a won game for the player to move first. So far, this claim has never been substantiated by (a tree of) variations or by a computer program. Meanwhile, many variants of Go‐Moku with slightly different rules have been developed. This paper shows that for two common variants, the game‐theoretical value has been established.

Moreover, the Go‐Moku program Victoria is described. It uses two new search techniques: threat‐space search and proof‐number search. One of the results is that Victoria is bound to win against any (optimal) counterplay if it moves first. Furthermore, it achieves good results as a defender against nonoptimally playing opponents. In this contribution we focus on threat‐space search and its advantages compared to conventional search algorithms.

Connect6(六目並べ)

どんどんならべる数が増えていきます(笑)。

六目並べは、交通大学工学部の呉毅成(I-Chen Wu)教授が「A New Family of k-in-a-Row Games」というタイトルの論文で発表した新しいゲームです。

https://link.springer.com/chapter/10.1007%2F11922155_14#page-1

ルールは、黒が最初に1つ置いた後、白黒ともに2つずつ石を置いていきます

そうすることによって、先手必勝の条件が緩和され、より公平なゲームに近づいたといえると思われます。

Almost all games are first person games

最後に、1981年に出た「Almost all games are first person games」という論文を紹介したいと思います。

https://ci.nii.ac.jp/naid/10021842427/

これは、「だいたい全てのゲームは先手が優位である」という意味です。

その理由は、ゲーム木探索における先手の着手可能手(blanching factor) を考えます。先手はその選択したどれか1つで勝てばよいが、後手はその全てにおいて勝たなければいけないので制約条件が付いてしまうため、先手が優位であるといえます。

ここで、オセロの場合は後手が勝つのはなぜか?という疑問がわいてくると思います。それは、オセロの先手の1手目は1通りしかなく(対称のため)、実質後手になるから、という理屈になっているようです。

 

関連記事

【ゲーム木探索】コンピュータにボードゲームをプレイさせる方法。

チェス・将棋・囲碁までもがコンピュータ(人工知能)が人間を超えてしまいました。 では、コンピュ

記事を読む

【人工知能】チェッカーの完全解明について。

ボードゲームの1つである「チェッカー」が完全解明され、お互いに最善手を指し続けると絶対に引き分けにな

記事を読む

2016年11月20日|囲碁フォーカス講座|ストップ!車の後押し

今回は、NHKの囲碁フォーカス講座から2016年11月20日に放送された、三村智保講師による「磨け初

記事を読む

【Game Refinement Theory】ゲームの面白さを数値化する研究について。

ゲームの面白さを数値化するような研究について紹介したいと思います。 ゲーム理論(game th

記事を読む

2017年6月4日|囲碁フォーカス講座|ハサみたい?~星

囲碁フォーカス講座「初段へのスタート、小山竜吾、囲碁ワールドで基礎力アップ」の内容です。 6月

記事を読む

【人工知能】コンピュータチェスの歴史をまとめてみた。

コンピュータチェスは、1997年に DEEP BLUE がグランドマスターのカスパロフを破ったことは

記事を読む

2017年6月11日|囲碁フォーカス講座|ハサみたい?~小目

囲碁フォーカス講座「初段へのスタート、小山竜吾、囲碁ワールドで基礎力アップ」の2017年6月11日の

記事を読む

【藤井聡太】将棋界に若き天才が登場!新たな時代の幕開けか!?

将棋界は、長らく羽生さんの時代が続いていました。しかし、若手棋士の台頭によりタイトルを連続して奪取さ

記事を読む

囲碁|棋譜再生ソフト「MultiGo」をインストールしてみた

NHKの囲碁講座の内容や詰め碁をブログに載せるために、棋譜再生のための囲碁盤ソフトを探していたところ

記事を読む

【Python】pip3 で「cannot import name ‘main’」エラーが出たときの対処法。

Python でライブラリをインストールする際に、pipを使います。

【mecab-python3】parseToNode で surface が正しく取得できないときの対処法。

python3 で mecab-python3 を使うと、parseT

【Python】形態素解析器 Mecab を Linux(Ubuntu)で使ってみた。

Linux の Ubuntu OS に、形態素解析器 Mecab をイ

【Python】NLTK(自然言語処理ライブラリ)を使ってみた。

Python の自然言語処理ライブラリである NLTK を Linux

【Python】OpenCV を使って顔画像を検出してみた。

OpenCV のインストール Numpy のインストール [c

→もっと見る

PAGE TOP ↑