数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 双L游戏
返回列表 发新帖
查看: 26335|回复: 14

[讨论] 双L游戏

[复制链接]
aimisiyou
发表于 2021-5-25 17:00:27 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
1、一个4*4的棋盘， 放有两个L形和两个小圆球； 其中一个L形被先手控制、 另一个被后手控制。
2、 两个人轮流走棋。 一个人每一步可以将L形拿起然后重新放入棋盘中的任何新位置（不能放在原来的位置，可以翻转、 旋转） ； 然后他可以选择任意一个小圆球移动到新的位置、 也可以不移动小圆球， 这由他决定。
3、 一旦某人不能走了， 就输了。 输入一个初始状态， 判断先手是必胜、 必败还是平局。 （假设两个人都足够聪明）
79cf4e7f95de82f8.png
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

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先手，先手能否获胜？
4ef047b0118a3ad7.png
-4b3e04053a7e43ef.png

点评

aimisiyou
感觉先手尽量将后手逼到角落，然后通过移动自己控制的L位置和其中一个小球来“将死”对方。  发表于 2021-5-26 22:36
mathe
所以双方的L是不同的，我以为可以任意选一个移动  发表于 2021-5-26 22:24
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
  1. FLBB
  2. FLLL
  3. FF*B
  4. B*BB

  6. FFLB
  7. FBLB
  8. FLL*
  9. *BBB

  11. FFLB
  12. FBLB
  13. FLLB
  14. *B*B

  16. FFLB
  17. FBLB
  18. FLLB
  19. *BB*

  21. FFLB
  22. FBLB
  23. F*LL
  24. *BBB

  26. FF*B
  27. FLB*
  28. FLBB
  29. BLLB

  31. FF*B
  32. FLBB
  33. FLB*
  34. BLLB

  36. FF*B
  37. FLL*
  38. FLBB
  39. BLBB

  41. FF*B
  42. FLLB
  43. FLB*
  44. BLBB

  46. FF*B
  47. FLLL
  48. FLBB
  49. B*BB

  51. FF*B
  52. FLBB
  53. FLLL
  54. *BBB

  56. FF*B
  57. FLBB
  58. FLLL
  59. B*BB

  61. FF*B
  62. F*BB
  63. FLLL
  64. BLBB

  66. FFLB
  67. BFLB
  68. *FLL
  69. B*BB

  71. FF*B
  72. BFLB
  73. *FLB
  74. BLLB

  76. FFF*
  77. FBLB
  78. LLL*
  79. BBBB

  81. FFF*
  82. FBLB
  83. LLLB
  84. BB*B

  86. FFF*
  87. FBLB
  88. LLLB
  89. BBB*

  91. FFF*
  92. FB*B
  93. LLLB
  94. BBLB

  96. FFFB
  97. FLL*
  98. *LBB
  99. BLBB

  101. FFF*
  102. FLLB
  103. *BLB
  104. BBLB

  106. FFFB
  107. FLL*
  108. *BLB
  109. BBLB

  111. FFFB
  112. FLLL
  113. *LBB
  114. B*BB

  116. FFFB
  117. FLLL
  118. *LBB
  119. BB*B

  121. FFFB
  122. FLLL
  123. *BBL
  124. B*BB

  126. FFFB
  127. FLLL
  128. *BBL
  129. BB*B

  131. FFFB
  132. F*LL
  133. *BLB
  134. BBLB

  136. FFFB
  137. LLF*
  138. BL*B
  139. BLBB

  141. FB*B
  142. FFF*
  143. LLLB
  144. BBLB

  146. FB*B
  147. FFFL
  148. *LLL
  149. BBBB

  151. BLFF
  152. BLFB
  153. LLF*
  154. BB*B

  156. B*FF
  157. BLFB
  158. BLF*
  159. BLLB

  161. BBLF
  162. LLLF
  163. B*FF
  164. BB*B

  166. BLFF
  167. BLBF
  168. LL*F
  169. BBB*

  171. BLFF
  172. BLBF
  173. *LLF
  174. BBB*

  176. BLFF
  177. BLBF
  178. BLLF
  179. *BB*

  181. BLFF
  182. BLBF
  183. BLLF
  184. B*B*

  186. B*FF
  187. LLLF
  188. BBLF
  189. BB*B

  191. B*FF
  192. BBLF
  193. LLLF
  194. BB*B

  196. B*FF
  197. BBLF
  198. LLLF
  199. BBB*

  201. B*FF
  202. BB*F
  203. LLLF
  204. BBLB

  206. B*FF
  207. *BLF
  208. BBLF
  209. BLLB

  211. B*FF
  212. BBLF
  213. *BLF
  214. BLLB

  216. B*FF
  217. *LLF
  218. BBLF
  219. BBLB

  221. B*FF
  222. BLLF
  223. *BLF
  224. BBLB

  226. BBLB
  227. LLLB
  228. FFF*
  229. FB*B

  231. BBBB
  232. *LLL
  233. FFFL
  234. FB*B

  236. BBLB
  237. LLLB
  238. FB*B
  239. FFF*

  241. BLBB
  242. *LBB
  243. FLL*
  244. FFFB

  246. BBLB
  247. *BLB
  248. FLL*
  249. FFFB

  251. BBLB
  252. *BLB
  253. FLLB
  254. FFF*

  256. BB*B
  257. LLLB
  258. FBLB
  259. FFF*

  261. BBB*
  262. LLLB
  263. FBLB
  264. FFF*

  266. BBBB
  267. LLL*
  268. FBLB
  269. FFF*

  271. BBLB
  272. *BLB
  273. F*LL
  274. FFFB

  276. B*BB
  277. *LBB
  278. FLLL
  279. FFFB

  281. BB*B
  282. *LBB
  283. FLLL
  284. FFFB

  286. B*BB
  287. *BBL
  288. FLLL
  289. FFFB

  291. BB*B
  292. *BBL
  293. FLLL
  294. FFFB

  296. BLBB
  297. BL*B
  298. LLF*
  299. FFFB

  301. BLBB
  302. FLB*
  303. FLLB
  304. FF*B

  306. BLBB
  307. FLBB
  308. FLL*
  309. FF*B

  311. BLLB
  312. FLB*
  313. FLBB
  314. FF*B

  316. BLLB
  317. FLBB
  318. FLB*
  319. FF*B

  321. BLBB
  322. FLLL
  323. F*BB
  324. FF*B

  326. *B*B
  327. FLLB
  328. FBLB
  329. FFLB

  331. *BB*
  332. FLLB
  333. FBLB
  334. FFLB

  336. *BBB
  337. FLL*
  338. FBLB
  339. FFLB

  341. *BBB
  342. FLLL
  343. FLBB
  344. FF*B

  346. B*BB
  347. FLLL
  348. FLBB
  349. FF*B

  351. B*BB
  352. FLBB
  353. FLLL
  354. FF*B

  356. *BBB
  357. F*LL
  358. FBLB
  359. FFLB

  361. B*BB
  362. FF*B
  363. FLLL
  364. FLBB

  366. BLLB
  367. *FLB
  368. BFLB
  369. FF*B

  371. B*BB
  372. *FLL
  373. BFLB
  374. FFLB

  376. BFFF
  377. *FLL
  378. B*LB
  379. BBLB

  381. BFFF
  382. LLLF
  383. LBB*
  384. B*BB

  386. BFFF
  387. LLLF
  388. LBB*
  389. BB*B

  391. BFFF
  392. LLLF
  393. BBL*
  394. B*BB

  396. BFFF
  397. LLLF
  398. BBL*
  399. BB*B

  401. BFFF
  402. LL*F
  403. BLB*
  404. BLBB

  406. *FFF
  407. BLLF
  408. BLB*
  409. BLBB

  411. BFFF
  412. *LLF
  413. BLB*
  414. BLBB

  416. BFFF
  417. *LLF
  418. BBL*
  419. BBLB

  421. *FFF
  422. BLBF
  423. *LLL
  424. BBBB

  426. *FFF
  427. BLBF
  428. BLLL
  429. *BBB

  431. *FFF
  432. BLBF
  433. BLLL
  434. B*BB

  436. *FFF
  437. B*BF
  438. BLLL
  439. BLBB

  441. B*BF
  442. LFFF
  443. LLL*
  444. BBBB

  446. B*BF
  447. *FFF
  448. BLLL
  449. BLBB

  451. BLLB
  452. BLF*
  453. BLFB
  454. B*FF

  456. BB*B
  457. BLF*
  458. BLFB
  459. LLFF

  461. BB*B
  462. LLF*
  463. BLFB
  464. BLFF

  466. BBLB
  467. LLLF
  468. BB*F
  469. B*FF

  471. BBLB
  472. *BLF
  473. BLLF
  474. B*FF

  476. BBLB
  477. BBLF
  478. *LLF
  479. B*FF

  481. BLLB
  482. *BLF
  483. BBLF
  484. B*FF

  486. BLLB
  487. BBLF
  488. *BLF
  489. B*FF

  491. BB*B
  492. LLLF
  493. BBLF
  494. B*FF

  496. BBB*
  497. LLLF
  498. BBLF
  499. B*FF

  501. BB*B
  502. BBLF
  503. LLLF
  504. B*FF

  506. BBB*
  507. BBLF
  508. LLLF
  509. B*FF

  511. BBB*
  512. LL*F
  513. BLBF
  514. BLFF

  516. *BB*
  517. BLLF
  518. BLBF
  519. BLFF

  521. B*B*
  522. BLLF
  523. BLBF
  524. BLFF

  526. BBB*
  527. *LLF
  528. BLBF
  529. BLFF

  531. BB*B
  532. B*FF
  533. LLLF
  534. BBLF

  536. BBBB
  537. LLL*
  538. LFFF
  539. B*BF

  541. BLBB
  542. BLLL
  543. *FFF
  544. B*BF

  546. BBBL
  547. BLLL
  548. *FFF
  549. B*BF

  551. BBLB
  552. B*LB
  553. *FLL
  554. BFFF

  556. BLBB
  557. BLB*
  558. LL*F
  559. BFFF

  561. BLBB
  562. BLB*
  563. *LLF
  564. BFFF

  566. BLBB
  567. BLB*
  568. BLLF
  569. *FFF

  571. BBLB
  572. BBL*
  573. *LLF
  574. BFFF

  576. BBLB
  577. BBL*
  578. BLLF
  579. *FFF

  581. B*BB
  582. LBB*
  583. LLLF
  584. BFFF

  586. BB*B
  587. LBB*
  588. LLLF
  589. BFFF

  591. B*BB
  592. BBL*
  593. LLLF
  594. BFFF

  596. BB*B
  597. BBL*
  598. LLLF
  599. BFFF

  601. BLBB
  602. BLLL
  603. B*BF
  604. *FFF

  606. *BBB
  607. BLLL
  608. BLBF
  609. *FFF

  611. B*BB
  612. BLLL
  613. BLBF
  614. *FFF

  616. BBBB
  617. *LLL
  618. BLBF
  619. *FFF

  621. Total 334 found in round 1
  622. FFBB
  623. FLLL
  624. FLBB
  625. B**B

  627. FFFB
  628. FLL*
  629. BLB*
  630. BLBB

  632. LLFF
  633. BLFB
  634. BLF*
  635. BB*B

  637. B*FF
  638. LLLF
  639. BBLF
  640. BBB*

  642. BBFF
  643. LLLF
  644. BBLF
  645. B**B

  647. LBBB
  648. LLLB
  649. FFF*
  650. FB*B

  652. BLBB
  653. *LBB
  654. FLLB
  655. FFF*

  657. BLBB
  658. BLB*
  659. FLL*
  660. FFFB

  662. *BBB
  663. FLBB
  664. FLLL
  665. FF*B

  667. B**B
  668. FLBB
  669. FLLL
  670. FFBB

  672. B*BB
  673. *FLB
  674. BFLB
  675. FFLL

  677. *FFF
  678. BLLF
  679. BBL*
  680. BBLB

  682. BFFF
  683. *LLF
  684. *BLB
  685. BBLB

  687. B*BF
  688. *FFF
  689. BLLL
  690. BBBL

  692. B**B
  693. BBLF
  694. LLLF
  695. BBFF

  697. BB*B
  698. BBLF
  699. LLLF
  700. *BFF

  702. BBL*
  703. BBLB
  704. *LLF
  705. BFFF

  707. BBLB
  708. *BLB
  709. *LLF
  710. BFFF

  712. Total 894 found in round 2
  713. F*BB
  714. FLLB
  715. FFLB
  716. B*LB

  718. FF*B
  719. FLLL
  720. FLBB
  721. *BBB

  723. FFBB
  724. FLLL
  725. FLB*
  726. B*BB

  728. FFLL
  729. BFLB
  730. *FLB
  731. B*BB

  733. FFF*
  734. FLLB
  735. *LBB
  736. BLBB

  738. FFFB
  739. FLL*
  740. BLBB
  741. BL*B

  743. FFFB
  744. *LF*
  745. BLLL
  746. BBBB

  748. FB*B
  749. FFF*
  750. LLLB
  751. LBBB

  753. BB*F
  754. BLLF
  755. BLFF
  756. BL*B

  758. *BFF
  759. LLLF
  760. BBLF
  761. BB*B

  763. BBFF
  764. LLLF
  765. *BLF
  766. BB*B

  768. *LBB
  769. BLBB
  770. FLL*
  771. FFFB

  773. BL*B
  774. BLBB
  775. FLL*
  776. FFFB

  778. BBBB
  779. BLLL
  780. *LF*
  781. FFFB

  783. B*BB
  784. FLB*
  785. FLLL
  786. FFBB

  788. B*BB
  789. FLBB
  790. FLLL
  791. FFB*

  793. B*LB
  794. FFLB
  795. FLLB
  796. F*BB

  798. BFFF
  799. *FL*
  800. LLLB
  801. BBBB

  803. BFFF
  804. *LLF
  805. BBLB
  806. B*LB

  808. BFFF
  809. *LLF
  810. BBLB
  811. BBL*

  813. B*B*
  814. BBLF
  815. LLLF
  816. BBFF

  818. BB**
  819. BBLF
  820. LLLF
  821. BBFF

  823. BB*B
  824. *BLF
  825. LLLF
  826. BBFF

  828. BBB*
  829. *BLF
  830. LLLF
  831. BBFF

  833. BL*B
  834. BLFF
  835. BLLF
  836. BB*F

  838. BBBB
  839. LLLB
  840. *FL*
  841. BFFF

  843. B*LB
  844. BBLB
  845. *LLF
  846. BFFF

  848. B*LB
  849. BBLB
  850. BLLF
  851. *FFF

  853. BBLB
  854. *BLB
  855. BLLF
  856. *FFF

  858. BBLB
  859. BBLB
  860. *LLF
  861. *FFF

  863. Total 64 found in round 3
  864. FFLB
  865. FBLB
  866. FLLB
  867. **BB

  869. FFB*
  870. FLLL
  871. FLBB
  872. B*BB

  874. FFF*
  875. FBL*
  876. LLLB
  877. BBBB

  879. FFFB
  880. FLL*
  881. BLBB
  882. *LBB

  884. BLFF
  885. BLBF
  886. BLLF
  887. BB**

  889. *BFF
  890. LLLF
  891. BBLF
  892. BBB*

  894. BBFF
  895. LLLF
  896. *BLF
  897. BBB*

  899. BBFF
  900. LLLF
  901. BBLF
  902. B*B*

  904. BBFF
  905. LLLF
  906. BBLF
  907. BB**

  909. *LBB
  910. BLBB
  911. FLLB
  912. FFF*

  914. BL*B
  915. BLBB
  916. FLLB
  917. FFF*

  919. BLBB
  920. BLB*
  921. FLLB
  922. FFF*

  924. BLBB
  925. BLBB
  926. FLL*
  927. FFF*

  929. BBBB
  930. LLLB
  931. FBL*
  932. FFF*

  934. **BB
  935. FLLB
  936. FBLB
  937. FFLB

  939. **BB
  940. FLBB
  941. FLLL
  942. FFBB

  944. *B*B
  945. FLBB
  946. FLLL
  947. FFBB

  949. *BBB
  950. FLB*
  951. FLLL
  952. FFBB

  954. *BBB
  955. FLBB
  956. FLLL
  957. FFB*

  959. *FFF
  960. *LLF
  961. BBLB
  962. BBLB

  964. *FFF
  965. BLLF
  966. *BLB
  967. BBLB

  969. *FFF
  970. BLLF
  971. BBLB
  972. B*LB

  974. *FFF
  975. BLLF
  976. BBLB
  977. BBL*

  979. *FFF
  980. *LBF
  981. BLLL
  982. BBBB

  984. BBB*
  985. BBLF
  986. LLLF
  987. *BFF

  989. BB**
  990. BLLF
  991. BLBF
  992. BLFF

  994. BBL*
  995. BBLB
  996. BLLF
  997. *FFF

  999. BBBB
  1000. BLLL
  1001. *LBF
  1002. *FFF

  1004. Total 71 found in round 4
  1005. FBB*
  1006. F*LB
  1007. FFLB
  1008. BLLB

  1010. FBBB
  1011. F*L*
  1012. FFLB
  1013. BLLB

  1015. FFB*
  1016. FLLL
  1017. FLBB
  1018. *BBB

  1020. FFBB
  1021. FLLL
  1022. FLB*
  1023. *BBB

  1025. FFBB
  1026. FLLL
  1027. FLB*
  1028. BB*B

  1030. FFBB
  1031. FLLL
  1032. FLBB
  1033. **BB

  1035. FFBB
  1036. FLLL
  1037. FLBB
  1038. *B*B

  1040. FFF*
  1041. FLL*
  1042. BLBB
  1043. BLBB

  1045. FFF*
  1046. FLLB
  1047. BLB*
  1048. BLBB

  1050. FFF*
  1051. FLLB
  1052. BLBB
  1053. *LBB

  1055. FFF*
  1056. FLLB
  1057. BLBB
  1058. BL*B

  1060. FFFB
  1061. FLLB
  1062. BLB*
  1063. BL*B

  1065. FFFB
  1066. B*FL
  1067. BLLL
  1068. *BBB

  1070. FFFB
  1071. B*FL
  1072. BLLL
  1073. B*BB

  1075. *BBF
  1076. BL*F
  1077. BLFF
  1078. BLLB

  1080. BBBF
  1081. *L*F
  1082. BLFF
  1083. BLLB

  1085. BBFF
  1086. LLLF
  1087. *BLF
  1088. B*BB

  1090. BL*B
  1091. BLB*
  1092. FLLB
  1093. FFFB

  1095. *BBB
  1096. BLLL
  1097. B*FL
  1098. FFFB

  1100. B*BB
  1101. BLLL
  1102. B*FL
  1103. FFFB

  1105. BB*B
  1106. FLB*
  1107. FLLL
  1108. FFBB

  1110. BLLB
  1111. FFLB
  1112. F*L*
  1113. FBBB

  1115. BLLB
  1116. FFLB
  1117. F*LB
  1118. FBB*

  1120. BFFF
  1121. LF*B
  1122. LLLB
  1123. BB*B

  1125. BFFF
  1126. LF*B
  1127. LLLB
  1128. BBB*

  1130. BFFF
  1131. BLLF
  1132. *BLB
  1133. B*LB

  1135. B*BB
  1136. *BLF
  1137. LLLF
  1138. BBFF

  1140. BLLB
  1141. BLFF
  1142. *L*F
  1143. BBBF

  1145. BLLB
  1146. BLFF
  1147. BL*F
  1148. *BBF

  1150. BB*B
  1151. LLLB
  1152. LF*B
  1153. BFFF

  1155. BBB*
  1156. LLLB
  1157. LF*B
  1158. BFFF

  1160. B*LB
  1161. *BLB
  1162. BLLF
  1163. BFFF
复制代码

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

点评

aimisiyou
只经历四轮就能分出胜负或是平局吗？暴力枚举的话可以确定胜负，但怎么判断是平局？除去暴力枚举的胜负情形，剩下的就是平局吗？  发表于 2021-5-27 15:19
mathe
先手输的局面。第一轮第二轮等就是前面楼上描述的迭代过程。所以所有第一轮的结果都是先手马上没有任何位置可以移动的。  发表于 2021-5-27 13:32
aimisiyou
这是先手必胜的初始局面吗？1、2、3轮是啥意思？  发表于 2021-5-27 09:56
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

王守恩
发表于 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种填法
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-23 16:13 , Processed in 0.030587 second(s), 21 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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