Skip to content

Latest commit

 

History

History
executable file
·
84 lines (70 loc) · 6.45 KB

File metadata and controls

executable file
·
84 lines (70 loc) · 6.45 KB

Patchwork 策略


规则和定义

Patchwork中玩家需要在纽扣数量、拼接方法、时间轴移动等维度上同时计算,以获得更高的分数。但游戏的目标在于获得比对手更高的分数,因此先后手置换、选择性跳过等策略有时可产生更高的分差。我们定义:

分数

  • $VP_1, VP_2$:玩家1和玩家2的总分。
  • $DVP$: 玩家1和玩家2的分数差。

碎布

  • $S$: 总面积,根据规则,每个方格的VP为2。
  • $C$: 购买时所需花费的纽扣数。
  • $T$: 购买后在时间轴上移动的格数。
  • $B$: 每次经过收益纽扣时获得的纽扣数。
  • $R$: 时间轴上剩余未经过的纽扣数。

几何形状

  • 破洞:$1\times1$ 和$1\times2$ 的空白区域
  • 平整:边缘周长尽量小.
  • 贴合:相邻碎布间不产生破洞。

碎布价值

碎布的价值计算需要考虑诸多因素,根据规则,拿取碎布时对游戏结束时能贡献的总VP为: $$ VP_{i}(R) = S_i \times 2 + B_i\times R-C_i $$ 对于$V=0$的碎布,无论在时间轴上何时拿取,对于玩家的总分贡献是固定的,即不依赖于玩家当前在时间轴上所处的位置,而对于$V=0$的碎布则需依赖其所在时间轴上的位置动态计算分数。一般而言$V=0$碎布在时间轴前段能贡献非常高的VP,随着游戏推进逐渐下降,接近终点时降至最低。

单位时间VP

一些具有很高总VP的碎布往往会耗费更多的时间步,由于玩家所能走的总时间步是完全相同的,因此提高每个时间步的平均VP(VP per timestep)即可很大程度保证获得较高的VP。拿取碎布的单位时间VP为: $$ VPPT_i(R) = \frac{Si × 2 + Bi × R − Ci}{T_i} $$

玩家同样可以选择不拿取碎布而直接跳过至对手时间轴前一格,同时可获得对应步数的纽扣,因此每个时间步的基本价值可定义为1VP。在游戏即将结束时,一些碎布的VP会降低至其消耗的时间步数之下,此时直接选择跳过可获得比拿取碎布更高的VP。

策略

==TODO==: 策略举例和画图 Patchwork是一个完全信息的轮流博弈游戏,理论上两方均存在最优解。

全局策略

  • 计算如何拿取碎布,保证在之后有限拿取步骤内,DVP最大。
  • 有限的计算步骤(对人类玩家而言一般1~3次拿取操作内)内计算最大的VPPT。
  • 在不考虑几何拼接、$7\times7$奖励时可直接使用minmax搜索获得最高的DVP对应的拿取策略。
  • 减少越过对手后的时间步。由于在时间轴落后的一方一直可拿取碎布直到越过对手,因此过大的时间步差距会给与对方更多的拿取方式组合,降低DVP。控制尽量恰好落在对手的前一格。
  • 注意时间步为0的碎布。这类碎布给与对手更大的选择空间,他可以在拿取后继续从下一组3块碎布中选择更有利的拿取。
  • 尽量获得特殊分数。特殊分数的获取对双方的分差贡献是双倍的:
    • $1\times1$碎布:分布在时间轴上,因此每块单位碎布都至少会被其中一名玩家拿取,每块的先得者产生4DVP。
    • $7\times7$奖励:当两方均有机会拿取时,先得者产生14DVP。

各阶段策略

  • 早期:

    • 避免过早消耗纽扣购买$B$值为0的碎布。保有一定的纽扣避免无法购买能产生更高DVP的碎布。
    • 选择$C$值低$T$较大的碎布,以保有更多的纽扣。
    • 可选择性跳过以获得足够的纽扣。
    • 在对手纽扣很少时尽量将花费高的可选碎布留下,以强迫对手跳过。
  • 中期:

    • 计算两方3步以内的DVP。
    • 保持拼接的几何形状最优。
    • 平衡纽扣的消耗。每两个收益纽扣间的间隔均为6个时间步。游戏早期会面临纽扣缺乏的问题,为避免频繁选择跳过,应当保留最低纽扣库存。每两个收益纽扣的前端内可选择拿取纽扣消耗较少的碎布,而越过纽扣前可选择值较高的碎布。
    • 评估$1\times1$碎布的价值。如果之前的拼接留下了很多$1\times1$的破洞、或者可获得更高的DVP等。
  • 后期:

    • 即将到达时间轴末端时可选择时间步更高的碎布。时间步较高的碎布往往有更高的分数,利用末端的时间溢出可减小该类碎布的拿取代价。
    • 留意对手可选的碎布。游戏后期由于大量面积已经被拼,很多形状的碎布无法再被选择,因此使对手面临无法拿取碎布时可快速提高DVP。
    • 留意对手是否能够完成$7\times7$。
    • 留意自己是否有机会完成$7\times7$奖励。

特性统计

==TODO== 碎布价值分布和相关性分析

选择跳过

  • 当前三块可选碎布的DVP均很低:直接选择跳过,即使对手选择跳过也仍然跳过。维持僵局直到遇到$1\times1$,考察拿取后是否可弥补所拿碎布产生的DVP。
  • 游戏初期的跳过可提高纽扣的保有量,增加拿取碎布时的可选范围。初期过多地拿取碎布会导致过早的消耗纽扣,中期会纽扣保有量低,会极大限制选择最优碎布。
  • 迫使对方跳过大量时间轴步数会直接降低他的VPPT,提高自己的DVP。

几何形状

游戏前期几何形状的限制其实微乎其微,完全可以仅通过优化碎布的VP和两方的DVP, 但好的几何形状可以为游戏后期创造更多的碎布拿取机会,提高获得$7\times7$的概率。几何拼接策略包括:

  • 避免空间切割。一些包含距离5的碎布会将空间切割为两部分,而单独填充两部分产生破洞的概率将大大增加。
  • 保持拼接的边缘平整。在计算一块碎布时,应放在最贴合的位置以减小新增的边缘周长。计算多块碎布时,则应考察拼接完成后的总周长,保持整体平整。
  • 如果没有更好的位置,尽量贴于边缘放置。大部分碎布可紧靠在边缘放置,使其和边缘重合部分的周长被充分吸收。
  • 从一个角落向外扩散。为了尽快达到$7\times7$奖励的条件,需至少拿取总面积49的碎布,因此需尽快将拿取的步覆盖在$7\times7$范围内。角落向外扩散能保证在凑集$7\times7$时,对面边界产生的是宽度为2的空白,可容纳更多类型的碎布,而非仅适合少数碎布的宽度1的空白。从角落扩散也更容易放置破洞的产生。
  • 从边界中间扩散。一些对称的碎布无法直接贴合在角落,因此可选择放置在边界中间位置,依靠后续的碎布逐次填充两侧的空白。