5つ先のNextShapeまで考慮した盤面評価を、全探索しようとした場合の探索時間について

以下のパッチで5つ先のNextShapeまで考慮した盤面評価を、全探索しようとした場合の探索時間について以下のようになった。

※厳密な計測ではなく、ざっくりです

=== 0:00:00.013404 現在のブロックのみ探索対象にすると、盤面評価に約0.010秒かかる === 0:00:00.068382 1つ先のブロックも探索対象にすると、盤面評価に約0.068秒かかる === 0:00:01.887630 2つ先のブロックも探索対象にすると、盤面評価に約1.887秒かかる === 0:01:05.828456 3つ先のブロックも探索対象にすると、盤面評価に約65秒かかる === xxx 4つ先のブロックも探索対象にすると、盤面評価に約6540(45分ほど) 秒かかる（計測できず） === xxx 5つ先のブロックも探索対象にすると、盤面評価に約6540*40(30hほど) 秒かかる（計測できず）

5つ先のブロックも探索対象にするパッチ

diff --git a/game_manager/block_controller_sample.py b/game_manager/block_controller_sample.py
index 3110401..7820bb5 100644
--- a/game_manager/block_controller_sample.py
+++ b/game_manager/block_controller_sample.py
@@ -37,6 +37,14 @@ class Block_Controller(object):
         # next shape info
         NextShapeDirectionRange = GameStatus["block_info"]["nextShape"]["direction_range"]
         self.NextShape_class = GameStatus["block_info"]["nextShape"]["class"]
+        Next2ShapeDirectionRange = GameStatus["block_info"]["nextShapeList"]["element2"]["direction_range"]
+        self.Next2Shape_class = GameStatus["block_info"]["nextShapeList"]["element2"]["class"]
+        Next3ShapeDirectionRange = GameStatus["block_info"]["nextShapeList"]["element3"]["direction_range"]
+        self.Next3Shape_class = GameStatus["block_info"]["nextShapeList"]["element3"]["class"]
+        Next4ShapeDirectionRange = GameStatus["block_info"]["nextShapeList"]["element4"]["direction_range"]
+        self.Next4Shape_class = GameStatus["block_info"]["nextShapeList"]["element4"]["class"]
+        Next5ShapeDirectionRange = GameStatus["block_info"]["nextShapeList"]["element5"]["direction_range"]
+        self.Next5Shape_class = GameStatus["block_info"]["nextShapeList"]["element5"]["class"]
         # current board info
         self.board_backboard = GameStatus["field_info"]["backboard"]
         # default board definition
@@ -56,21 +64,48 @@ class Block_Controller(object):
                 board = self.getBoard(self.board_backboard, self.CurrentShape_class, direction0, x0)

                 # evaluate board
-                EvalValue = self.calcEvaluationValueSample(board)
+                #EvalValue = self.calcEvaluationValueSample(board)
                 # update best move
-                if EvalValue > LatestEvalValue:
-                    strategy = (direction0, x0, 1, 1)
-                    LatestEvalValue = EvalValue
-
-                ###test
-                ###for direction1 in NextShapeDirectionRange:
-                ###  x1Min, x1Max = self.getSearchXRange(self.NextShape_class, direction1)
-                ###  for x1 in range(x1Min, x1Max):
-                ###        board2 = self.getBoard(board, self.NextShape_class, direction1, x1)
-                ###        EvalValue = self.calcEvaluationValueSample(board2)
-                ###        if EvalValue > LatestEvalValue:
-                ###            strategy = (direction0, x0, 1, 1)
-                ###            LatestEvalValue = EvalValue
+                #if EvalValue > LatestEvalValue:
+                #    strategy = (direction0, x0, 1, 1)
+                #    LatestEvalValue = EvalValue
+
+                # search next
+                for direction1 in NextShapeDirectionRange:
+                    x1Min, x1Max = self.getSearchXRange(self.NextShape_class, direction1)
+                    for x1 in range(x1Min, x1Max):
+                        board1 = self.getBoard(board, self.NextShape_class, direction1, x1)
+                        #EvalValue = self.calcEvaluationValueSample(board2)
+
+                        # search with next2
+                        for direction2 in Next2ShapeDirectionRange:
+                            x2Min, x2Max = self.getSearchXRange(self.Next2Shape_class, direction2)
+                            for x2 in range(x2Min, x2Max):
+                                board2 = self.getBoard(board1, self.Next2Shape_class, direction2, x2)
+
+                                # search with next3
+                                for direction3 in Next3ShapeDirectionRange:
+                                    x3Min, x3Max = self.getSearchXRange(self.Next3Shape_class, direction3)
+                                    for x3 in range(x3Min, x3Max):
+                                        board3 = self.getBoard(board1, self.Next3Shape_class, direction3, x3)
+
+                                        # search with next4
+                                        for direction4 in Next4ShapeDirectionRange:
+                                            x4Min, x4Max = self.getSearchXRange(self.Next4Shape_class, direction4)
+                                            for x4 in range(x4Min, x4Max):
+                                                board4 = self.getBoard(board1, self.Next4Shape_class, direction4, x4)
+                                                EvalValue = self.calcEvaluationValueSample(board4)
+
+                                                # search with next5
+                                                for direction5 in Next5ShapeDirectionRange:
+                                                    x5Min, x5Max = self.getSearchXRange(self.Next5Shape_class, direction5)
+                                                    for x5 in range(x5Min, x5Max):
+                                                        board5 = self.getBoard(board1, self.Next5Shape_class, direction5, x5)
+                                                        EvalValue = self.calcEvaluationValueSample(board5)
+
+                                                        if EvalValue > LatestEvalValue:
+                                                            strategy = (direction0, x0, 1, 1)
+                                                            LatestEvalValue = EvalValue
         # search best nextMove <--

         print("===", datetime.now() - t1)

seigot / tetris

5つ先のNextShapeまで考慮した盤面評価を、全探索しようとした場合の探索時間について #16