Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python

Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python
Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python

Если вы хотя бы отдалённо интересуетесь играми и не прожили последнюю пару лет в тайге, то, вероятно, слышали что-нибудь о Cyberpunk 2077. После долгого ожидания она наконец вышла! И в ней есть мини-игра про взлом! И чем больше получишь в ней очков, тем ценнее приз! Может ли магия Python дать нам преимущество в этом жестоком Нете? Разумеется.

Краткое описание мини-игры: игроку даётся квадратная матрица и одна или несколько последовательностей шестнадцатеричных чисел, а также буфер определённой длины. Цель игрока — завершить наибольшее количество последовательностей, выбирая столько узлов, сколько позволяет буфер. Каждая последовательность заполняется значением, если выбранный узел является следующим узлом последовательности. В начале игры можно выбрать любое из значений в первой строке матрицы. После этого в каждом ходе можно попеременно выбирать N-ный столбец/строку, где N — индекс последнего выбранного значения. Если это ужасное описание вам не помогло, то более подробное можно прочитать здесь.

Учитываются все допустимые пути, а окончательное количество очков каждого пути вычисляется в зависимости от того, сколько последовательностей было завершено при его прохождении. Путь с наибольшим количеством очков затем выводится на экран. К сожалению, мой алгоритм не особо интересен и эффективен. Однако он должен быть достаточно быстр, чтобы решить любую из мини-игр Cyberpunk за несколько секунд, и этого вполне хватает! Уверен, что есть какие-то простые способы ускорения выполнения скрипта, но я решил поделиться уже имеющимися результатами, и обновлять пост по мере поступления новых идей и предложений.

Начнём с компонентов игры:

  • Матрица кода: многомерный массив, содержащий шестнадцатеричные значения (узлы) — «игровое поле»
    1
    2
    3
    4
    5
    6
    7
    code_matrix = [
        [<span class="hljs-number">0x1c</span>, <span class="hljs-number">0xbd</span>, <span class="hljs-number">0x55</span>, <span class="hljs-number">0xe9</span>, <span class="hljs-number">0x55</span>],
        [<span class="hljs-number">0x1c</span>, <span class="hljs-number">0xbd</span>, <span class="hljs-number">0x1c</span>, <span class="hljs-number">0x55</span>, <span class="hljs-number">0xe9</span>],
        [<span class="hljs-number">0x55</span>, <span class="hljs-number">0xe9</span>, <span class="hljs-number">0xe9</span>, <span class="hljs-number">0xbd</span>, <span class="hljs-number">0xbd</span>],
        [<span class="hljs-number">0x55</span>, <span class="hljs-number">0xff</span>, <span class="hljs-number">0xff</span>, <span class="hljs-number">0x1c</span>, <span class="hljs-number">0x1c</span>],
        [<span class="hljs-number">0xff</span>, <span class="hljs-number">0xe9</span>, <span class="hljs-number">0x1c</span>, <span class="hljs-number">0xbd</span>, <span class="hljs-number">0xff</span>]
    ]
  • Буфер: число, обозначающее максимальное количество выбираемых координат
    1
    buffer_size = <span class="hljs-number">7</span>
  • Координата: точка в матрице кода
  • Путь: упорядоченный набор уникальных координат, по которым проходил пользователь
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    <span class="hljs-comment"># The same coordinate can't be chosen more than once per path</span>
    <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DuplicatedCoordinateException</span>(<span class="hljs-params">Exception</span>):</span>
        <span class="hljs-keyword">pass</span>
     
    <span class="hljs-comment"># All paths match the following pattern:</span>
    <span class="hljs-comment"># [(0, a), (b, a), (b, c), (d, c), ...]</span>
    <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Path</span>():</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span>(<span class="hljs-params">self, coords=[]</span>):</span>
            self.coords = coords
     
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__add__</span>(<span class="hljs-params">self, other</span>):</span>
            new_coords = self.coords + other.coords
            <span class="hljs-keyword">if</span> any(map(<span class="hljs-keyword">lambda</span> coord: coord <span class="hljs-keyword">in</span> self.coords, other.coords)):
                <span class="hljs-keyword">raise</span> DuplicatedCoordinateException()
            <span class="hljs-keyword">return</span> Path(new_coords)
     
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__repr__</span>(<span class="hljs-params">self</span>):</span>
            <span class="hljs-keyword">return</span> str(self.coords)
  • Последовательность: пути, дающие при завершении награды различного качества
    1
    2
    3
    4
    5
    6
    sequences = [
        [<span class="hljs-number">0x1c</span>, <span class="hljs-number">0x1c</span>, <span class="hljs-number">0x55</span>],
        [<span class="hljs-number">0X55</span>, <span class="hljs-number">0Xff</span>, <span class="hljs-number">0X1c</span>],
        [<span class="hljs-number">0xbd</span>, <span class="hljs-number">0xe9</span>, <span class="hljs-number">0xbd</span>, <span class="hljs-number">0x55</span>],
        [<span class="hljs-number">0x55</span>, <span class="hljs-number">0x1c</span>, <span class="hljs-number">0xff</span>, <span class="hljs-number">0xbd</span>]
    ]
  • Очки: вычисления, которые можно настраивать, чтобы отдавать приоритет разным наградам
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SequenceScore</span>():</span>
     
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span>(<span class="hljs-params">self, sequence, buffer_size, reward_level=<span class="hljs-number">0</span></span>):</span>
            self.max_progress = len(sequence)
            self.sequence = sequence
            self.score = <span class="hljs-number">0</span>
            self.reward_level = reward_level
            self.buffer_size = buffer_size
     
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">compute</span>(<span class="hljs-params">self, compare</span>):</span>
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> self.__completed():
                <span class="hljs-keyword">if</span> self.sequence[self.score] == compare:
                    self.__increase()
                <span class="hljs-keyword">else</span>:
                    self.__decrease()
     
        <span class="hljs-comment"># When the head of the sequence matches the targeted node, increase the score by 1</span>
        <span class="hljs-comment"># If the sequence has been completed, set the score depending on the reward level</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__increase</span>(<span class="hljs-params">self</span>):</span>
            self.buffer_size -= <span class="hljs-number">1</span>
            self.score += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> self.__completed():
                <span class="hljs-comment"># Can be adjusted to maximize either:</span>
                <span class="hljs-comment">#   a) highest quality rewards, possibly lesser quantity</span>
                self.score = <span class="hljs-number">10</span> ** (self.reward_level + <span class="hljs-number">1</span>)
                <span class="hljs-comment">#   b) highest amount of rewards, possibly lesser quality</span>
                <span class="hljs-comment"># self.score = 100 * (self.reward_level + 1)</span>
     
        <span class="hljs-comment"># When an incorrect value is matched against the current head of the sequence, the score is decreased by 1 (can't go below 0)</span>
        <span class="hljs-comment"># If it's not possible to complete the sequence, set the score to a negative value depending on the reward </span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__decrease</span>(<span class="hljs-params">self</span>):</span>
            self.buffer_size -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> self.score &gt; <span class="hljs-number">0</span>:
                self.score -= <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> self.__completed():
                self.score = -self.reward_level - <span class="hljs-number">1</span>
     
        <span class="hljs-comment"># A sequence is considered completed if no further progress is possible or necessary</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__completed</span>(<span class="hljs-params">self</span>):</span>
            <span class="hljs-keyword">return</span> self.score &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> self.score &gt;= self.max_progress <span class="hljs-keyword">or</span> self.buffer_size &lt; self.max_progress - self.score
     
    <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">PathScore</span>():</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span>(<span class="hljs-params">self, path, sequences, buffer_size</span>):</span>
            self.score = <span class="hljs-literal">None</span>
            self.path = path
            self.sequence_scores = [SequenceScore(sequence, buffer_size, reward_level) <span class="hljs-keyword">for</span> reward_level, sequence <span class="hljs-keyword">in</span> enumerate(sequences)]
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">compute</span>(<span class="hljs-params">self</span>):</span> <span class="hljs-comment"># Returns the sum of the individual sequence scores</span>
            <span class="hljs-keyword">if</span> self.score != <span class="hljs-literal">None</span>:
                <span class="hljs-keyword">return</span> self.score
            <span class="hljs-keyword">for</span> row, column <span class="hljs-keyword">in</span> self.path.coords:
                <span class="hljs-keyword">for</span> seq_score <span class="hljs-keyword">in</span> self.sequence_scores:
                    seq_score.compute(code_matrix[row][column])
            self.score = sum(map(<span class="hljs-keyword">lambda</span> seq_score: seq_score.score, self.sequence_scores))
            <span class="hljs-keyword">return</span> self.score

Генерация пути очень похожа на обход графа поиска в глубину. Единственное значимое отличие заключается в том, что доступные узлы варьируются в зависимости от текущего хода и координат предыдущего узла.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<span class="hljs-comment"># Returns all possible paths with size equal to the buffer</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">generate_paths</span>(<span class="hljs-params">buffer_size</span>):</span>
    completed_paths = []
 
    <span class="hljs-comment"># Return next available row/column for specified turn and coordinate.</span>
    <span class="hljs-comment"># If it's the 1st turn the index is 0 so next_line would return the </span>
    <span class="hljs-comment"># first row. For the second turn, it would return the nth column, with n</span>
    <span class="hljs-comment"># being the coordinate's row</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">candidate_coords</span>(<span class="hljs-params">turn=<span class="hljs-number">0</span>, coordinate=(<span class="hljs-number">0</span>,<span class="hljs-number">0</span>)</span>):</span>
        <span class="hljs-keyword">if</span> turn % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> [(coordinate[<span class="hljs-number">0</span>], column) <span class="hljs-keyword">for</span> column <span class="hljs-keyword">in</span> range(len(code_matrix))]
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> [(row, coordinate[<span class="hljs-number">1</span>]) <span class="hljs-keyword">for</span> row <span class="hljs-keyword">in</span> range(len(code_matrix))]
 
    <span class="hljs-comment"># The stack contains all possible paths currently being traversed.</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_walk_paths</span>(<span class="hljs-params">buffer_size, completed_paths, partial_paths_stack = [Path()], turn = <span class="hljs-number">0</span>, candidates = candidate_coords()</span>):</span>
    
        path = partial_paths_stack.pop()
        
        <span class="hljs-keyword">for</span> coord <span class="hljs-keyword">in</span> candidates:
            <span class="hljs-keyword">try</span>:
                new_path = path + Path([coord])
            
            <span class="hljs-comment"># Skip coordinate if it has already been visited</span>
            <span class="hljs-keyword">except</span> DuplicatedCoordinateException:
                <span class="hljs-keyword">continue</span>
 
            <span class="hljs-comment"># Full path is added to the final return list and removed from the partial paths stack</span>
            <span class="hljs-keyword">if</span> len(new_path.coords) == buffer_size:
                completed_paths.append(new_path)
            <span class="hljs-keyword">else</span>: <span class="hljs-comment"># Add new, lengthier partial path back into the stack</span>
                partial_paths_stack.append(new_path)
                _walk_paths(buffer_size, completed_paths, partial_paths_stack, turn + <span class="hljs-number">1</span>, candidate_coords(turn + <span class="hljs-number">1</span>, coord))
 
    _walk_paths(buffer_size, completed_paths)
    <span class="hljs-keyword">return</span> completed_paths

Давайте запустим код и убедимся, что всё работает правильно. Хотя большинство мини-игр со взломом протокола имеют рандомизированные значения, в квесте «Spellbound» используется фиксированное состояние, и наилучшее решение уже известно. Оно создано GamerJournalist:

Решаем мини-игру про взлом протокола в Cyberpunk 2077 за 50 строк на Python

1
2
3
4
paths = [(path, PathScore(path, sequences, buffer_size).compute()) <span class="hljs-keyword">for</span> path <span class="hljs-keyword">in</span> generate_paths(buffer_size)]
max_path = max(paths, key=<span class="hljs-keyword">lambda</span> path: path[<span class="hljs-number">1</span>])
<span class="hljs-comment"># [(0, 1), (2, 1), (2, 3), (1, 3), (1, 0), (4, 0), (4, 3)] -&gt; Should traverse 3rd and 4th sequences, finishes in ~3 seconds</span>
print(max_path[<span class="hljs-number">0</span>])

Успех! Из любопытства я решил увеличивать размер буфера, пока не смогу найти путь, выполняющий все последовательности. Учтите, что для вычисления результата может понадобиться какое-то время, поскольку алгоритм проходит по всем возможным путям длиной 11.

1
2
3
4
5
6
buffer_size = <span class="hljs-number">11</span>
paths = [(path, PathScore(path, sequences, buffer_size).compute()) <span class="hljs-keyword">for</span> path <span class="hljs-keyword">in</span> generate_paths(buffer_size)]
max_path = max(paths, key=<span class="hljs-keyword">lambda</span> path: path[<span class="hljs-number">1</span>])
 
<span class="hljs-comment"># [(0, 0), (1, 0), (1, 3), (3, 3), (3, 1), (0, 1), (0, 3), (2, 3), (2, 0), (4, 0), (4, 2)] -&gt; Should traverse all sequences, finishes in ~40 seconds</span>
print(max_path[<span class="hljs-number">0</span>], max_path[<span class="hljs-number">1</span>])

Хорошо, а теперь займёмся оптимизацией! Будем предполагать, что существует хотя бы один путь с неотрицательным количеством очков. Благодаря этому мы можем прерывать обхождение частичного пути, если его текущее количество очков (скорректированное в соответствии с размером буфера и текущим ходом) меньше 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">generate_paths</span>(<span class="hljs-params">...</span>):</span>
    ...
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_walk_paths</span>(<span class="hljs-params">...</span>):</span>
    ...
 
                <span class="hljs-comment"># Full path is added to the final return list and removed from the partial paths stack</span>
                <span class="hljs-keyword">if</span> len(new_path.coords) == buffer_size:
                    completed_paths.append(new_path)
                <span class="hljs-comment"># If the partial path score is already lower than 0 we should be able to safely stop traversing it</span>
                <span class="hljs-keyword">elif</span> PathScore(new_path, sequences, buffer_size).compute() &lt; <span class="hljs-number">0</span>:
                    <span class="hljs-keyword">continue</span>
                <span class="hljs-keyword">else</span>: <span class="hljs-comment"># Add new, lengthier partial path back into the stack</span>
                    partial_paths_stack.append(new_path)
                    _walk_paths(buffer_size, completed_paths, partial_paths_stack, turn + <span class="hljs-number">1</span>, candidate_coords(turn + <span class="hljs-number">1</span>, coord))
    ...

Давайте попробуем получить исходный результат заново с буфером длиной 7:

1
2
3
4
5
buffer_size = <span class="hljs-number">7</span>
paths = [(path, PathScore(path, sequences, buffer_size).compute()) <span class="hljs-keyword">for</span> path <span class="hljs-keyword">in</span> generate_paths(buffer_size)]
max_path = max(paths, key=<span class="hljs-keyword">lambda</span> path: path[<span class="hljs-number">1</span>])
<span class="hljs-comment"># [(0, 1), (2, 1), (2, 3), (1, 3), (1, 0), (4, 0), (4, 3)] -&gt; Should traverse 3rd and 4th sequences, finishes instantly</span>
print(max_path[<span class="hljs-number">0</span>])

Сработало! Новое решение заметно быстрее, но буфер длиной 7 уже и так вычислен довольно быстро, поэтому трудно ощутить ускорение. Посмотрим, как проявляет себя оптимизация при вычислении пути с наибольшей наградой.

1
2
3
4
5
buffer_size = <span class="hljs-number">7</span>
paths = [(path, PathScore(path, sequences, buffer_size).compute()) <span class="hljs-keyword">for</span> path <span class="hljs-keyword">in</span> generate_paths(buffer_size)]
max_path = max(paths, key=<span class="hljs-keyword">lambda</span> path: path[<span class="hljs-number">1</span>])
<span class="hljs-comment"># [(0, 0), (1, 0), (1, 3), (3, 3), (3, 1), (0, 1), (0, 3), (2, 3), (2, 0), (4, 0), (4, 2)] -&gt; Should traverse all sequences, finishes in ~13 seconds</span>
print(max_path[<span class="hljs-number">0</span>])

Ускорение почти в три раза благодаря добавлению двух строк кода. Совсем неплохо. Вероятно, существуют и другие простые возможности оптимизации, поэтому я, может быть, через неделю дополню пост. Ну а на этом всё. Присылайте свои предложения по улучшению качества/производительности кода!

источник