数学研发论坛

 找回密码
 欢迎注册
查看: 53|回复: 1

[讨论] 海战棋的最佳策略

[复制链接]
发表于 2021-11-24 09:49:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
海战棋是一个双人的非完全信息博弈,简单来说就是猜对方的船只在哪儿。

开战前双方在10乘10的格子阵中,摆放1搜长度为4的船只、2搜长度为3的船只、3搜长度为2的船只、4搜长度为1的船只,共计10艘船占20个格子。

摆放的船只不能紧邻(占领的格子不能有公共边),也不能对角相邻(占领的格子不能有公共点)。

这是一种可行的摆法(蓝色矩形表示船只):

pattern.png

双方都摆好后,就轮流轰炸对方阵地。

对于每轮轰炸,都是选择对方阵地中的1个格子进行轰炸,

如果轰炸的格子有船只,则可以继续另选格子进行轰炸,

直到轰炸的格子没有船只为止,本轮轰炸结束。

如果某艘船所占的格子都被轰炸过,则必须立即把这艘船亮出来,然后这艘船周围一圈的格子都无需再轰炸。

先把对方10艘船所占的20个格子都轰炸完的一方获胜。

在这个网站上,无需注册账号就可以玩这个游戏:

http://zh.battleship-game.org

本贴希望编程解决以下问题:

问题1:我方有多少种摆法?

问题2:分别以多大的概率选择每种摆法,可以使得对方轰炸的轮数的期望值达到最大(假设对方使用最佳策略轰炸)?

问题3:我方应如何轰炸对方阵地,可以使得轰炸所需轮数的期望值达到最小(假设对方使用最佳策略摆船)?

问题4:当双方都使用纳什均衡策略进行摆船和轰炸时,先手的胜率是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 4 天前 | 显示全部楼层
我从$2^6*10^20$种摆法中,随机抽取了$2240000000$种摆法进行判断,结果仅有$187391$种摆法是合规摆法,

因此可以估算出我方有$2^6*10^20*187391/2240000000\approx 5.354*10^17$种摆法。

这是按$10$艘船都不一样来计算的摆法数。

实际上有些船是一样的,所以摆法数没那么多。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-12-7 19:41 , Processed in 0.054791 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表