2024/07/11 オセロアプリの開発
構成
進め方
作り方の理解
必要な関数とテストケースをt6o_o6t.iconで用意するので、テストが通るように実装!
AIを強くしよう
要件(仮)
BoardのAll Legal Movesを取得できる。
BoardのAll Legal Movesを取得するとき、同時に各Legal Moveに対応するAll Flippable Stonesを取得できる。
BoardのあるPositionへのMoveがLegalであることを検査できる。
BoardのあるPositionにMoveした結果を表すBoard(= Moved Board)を取得できる。
Evaluatorは、BoardのEvaluation Valueを計算できる。
要件(新)
トップダウンで決めないと無駄な作りこみが起こってしまうt6o_o6t.icon
BoardにLegal Moveを渡し、Moved Boardを取得できる。
Boardに対するPut がLegal Putでないとき、Putは失敗する。
code:classes.py
class LegalPut:
def __init__(self, board: Board, position: Position):
self.board = board
self.position = position
def putted_board(self):
#
class Board:
def put(self, where: LegalPut):
def main():
b = Board()
def play():
b = Board()
command = b.player.think()
b.player.put(command)
print(b)
class MyEvaluator:
def __init__(self, board):
self.b = board
def dfs(depth):
if
for legal_put in b.legal_puts:
b.put(legal_put)
self.dfs(depth - 1)
b.undo()
return
def evaluate(depth=5):
class BoardStore:
def __init__(self):
pass
def move_result(self, board):
pass
class LegalMove:
# board: Board
# position: Position
def __init__(self, position: Position):
pass
def is_flippable(self, stone: OppositeSideStone):
pass
def get_all_flippable_stones(self):
return filter(self.is_flippable, board.opposite_side)
class Stone:
# board: Board
# position: Position
class Board:
# same_side: SameSide
# opposite_side: OppositeSide
def get_moved_board(move: Move) -> Board:
# boardの差分管理をどうしよう?
pass
# Interface
class Side:
pass
class OppositeSide(Side):
pass
ユビキタス言語
盤面に関する用語
Row(行線)
Boardの横1列。
Column(列線)
Boardの縦1列。
Diagonal(斜め線)
Boardの斜め1列。
ToRightDiagonal(右下線)
Diagonalのうち、右下向きのもの。
ToLeftDiagonal(左下線)
Diagonalのうち、左下向きのもの。
Line(ライン)
Row、Column、Diagonalの総称
Put(置く)
Stone(石)
Side(側)
Same Side(同じ側)
Opposite Side(違う側)
合法手
Move(着手)
Legal((着手が)合法)
Legal Move(合法手)
All Legal Moves(全合法手)
Flip(裏返す)
BoardのあるPositionへのMoveがLegalであるとき、そのPositionにMoveした場合に発生する、Opposite SideのStoneの裏返しを指す。
Flipping(裏返し)
Flippable(裏返し可能)
あるPositionにMoveした場合に、あるOpposite SideのStoneが裏返されるとき、そのStoneはFlippableであるという。
All Flippable Stones(全裏返し可能石)
あるPositionにMoveしたときにFlippableとなる全ての石。
Moved Board(着手後のBoard)
評価
Evaluation(評価)
あるSideにとってBoardの状況が良いかどうかを計算する作業。
Evaluation Value(評価値)
Boardに対してEvaluationを実施することで得られる数値。
Evaluator(評価手法)
BoardからEvaluation Valueを計算する機構。
複数の種類がある
単一のBoardのみを用いて計算するもの
Evaluator自身を再帰的に適用し、探索の末尾では単一のBoardのみを用いて計算するもの
実際にはこれらの区別は曖昧になるので、区別は設けない?
後者は共通して枝刈りが必要になるので、With Pruningという区別はあってよさそう
Line Hash(ラインハッシュ)
一般的には index と呼ばれる。
プログラミング用語のインデックスと区別するため、異なる呼称を用いた。
Pruning(枝狩り)
Transposition Table(置換表)
Player(プレイヤー)
Bot Player(Botプレイヤー)
Put Position Request
設計メモ
抽象化できそうな(まとめられる)概念
Pruning
Mini Max Pruning
Alpha Beta Pruning
Evaluation
計算に必要な過程は様々あり、段階ごとに抽象化(まとめる)ことができそう
evaluator.evaluate(board) 程度まで抽象化できればOK
Player
position = player.request_put_position(board)
player.id
ValueObject化すべき概念
Position
Row Index
Column Index
Diagonal Index
上位のロジックは、下位の計算がメモ化されているかどうかに興味がない
ただし、メモ化そのものは別の関心事である
たとえば、あるMoveに対するAll Flippable Stonesの計算を考える
AllFlippableStonesMemoStoreのように関心事を切り分ける
上位のロジックからはこのクラスは見えてはならない
Listをイミュータブルに使うことを考えるくらいならBit Board化したほうが良さそうt6o_o6t.icon
設計とコードの区別が曖昧になってきた
設計する上でコードをいきなり書いてはいけないということは本来ないと思う..t6o_o6t.icon
頭の中では日本語でロジックを考えていない or コードでロジックを出力するほうが楽
書いたコードをそのまま採用するとは限らない
Pythonはメソッドを完全にprivateにするのが難しいのでインターフェースへの依存を強制するのが難しい
Modelに依存するコードは、原則ABCとして定義した基底クラスに依存させる
具体クラスをインスタンス化するときも、Type Hintで基底クラスとして取り扱う
Put.init(Board board, Empty where)
Board自体に興味はない
1. board.hashを用いてPuttablity Memoを参照(裏返る位置を特定)
2. board.playerを用いてPlayerを参照(色を確定)
3. 以上の情報を用いて、Diff(EmplaceStoneRequest emplace, FlipStoneRequest flippables[])を作成しdiffに格納
オセロゲームに必要な情報は全てboard.hashから取得できそう
Playersクラスでターンを管理すれば、現在Playerの色のPuttability Memoを取得することで、着手可能位置が全て計算できる
Puttability Memo
黒と白で完全に分けて事前計算することが重要
Move時に差分を使って管理する方式でも破綻なくBoardを扱うにはどうすべきかt6o_o6t.icon
これが分からないと、Boardの管理方式を抽象化できない!
差分で管理すると危険になるのはどういう状況?
異なる局面を複数の変数で管理する仮定はまだ高度すぎるので、Moveが副作用を持つという状況だけを考えてみる
Moveを差分で管理するということは、下記のようになるのでは?
code:example.py
b = Board()
b.move()
Undo / Moveが出来る機能と、現在の局面情報をBoardクラスに持たせれば良いのでは?
code:example.py
class Move:
def to_undo():
return ...
class Board:
def undo():
move_log
pass
def move():
pass
class
Boardを複数の場所から書き換えるときにひどく混乱しそうt6o_o6t.icon
副作用があるとき必ずこれが起こるのでは?
副作用がなければ混乱しない
副作用がある前提で書かれたコードは、下位モジュールから副作用を取り去っても変更なく動作させられる?
副作用がないコードというのは、下記のようなコードだろう
code:not_effect.py
moved_b = move(b)
副作用があるコードがこのような形になっていると、驚きがあるのではないか
メモリを変更しつつ新しい値を返値として返すAPIにはびっくりするt6o_o6t.icon
→ 無理そう
副作用を持つか、持たないかをここで決めないと話が進まない
軽量な履歴オブジェクトから$ O(1)でBoardの状態を取得できないか?
副作用がある前提だと、誤ったプログラムが書かれないことを型で保証するのがかなり難しいt6o_o6t.icon
Boardインスタンスが唯一存在し、それが正しいものとしない限り
たとえばb.player.think()と書いたとして、その戻り値がbにとって本当にLegalかは保証できないから
thinkの実装にはb.player.boardを使うとしたとき、b.player.boardをBoardの別インスタンスb2に向けるようなプログラムを書いた時点で型による制約は意味を無くす
複雑なプログラムを書かなければ良い?t6o_o6t.icon
今回は書き捨てに近い
そんなに難しく考える必要はない?t6o_o6t.icon
理想的な設計を実施しようとすると速度の要件と難易度の要件を
Putを不適切なタイミングでBoardにapplyしてしまう可能性を防ぐのは難しい
Boardが副作用を持つ限り
妥当な解決策は思い浮かばなかった
モデル層でBoardを処理したときには、差分をクラスから返せば良い
返せる位置を特定するクラス
code:eaxmple.py
# Put時の差分を計算
class Put:
def __init__(self, board: Board, position: Position):
self._player
self._position
self._flip_positions = []
@property
def color(self):
return Color.from_side(self.player, SAME_SIDE)
class Color:
@staticmethod
def from_player(player, side):
return player if side == SAME_SIDE else player.flipped()
def flipped():
return !flipped
# TODO: enum
EMPTY = -1
BLACK = 0
WHITE = 1
# Indexの計算は、Sideには関係ない。(∵ 色を反転した際にIndexが変化するため)
class Index:
row = 0
column = 0
diagonal = 0
def apply(self, put):
delta = 0
delta += put.color * (3 ** put.position.row)
delta -= 2 * put.color.flipped * (3 ** put.flip_positions.row)
if put.color == WHITE:
delta *= -1
self.row += delta
def undo(self, put):
pass
@property
def row(self):
return self._row
class Diff:
put_position = Position(0, 0)
flip_position = []
class Board:
index = Index()
applied_diffs = []
def apply(diff):
# ...
self.applied_diffs.append(diff)
def undo():
diff = self.applited_diffs.pop()
def main():