蜜蜂与果蝇：Hex棋中的生物启发算法比较

需积分: 44 193 浏览量更新于2024-07-19 3 收藏 953KB PDF 举报

《计算机Hex：蜜蜂优于果蝇吗？》是一篇由杰克·范里斯维克撰写的硕士论文，于2000年在阿尔伯塔大学获得计算机科学硕士学位。该研究专注于将人工智能和蜂群行为模型应用于一种名为Hex的游戏，这是一种具有策略性和复杂性的六边形棋类游戏。作者在文中探讨了模拟蜜蜂的社会行为和决策过程是否能提供对Hex棋的优化策略，以此来比较自然界的生物智慧与人工设计的算法在解决这类问题上的表现。在文章中，杰克·范里斯维克可能运用了进化计算或模拟退火等方法，将蜜蜂的觅食行为规则转化为搜索算法，试图通过模仿真实世界的协作和适应性来提升Hex棋的算法性能。蜜蜂的"舞蹈语言"和它们在寻找蜜源时的集体智慧被作为灵感来源，以评估这种自然智能在复杂环境中的潜在价值。论文的核心内容可能包括了以下几点： 1. **蜂群优化算法介绍**：作者可能会详细解释如何将蜜蜂的觅食行为转换为一种高效的搜索算法，这可能涉及到群体智能和局部搜索的结合。 2. **Hex棋游戏理论**：对于Hex游戏的规则、策略和已知的最佳解决方案进行简要回顾，以便读者理解研究背景。 3. **实验设计与实施**：阐述如何在Hex棋游戏中应用模拟的蜜蜂算法，并描述实验设置，包括数据收集和评估标准。 4. **结果分析与比较**：展示模拟蜜蜂行为的算法在Hex棋中的实际效果，与已知的传统算法（如深度优先搜索或广度优先搜索）进行对比，讨论优劣。 5. **结论与启示**：基于实验结果，作者会讨论蜜蜂启发式是否真的能带来性能提升，以及这些发现对人工智能领域特别是搜索算法设计的潜在意义。 6. **版权声明**：最后，论文强调了作者保留了关于出版和其他权利，并明确指出未经作者事先书面许可，任何形式的复制或传播必须遵守规定。这篇论文深入研究了自然界的生物行为如何影响人工智能算法的设计，通过将蜜蜂的行为模型应用到Hex棋这样的博弈问题上，探讨了其可能带来的创新性和效率提升。这对于理解复杂系统优化、生物启发式在计算科学中的应用具有重要价值。

1.6. Summary Chapter 1. Introduction

with a high branching factor, such as Go. Indeed, humans typically are still stronger than

computers at these games. The game of Hex is starting to become an exception to this rule.

• New evaluation function idea. The key behind Queenbee’s selective search as well as its

evaluation function is the concept of “two-distance”, an new way to measure connectivity in a

graph which appears to be naturally suited to two-player adversary games.

In addition, Queenbee has signiﬁcantly enhanced theoretical knowledge of Hex play on small boards,

by achieving p erfect play on any board size up to 6 × 6.

The remainder of this thesis is organized as follows. Chapter 2 gives an overview of the state of

the art in search algorithms. The history, rules, and mathematical background of game of Hex

are introduced in Chapter 3. To gain an understanding of the diﬃculty of the game, Chapter 4

explains the basics of Hex strategy. Chapter 5 details the two-distance evaluation that forms the

heart of Queenbee, and Chapter 6 describes the search methods used by the program. An analysis

of Queenbee’s playing strength follows in Chapter 7. Conclusions and future work are presented in

Chapter 8.

2.2. Evaluation function Chapter 2. Search algorithms

players. The payoﬀ can be positive, zero, or negative. Again without loss of generality it is assumed

that White receives the payoﬀ. Thus it is White’s task to maximize this score, while Black tries to

minimize it.

The game theoretic value of a position is deﬁned as the outcome of the game if both players follow

optimal play starting from that position.

With optimal play, White always moves such that a score

at least equal to the game theoretic value is reached, regardless of Black’s choice of moves. Similarly,

Black always moves such that a score of at most equal to the game theoretic value is reached. The

game theoretic value v( c) of a position c can therefore be deﬁned recursively. For a white position,

which is a position in which White is to move, we have:

v(c) =

S(c) if c ∈ L;

max

∈M (c)

v(c

) otherwise.

(2.1)

This reﬂects the fact that White always chooses the continuation that guarantees the maximum

possible outcome. Similarly, for black positions:

v(c) =

S(c) if c ∈ L;

min

∈M (c)

v(c

) otherwise.

(2.2)

The game theoretic value can thus be computed by means of a recursive algorithm called minimax.

Game playing programs actually use an equivalent variant of this algorithm, which computes the

function v

∗

other words, where v(c) is the payoﬀ for White at the end of the game, v

∗

player to move. If S

∗

(c)

is identical for white and black positions:

∗

max

∈M (c)

−v

∗

) otherwise.

(2.3)

The algorithm that computes v

∗

generates to compute the value v

∗

Any move in position c that leads to a position c

for which v

∗

) = −v

∗

accordingly, the position c

is called an optimal successor. The branching factor of a game is deﬁned

as the average number of available moves in a position. In other words, it is the average cardinality

|M(c)| over all positions c in the game. If the branching factor is b, then the number of nodes that

a search tree of depth d contains is of the order of b

2.2 Evaluation function

For most games, the search tree is too large to enable the game theoretic value of the root node to

be determined in a reasonable amount of time. To produce a reliable estimate for v

∗

(c), a game

The deﬁnition of the game theoretic value is more involved when there is the possibility of cyclic play, in which

a sequence of moves can lead back to the same position, or inﬁnite play, in which there exists an inﬁnite sequence of

moves that never leads to a leaf position. However, Hex is clearly non-cyclic and non-inﬁnite.

Chapter 2. Search algorithms 2.3. Alpha-beta search

t t t

≥ 3

−3

≥ 1

−1

Figure 2.1: An α-β cutoﬀ in a search tree

playing program uses an evaluation function. This function computes a heuristic estimate h(c) of

∗

(c). The game playing program will expand a subtree of the game tree. This tree is called the

search tree. For each leaf node c

leaf

of the search tree, the heuristic value h(c

leaf

) is computed by the

evaluation function. Interior nodes are non-leaf nodes; for each interior node c

int

, the heuristic value

h(c

int

) is backed up by the heuristic algorithm: h(c

int

) = max

∈M (c

int

)

−h(c

). Or, equivalently:

h(c

int

) = − min

∈M (c

int

)

h(c

). (2.4)

The search tree is typically expanded to a ﬁxed distance from the root. This distance is called the

search depth; it is commonly measured in ply, where one ply represents one single move by either

player. As the search depth increases, the accuracy of the root node value increases. The limit

case is reached if the search depth equals the maximum length of the game, in which case the value

that is backed up to the root node equals the true game theoretic value provided h(c) = S

∗

terminal nodes c ∈ L.

2.3 Alpha-beta search

To ﬁnd the root node value, it is not necessary to expand the full search tree. Consider Figure 2.1,

which depicts a subtree of the search tree. The root position c has three successor positions c

, c

and c

. Once it is established that v

∗

) = −3, it is known that v

∗

in boxes. As the minimax algorithm is backtracking through this tree, the next step is to compute

∗

). Suppose the value of the ﬁrst successor position is determined to be −1. At that point, it

is known that v

∗

) ≥ 1, and therefore c

cannot be an optimal successor position as the value of

node c is determined by the minimum value of its successor positions. Thus it is no longer necessary

to calculate the values for c

and c

剩余93页未读，继续阅读

smnooy

粉丝: 5
资源: 4

蜜蜂与果蝇：Hex棋中的生物启发算法比较

海战棋源代码

雷曼克斯USB写频线驱动程序

森海克斯N70双模对讲机写频软件.zip

海克斯棋博弈深度学习

matlab海克斯棋

用c语言写一个海克斯棋程序

雷曼克斯写频软件

五子棋程序（附带完整源代码）

CRISPRi, One Technology Better than CRISPR-Cas9

雷曼克斯写频软件集合_1.01.zip

最新资源