3目並べ：ミニマックス法での評価

Question

コードの写し書きを、「python ではじめるアルゴリズム入門」(翔泳社)からしているのですが、

打ち手の評価を行う minmax 関数内の下記の check 関数を用いて3目並んだ時点での
終了条件の記述の挙動がいまひとつわからず... minmax関数での、勝ちを 1, 負けを -1,
引き分けを 0 打ち手の評価値としていることは理解できるのですが、そのうえで、評価値を
どこにどのように return されるのでしょうか？

def minmax(p1, p2, turn):
    if check(p2):　#3目並びをは判定する check 関数を呼び出し
        if turn:
            return 1 #勝ち
        else:
            return -1 #負け
    board = p1 | p2
    if board == 0b111111111:
        return 0 #引き分け


#以下省略

minmax関数の呼び出し元の play 関数内で参照すると、 r の内包表記の一部として return されている
のですが、ここの挙動が具体的によくわからず、何か手がかりをご教示いただければ幸いです。

def play(p1, p2, turn):
#先行部分省略
    w = [i for i in range(9) if (board & (1 << i)) == 0] #打てる領域(="0") を９bitのビット列から順次探索
    r = [minmax(p2, p1 | (1 << i ), True) for i in w] # 領域の評価
    j = w[r.index(max(r))] #評価の一番高いものを確定し、
    play(p2, p1 | (1 << j ), not turn)  #打ち手とする
#以下省略

import random
import math

goal = [
    0b111000000, 0b000111000, 0b000000111, 0b100100100,
    0b010010010, 0b001001001, 0b100010001, 0b001010100
]

#3つ並んだか判定

def check(player):
    for mask in goal:
        if player & mask == mask:
            return True
    return False

def minmax(p1, p2, turn):
    if check(p2):
        if turn:
            return 1
        else:
            return -1
        
    board = p1 | p2
    if board == 0b111111111:
        return 0
    
    w = [i for i in range(9) if (board & (1<< i )) == 0]

    if turn:
        return min([minmax(p2, p1 | (1 << i ), not turn) for i in w])
    else:
        return max([minmax(p2, p1 | (1 << i ), not turn) for i in w])


def play(p1, p2, turn):

    if check(p2): 
        print("settled", [bin(p1), bin(p2)])
        return
    
    board = p1 | p2
    print("current_board: ", bin(board))
    
    if board == 0b111111111:
        print([bin(p1), bin(p2), "draw"])
        return
    w = [i for i in range(9) if (board & (1 << i)) == 0]
    r = [minmax(p2, p1 | (1 << i ), True) for i in w]
    j = w[r.index(max(r))]
    play(p2, p1 | (1 << j ), not turn) 
    
play(0, 0, True)

Answer 1

minmax関数がよくわからないという質問で良いですか…？

#以下省略 としてしまっていますが、多分ここが一番重要では無いかと

    if turn:
        return min([minmax(p2, p1 | (1 << i ), not turn) for i in w])
    else:
        return max([minmax(p2, p1 | (1 << i ), not turn) for i in w])

• w はプレイヤーが 置ける位置
• xxx for i in w で i に プレイヤーが置ける位置を代入しながらループを回す
• p1 | (1 << i ) p1 が i に石を置く
• minmax(p2, placed_p1, not turn) 次は p2 が置くターンですが、実装を簡略化するため、p2と p1 を交換して、p1にプレイさせます。
• turn がコードを難読化させているような気がします。今、プレイヤーを交換したので、評価が逆転します。評価が逆転したことを伝えるために、turnを使っています

こう書けばturnを無くせそうです(デバッグしていないので間違っているかもしれませんが…)
別のアルゴリズムに置き換わっている可能性があるので、撤回します

def minmax(p1, p2):
    if check(p2):
        return -1

    board = p1 | p2
    if board == 0b111111111:
        return 0

    w = [i for i in range(9) if (board & (1<< i )) == 0]

    return max([-minmax(p2, p1 | (1 << i )) for i in w])

Comments

[step_by_step]

質問内容が漠然としている中、示唆いただきありがとうございます。
引き続き理解が曖昧なところがあり、ご容赦いただきたいのですが、

挙げていただいた箇所で

`if turn:` では   `min()` で返し、
`else: ` では `max()` で返すのは、何に対応しているのでしょうか。

min と max で交互に行っていくのは理解できているのですが、
順番としての必然性はありますでしょうか？
(` if turn: ` を`max() ` で返し、`else:` を `min()`で返す形で
始めても基本的には同じことでしょうか？)

turn をなくす記述まで理解が追いついておらず、恐縮です。

[step_by_step]

連投すみません、上記の質問があまりにも漠然としていたため、
聞き方を変えさせていただきます。

turn がそもそもこのコードで果たしている役割の理解が曖昧だと思うのですが、
こちらは

turn = True のときは先攻のターン
turn = False のときは後攻のターン

というのを管理しているフラグという理解で合っていますでしょうか？

[maai]

（ソースコードが正しいという前提で書きますが…）

「play(0, 0, True)」で始まって、True、Falseと交互に変わっているため、
play関数は、「turn = True のときは先攻のターン」という考え方で正しそうです。

minmax関数は、後攻でも「minmax(p2, p1 | (1 << i ), True)」と turn = True で呼び出しているため、
turnが先攻か後攻かを表している訳では無いことが分かります。
「if check(p2): if turn: return 1」から、
p2 が揃ったら turn = True の時は嬉しいようです。
「turn = True のときは p2 が評価したい打ち手の盤面」が近いのかな…と思っています。

- - -

自分も混乱気味なので、整理してみました。turn の真偽を関数名に移動させました。
minmax_false は評価したくない相手が揃ってしまったので-1を返している、とも取れるように見えます

```
def minmax_true(p1, p2):
if check(p2):
return 1

board = p1 | p2
if board == 0b111111111:
return 0

w = [i for i in range(9) if (board & (1<< i )) == 0]

return min([minmax_false(p2, p1 | (1 << i )) for i in w])

def minmax_false(p1, p2):
if check(p2):
return -1

board = p1 | p2
if board == 0b111111111:
return 0

w = [i for i in range(9) if (board & (1<< i )) == 0]

return max([minmax_true(p2, p1 | (1 << i )) for i in w])
```

[step_by_step]

咀嚼するのに時間がかかってしまいましたが、
play 関数と、minmax関数で turn のコンテクストが違うことが理解できました。
関数の引数名は原著ママなのですが、こういった構成でしたら、それぞれの関数で
引数の名前は変えたほうが良いのかもという気付きも得られました。
ご示唆のほど、ありがとうございました！