博弈树是一种数据结构,用于表示博弈中的所有可能的行动序列和结果。它是一个树形图,其中每个节点代表一个博弈状态,而每个分支代表博弈者在该状态下可以采取的行动。博弈树具有以下特点:
深度
博弈树的深度表示博弈中允许的行动序列的长度。它决定了博弈的复杂性,深度越大的博弈,博弈者需要考虑的可能行动越多。
宽度
博弈树的宽度表示博弈中每个状态下可以采取的行动数量。它决定了博弈的策略空间,宽度越大的博弈,博弈者拥有的策略选择越多。
终结状态
终结状态是博弈树中没有后续行动的状态。它表示博弈的结束,并且具有明确的结果。终结状态可以是胜利、平局或失败。
策略
策略是博弈者在博弈树中的一系列行动。它定义了博弈者在每个状态下应该采取的行动,以达到他们想要的结果。
值
博弈树的每个状态都有一个值,表示博弈者在该状态下的预期结果。这个值通常是博弈者可以获得的效用或收益。
最小最大搜索
最小最大搜索是一种算法,用于在博弈树中找到最佳策略。它通过递归地计算每个状态下博弈者的最佳行动和对手的最差行动来实现。
剪枝
剪枝是一种优化技术,用于最小最大搜索。它通过消除不可能出现在最佳策略中的分支来减少搜索空间。
信息完美度
信息完美度是博弈是否具有完全信息的状态。在完全信息博弈中,所有博弈者都可以看到所有其他博弈者的行动。
随机性
随机性是博弈中引入不确定性的元素。它可以来自骰子掷出、洗牌或其他随机事件。
合作博弈
合作博弈是博弈者可以合作以实现共同目标的博弈。在这个博弈中,博弈者的目标是一致的。
非合作博弈
非合作博弈是博弈者不能合作以实现共同目标的博弈。在这个博弈中,博弈者的目标是相互冲突的。
顺序博弈
顺序博弈是博弈者轮流行动的博弈。在这个博弈中,博弈者的行动顺序是固定的。
并行博弈
并行博弈是博弈者可以同时行动的博弈。在这个博弈中,博弈者的行动顺序不是固定的。
确定博弈
确定博弈是博弈中所有信息都是已知的,并且没有随机性。在这个博弈中,最佳策略是可以计算出来的。
不确定博弈
不确定博弈是博弈中信息不完全或存在随机性。在这个博弈中,最佳策略不能被计算出来,只能通过估计和直觉来确定。
完美信息博弈
完美信息博弈是博弈者在每个状态下都可以看到所有其他博弈者的行动的博弈。在这个博弈中,博弈者可以完美地预测对手的行动。
不完全信息博弈
不完全信息博弈是博弈者在某些状态下看不到所有其他博弈者的行动的博弈。在这个博弈中,博弈者不能完美地预测对手的行动。
零和博弈
零和博弈是博弈中博弈者的收益总和为零的博弈。在这个博弈中,一方的收益就是另一方的损失。
非零和博弈
非零和博弈是博弈中博弈者的收益总和不为零的博弈。在这个博弈中,博弈者可以既受益又损失。
对称博弈
对称博弈是所有博弈者拥有相同策略空间和相同收益的博弈。在这个博弈中,没有博弈者拥有内在优势。
非对称博弈
非对称博弈是所有博弈者不拥有相同策略空间和相同收益的博弈。在这个博弈中,某些博弈者可能拥有内在优势。