aimisiyou 发表于 2021-5-25 17:00:27

双L游戏

1、一个4*4的棋盘， 放有两个L形和两个小圆球； 其中一个L形被先手控制、 另一个被后手控制。
2、 两个人轮流走棋。 一个人每一步可以将L形拿起然后重新放入棋盘中的任何新位置（不能放在原来的位置，可以翻转、 旋转） ； 然后他可以选择任意一个小圆球移动到新的位置、 也可以不移动小圆球， 这由他决定。
3、 一旦某人不能走了， 就输了。 输入一个初始状态， 判断先手是必胜、 必败还是平局。 （假设两个人都足够聪明）

mathe 发表于 2021-5-26 19:31:07

好像总是有新位置可下

王守恩 发表于 2021-5-26 20:02:53

看不懂，譬如：上方的球右移1格，下方的球左移1格，右上方的人不能走，就输了？

aimisiyou 发表于 2021-5-26 21:45:22

mathe 发表于 2021-5-26 19:31
好像总是有新位置可下

与初始状态有关。若出现总有新位置可下，那就是平局了。

aimisiyou 发表于 2021-5-26 22:16:25

本帖最后由 aimisiyou 于 2021-5-26 22:22 编辑

比如初始状态，且黄色L先手，那么先手操作后后手没法移动，所以后手输。
如果同样的初始状态，绿色L先手，先手能否获胜？

mathe 发表于 2021-5-26 23:18:35

不去除对称局面共14112种，好像先手输的2792种，先手赢的9562种，余下的平局。

aimisiyou 发表于 2021-5-26 23:24:08

mathe 发表于 2021-5-26 23:18
不去除对称局面共14112种，好像先手输的2792种，先手赢的9562种，余下的平局。

怎么得出来的？

mathe 发表于 2021-5-27 06:10:01

前面应该1错了，遗漏局面了，应该共18368种（去除对称性2296种），先手赢8048种，输232种，其余都平
所以去除对称性，只有29种先手输的局面。
总体局面数目不多，先全部找出来。
然后先搜索所有无法移动的局面（输的局面）
然后在找出能移动到任意一个让对方输的局面（赢的局面）
然后再寻找只能移动到让对方赢的局面（输的局面），反复重复上面过程直到没有新的局面。

mathe 发表于 2021-5-27 06:13:19

FLBB
FLLL
FF*B
B*BB

FFLB
FBLB
FLL*
*BBB

FFLB
FBLB
FLLB
*B*B

FFLB
FBLB
FLLB
*BB*

FFLB
FBLB
F*LL
*BBB

FF*B
FLB*
FLBB
BLLB

FF*B
FLBB
FLB*
BLLB

FF*B
FLL*
FLBB
BLBB

FF*B
FLLB
FLB*
BLBB

FF*B
FLLL
FLBB
B*BB

FF*B
FLBB
FLLL
*BBB

FF*B
FLBB
FLLL
B*BB

FF*B
F*BB
FLLL
BLBB

FFLB
BFLB
*FLL
B*BB

FF*B
BFLB
*FLB
BLLB

FFF*
FBLB
LLL*
BBBB

FFF*
FBLB
LLLB
BB*B

FFF*
FBLB
LLLB
BBB*

FFF*
FB*B
LLLB
BBLB

FFFB
FLL*
*LBB
BLBB

FFF*
FLLB
*BLB
BBLB

FFFB
FLL*
*BLB
BBLB

FFFB
FLLL
*LBB
B*BB

FFFB
FLLL
*LBB
BB*B

FFFB
FLLL
*BBL
B*BB

FFFB
FLLL
*BBL
BB*B

FFFB
F*LL
*BLB
BBLB

FFFB
LLF*
BL*B
BLBB

FB*B
FFF*
LLLB
BBLB

FB*B
FFFL
*LLL
BBBB

BLFF
BLFB
LLF*
BB*B

B*FF
BLFB
BLF*
BLLB

BBLF
LLLF
B*FF
BB*B

BLFF
BLBF
LL*F
BBB*

BLFF
BLBF
*LLF
BBB*

BLFF
BLBF
BLLF
*BB*

BLFF
BLBF
BLLF
B*B*

B*FF
LLLF
BBLF
BB*B

B*FF
BBLF
LLLF
BB*B

B*FF
BBLF
LLLF
BBB*

B*FF
BB*F
LLLF
BBLB

B*FF
*BLF
BBLF
BLLB

B*FF
BBLF
*BLF
BLLB

B*FF
*LLF
BBLF
BBLB

B*FF
BLLF
*BLF
BBLB

BBLB
LLLB
FFF*
FB*B

BBBB
*LLL
FFFL
FB*B

BBLB
LLLB
FB*B
FFF*

BLBB
*LBB
FLL*
FFFB

BBLB
*BLB
FLL*
FFFB

BBLB
*BLB
FLLB
FFF*

BB*B
LLLB
FBLB
FFF*

BBB*
LLLB
FBLB
FFF*

BBBB
LLL*
FBLB
FFF*

BBLB
*BLB
F*LL
FFFB

B*BB
*LBB
FLLL
FFFB

BB*B
*LBB
FLLL
FFFB

B*BB
*BBL
FLLL
FFFB

BB*B
*BBL
FLLL
FFFB

BLBB
BL*B
LLF*
FFFB

BLBB
FLB*
FLLB
FF*B

BLBB
FLBB
FLL*
FF*B

BLLB
FLB*
FLBB
FF*B

BLLB
FLBB
FLB*
FF*B

BLBB
FLLL
F*BB
FF*B

*B*B
FLLB
FBLB
FFLB

*BB*
FLLB
FBLB
FFLB

*BBB
FLL*
FBLB
FFLB

*BBB
FLLL
FLBB
FF*B

B*BB
FLLL
FLBB
FF*B

B*BB
FLBB
FLLL
FF*B

*BBB
F*LL
FBLB
FFLB

B*BB
FF*B
FLLL
FLBB

BLLB
*FLB
BFLB
FF*B

B*BB
*FLL
BFLB
FFLB

BFFF
*FLL
B*LB
BBLB

BFFF
LLLF
LBB*
B*BB

BFFF
LLLF
LBB*
BB*B

BFFF
LLLF
BBL*
B*BB

BFFF
LLLF
BBL*
BB*B

BFFF
LL*F
BLB*
BLBB

*FFF
BLLF
BLB*
BLBB

BFFF
*LLF
BLB*
BLBB

BFFF
*LLF
BBL*
BBLB

*FFF
BLBF
*LLL
BBBB

*FFF
BLBF
BLLL
*BBB

*FFF
BLBF
BLLL
B*BB

*FFF
B*BF
BLLL
BLBB

B*BF
LFFF
LLL*
BBBB

B*BF
*FFF
BLLL
BLBB

BLLB
BLF*
BLFB
B*FF

BB*B
BLF*
BLFB
LLFF

BB*B
LLF*
BLFB
BLFF

BBLB
LLLF
BB*F
B*FF

BBLB
*BLF
BLLF
B*FF

BBLB
BBLF
*LLF
B*FF

BLLB
*BLF
BBLF
B*FF

BLLB
BBLF
*BLF
B*FF

BB*B
LLLF
BBLF
B*FF

BBB*
LLLF
BBLF
B*FF

BB*B
BBLF
LLLF
B*FF

BBB*
BBLF
LLLF
B*FF

BBB*
LL*F
BLBF
BLFF

*BB*
BLLF
BLBF
BLFF

B*B*
BLLF
BLBF
BLFF

BBB*
*LLF
BLBF
BLFF

BB*B
B*FF
LLLF
BBLF

BBBB
LLL*
LFFF
B*BF

BLBB
BLLL
*FFF
B*BF

BBBL
BLLL
*FFF
B*BF

BBLB
B*LB
*FLL
BFFF

BLBB
BLB*
LL*F
BFFF

BLBB
BLB*
*LLF
BFFF

BLBB
BLB*
BLLF
*FFF

BBLB
BBL*
*LLF
BFFF

BBLB
BBL*
BLLF
*FFF

B*BB
LBB*
LLLF
BFFF

BB*B
LBB*
LLLF
BFFF

B*BB
BBL*
LLLF
BFFF

BB*B
BBL*
LLLF
BFFF

BLBB
BLLL
B*BF
*FFF

*BBB
BLLL
BLBF
*FFF

B*BB
BLLL
BLBF
*FFF

BBBB
*LLL
BLBF
*FFF

Total 334 found in round 1
FFBB
FLLL
FLBB
B**B

FFFB
FLL*
BLB*
BLBB

LLFF
BLFB
BLF*
BB*B

B*FF
LLLF
BBLF
BBB*

BBFF
LLLF
BBLF
B**B

LBBB
LLLB
FFF*
FB*B

BLBB
*LBB
FLLB
FFF*

BLBB
BLB*
FLL*
FFFB

*BBB
FLBB
FLLL
FF*B

B**B
FLBB
FLLL
FFBB

B*BB
*FLB
BFLB
FFLL

*FFF
BLLF
BBL*
BBLB

BFFF
*LLF
*BLB
BBLB

B*BF
*FFF
BLLL
BBBL

B**B
BBLF
LLLF
BBFF

BB*B
BBLF
LLLF
*BFF

BBL*
BBLB
*LLF
BFFF

BBLB
*BLB
*LLF
BFFF

Total 894 found in round 2
F*BB
FLLB
FFLB
B*LB

FF*B
FLLL
FLBB
*BBB

FFBB
FLLL
FLB*
B*BB

FFLL
BFLB
*FLB
B*BB

FFF*
FLLB
*LBB
BLBB

FFFB
FLL*
BLBB
BL*B

FFFB
*LF*
BLLL
BBBB

FB*B
FFF*
LLLB
LBBB

BB*F
BLLF
BLFF
BL*B

*BFF
LLLF
BBLF
BB*B

BBFF
LLLF
*BLF
BB*B

*LBB
BLBB
FLL*
FFFB

BL*B
BLBB
FLL*
FFFB

BBBB
BLLL
*LF*
FFFB

B*BB
FLB*
FLLL
FFBB

B*BB
FLBB
FLLL
FFB*

B*LB
FFLB
FLLB
F*BB

BFFF
*FL*
LLLB
BBBB

BFFF
*LLF
BBLB
B*LB

BFFF
*LLF
BBLB
BBL*

B*B*
BBLF
LLLF
BBFF

BB**
BBLF
LLLF
BBFF

BB*B
*BLF
LLLF
BBFF

BBB*
*BLF
LLLF
BBFF

BL*B
BLFF
BLLF
BB*F

BBBB
LLLB
*FL*
BFFF

B*LB
BBLB
*LLF
BFFF

B*LB
BBLB
BLLF
*FFF

BBLB
*BLB
BLLF
*FFF

BBLB
BBLB
*LLF
*FFF

Total 64 found in round 3
FFLB
FBLB
FLLB
**BB

FFB*
FLLL
FLBB
B*BB

FFF*
FBL*
LLLB
BBBB

FFFB
FLL*
BLBB
*LBB

BLFF
BLBF
BLLF
BB**

*BFF
LLLF
BBLF
BBB*

BBFF
LLLF
*BLF
BBB*

BBFF
LLLF
BBLF
B*B*

BBFF
LLLF
BBLF
BB**

*LBB
BLBB
FLLB
FFF*

BL*B
BLBB
FLLB
FFF*

BLBB
BLB*
FLLB
FFF*

BLBB
BLBB
FLL*
FFF*

BBBB
LLLB
FBL*
FFF*

**BB
FLLB
FBLB
FFLB

**BB
FLBB
FLLL
FFBB

*B*B
FLBB
FLLL
FFBB

*BBB
FLB*
FLLL
FFBB

*BBB
FLBB
FLLL
FFB*

*FFF
*LLF
BBLB
BBLB

*FFF
BLLF
*BLB
BBLB

*FFF
BLLF
BBLB
B*LB

*FFF
BLLF
BBLB
BBL*

*FFF
*LBF
BLLL
BBBB

BBB*
BBLF
LLLF
*BFF

BB**
BLLF
BLBF
BLFF

BBL*
BBLB
BLLF
*FFF

BBBB
BLLL
*LBF
*FFF

Total 71 found in round 4
FBB*
F*LB
FFLB
BLLB

FBBB
F*L*
FFLB
BLLB

FFB*
FLLL
FLBB
*BBB

FFBB
FLLL
FLB*
*BBB

FFBB
FLLL
FLB*
BB*B

FFBB
FLLL
FLBB
**BB

FFBB
FLLL
FLBB
*B*B

FFF*
FLL*
BLBB
BLBB

FFF*
FLLB
BLB*
BLBB

FFF*
FLLB
BLBB
*LBB

FFF*
FLLB
BLBB
BL*B

FFFB
FLLB
BLB*
BL*B

FFFB
B*FL
BLLL
*BBB

FFFB
B*FL
BLLL
B*BB

*BBF
BL*F
BLFF
BLLB

BBBF
*L*F
BLFF
BLLB

BBFF
LLLF
*BLF
B*BB

BL*B
BLB*
FLLB
FFFB

*BBB
BLLL
B*FL
FFFB

B*BB
BLLL
B*FL
FFFB

BB*B
FLB*
FLLL
FFBB

BLLB
FFLB
F*L*
FBBB

BLLB
FFLB
F*LB
FBB*

BFFF
LF*B
LLLB
BB*B

BFFF
LF*B
LLLB
BBB*

BFFF
BLLF
*BLB
B*LB

B*BB
*BLF
LLLF
BBFF

BLLB
BLFF
*L*F
BBBF

BLLB
BLFF
BL*F
*BBF

BB*B
LLLB
LF*B
BFFF

BBB*
LLLB
LF*B
BFFF

B*LB
*BLB
BLLF
BFFF

F代表先手，L后手,B空格，*圆球

王守恩 发表于 2021-5-27 07:59:05

本帖最后由 王守恩 于 2021-5-27 08:00 编辑

王守恩 发表于 2021-5-26 20:02
看不懂，譬如：上方的球右移1格，下方的球左移1格，右上方的人不能走，就输了？

起始状态，2个球有21种填法
1，第1个球在角格(4个位置)，第2个球有9种填法
2，第1个球在边格(8个位置)，第2个球有10种填法
3，第1个球在中格(4个位置)，第2个球有2种填法
页: [1]
查看完整版本: 双L游戏