估计合法象棋位置的数量-C/C++开发

  • C4_783308
    了解作者
  • 4.6MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-29 21:38
    上传日期
ChessCounter ChessCounter尝试准确计算合法棋位置的数量。 克劳德·香农(Claude Shannon)首先估算了大约1E + 43 che ChessCounter ChessCounter试图准确计算合法棋位置的数量。 克劳德·香农(Claude Shannon)在1950年首先估计了大约1E + 43棋位置:[1]。 维克托·艾利斯(Victor Allis)提到已计算出5E + 52的上限,并假设真实的空间复杂度接近1E + 50 [2]。 John Tromp提出4.5E + 46 [3],可能提出7.7E + 45,Will Entriken提供2.4E + 49 [4],而Shirish Chinchalkar提供1.8E + 46 [5]。 Arshia Atashpendar无需任何计算即可计算出7.22E + 40
ChessCounter-master.zip
内容介绍
# ChessCounter **ChessCounter tries to accurately calculate the number of legal chess positions.** Claude Shannon first made an estimate of around 1E+43 chess positions in 1950: [[1]](https://vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf). Victor Allis makes a mention that an upper bound of 5E+52 has been calculated and assumes the true space-complexity to be close to 1E+50 [[2]](https://www.dphu.org/uploads/attachements/books/books_3721_0.pdf). John Tromp came up with 4.5E+46 [[3]](https://tromp.github.io/chess/chess.html) and possibly 7.7E+45, Will Entriken with 2.4E+49 [[4]](https://groups.google.com/g/rec.games.chess.computer/c/vmvI0ePH2kI) and Shirish Chinchalkar with 1.8E+46 [[5]](https://content.iospress.com/articles/icga-journal/icg19-3-05). Arshia Atashpendar calculates 7.22E+40 without any promotions, castling, or en passant [[6]](https://zenodo.org/record/163434/files/Graduate_thesis_Arshia.pdf). There are some more attempts here: [[7]](https://codegolf.stackexchange.com/questions/19397/smallest-chess-board-compression). As we can see there is a large variety of estimates. This program attempts to do it in a more documented and systematic way to come up with a better answer. ## General case search space First, we place two kings. This can be done in 3,612 different legal ways (so that they are not on neighboring squares). Now we pick squares where we will place the pieces. There can be from 2-2=0 to 32-2=30 squares chosen out of the remaining 64-2=62 squares. There are 10 different non-king pieces that can be placed in each of these squares (Q, R, B, N, P, q, r, b, n, p). The number of possible combinations for m non-king pieces is 10^m. Each of them can be white-to-move or black-to-move. The total sum of pseudo-legal unique positions to consider is therefore 2 * 3612 * Sum(Comb(62, m) * 10^m, m=[0, 30]) = 3580731277913911451307082034763461066056798885824504 (3.58E+51). 100s of billions of samples from 3.58E+51 positions is enough to get 100s of thousands of hits and get a decent estimate of the number of legal positions. However, we we'd like to reduce the sampling space further. One way to do it is to first select w white pieces and then b black pieces. This will mean that we won't have to sample from impossible positions like with 16 white non-king pieces and 14 black non-king pieces. We get 2 * 3612 * Sum(Sum(Comb(62, w) * 5^w * Comb(62-w,b) * 5^b, w=[0,15]), b=[0,15]) = 568159542837347293680664103149567870390294979574504 = 5.68E+50 combinations and our search space has been reduced to less than 1/6th of what it was. ## Restricted case search space Disallowing underpromotions and limiting queens to three per side reduces the search space greatly. There are now at most 3 queens, 2 knights, 2 bishops, 2 rooks, and 8 pawns per side. 2 * 3,612 * Sum(Sum(Sum(Sum(Sum(Sum(Sum(Sum(Sum(Sum(Comb(62,wp) * Comb(62-wp,bp) * Comb(62-wp-bp,wn) * Comb(62-wp-bp-wn,bn) * Comb(62-wp-bp-wn-bn,wb) * Comb(62-wp-bp-wn-bn-wb,bb) * Comb(62-wp-bp-wn-bn-wb-bb,wr) * Comb(62-wp-bp-wn-bn-wb-bb-wr,br) * Comb(62-wp-bp-wn-bn-wb-bb-wr-br,wq) * Comb(62-wp-bp-wn-bn-wb-bb-wr-br-wq,bq),wp=[0,8]),bp=[0,8]),wn=[0,2]),bn=[0,2]),wb=[0,2]),bb=[0,2]),wr=[0,2]),br=[0,2]),wq=[0,min(min(3,15-wp-wn-wb-wr),30-wp-wn-wb-wr-bp-bn-bb-br)],bq=[0,min(min(3,15-bp-bn-bb-br),30-wp-wn-wb-wr-bp-bn-bb-br-wq)]) = 10969175368880644381707380652409200270873861528 (1.10E+46) combinations. Analogously, the search space for even more restricted case with one queen per side is 2.12E+43. ## Monte Carlo search This program uses a Monte Carlo approach - it samples billions of random positions out of these possibilities and applies various rules to check whether each sample position is legal and whether castling or en passant are possible. When estimating the number of "likely" legal positions (restricted use case above), we need to make sure to sample proportionally to the number of positions for each combination of the number of various pieces. There are 933,156 such combinations to choose from. Some of the positions might have castling and en passant rights, increasing the number of possibilities. The program only looks at positions with white-to-move (and doubles the result). It counts the number of possible castling moves and en passant moves and weighs each random sample position as more than 1 when it’s needed. For example, if a position allows white short, white long, and black short castling and there are black pawns on f5 and c5 (with empty squares at f6, f7, and c6, and c7) and white pawns at g5 and b5, it will be counted at 2^3 * 3 = 24 positions. Since we might be looking at trillion+ positions, we're using a 64-bit PRNG with at least 128 bits of state (PCG or JSF work well). ## Rules The following rules for determining if a position is legal are used (white-to-move): 1. No pawns on 1st or 8th rank 2. At most 16 pieces per side 3. At most 8 pawns, 9 queens, 10 bishops, 10 rooks, 10 knights per side 4. The total number of promoted pieces plus the number of pawns per side can’t be more than 8. A piece is counted as promoted if it is a 2nd+ queen, 3rd+ rook, 3rd+ knight, 3rd+ bishop, or a 2nd bishop that is on the same-colored squares as the 1st bishop 5. The number of promoted pieces (counted separately for white and black) can’t be more than the number of captures of pieces. E.g. if there is an extra white queen and an extra black bishop, it means that at least 1 piece of any side was captured. 6. One capture of a pawn allows 3 total promotions (2 on the capturing side, 1 on the captured side). 7. A bishop that is not in its starting position can’t be at positions unreachable because of pawns still at their starting positions. E.g. if there is a white pawn at b2, there can’t be a bishop at a1 or if there are black pawns at d7 and f7, there can’t be a bishop at e8. 8. Various pawn structures are impossible from the starting chess position, especially on the sides. For example, white pawns at a2, b2, a3, white pawns at a2, a3, c2, a4, white pawns at a3, a4, b3, c2, white pawns at b2, c2, d2, c3, etc. 9. Each extra pawn on the same file means the opposite-side piece was captured. E.g. if there are white pawns at d2, d4, and d6, it means that at least two black pieces or pawns were captured. Some positions would require two captures, such as white pawns on a2, a4, and b2. 10. If the white pawn is on the same file as the black pawn and it's above it, this means that there was a capture. E.g. white pawn at c7 and a black pawn at c4. 11. If the black king is in check when it’s white-to-move then the position is illegal. 12. If the white king is in check by three or more attackers, the position is illegal. 13. A position in which the white king is checked by two black attackers is legal only under certain circumstances: A. There was a double-discovered en passant move. The white king would have to be above or below the source square of the en passant capturing black pawn. It would have to be attacked through the rays crossing that source square and the square where the captured pawn was previously. B. One of the checking pieces was blocking another currently checking piece from checking previously. This means that, for example, the checks can’t be from two rooks at once (but see C.). If a piece that moved to enable the discovery check has an attacking slider piece behind it that would be checking the white king if the square was empty, that position would have been illegal (black-to-move and white king in check). C. Black previously made a promotion move. The white king would have to be attacked by the promoted piece and this pawn must have been previously blocking another piece from checking. There must be fewer than 8 black pawns on the board now. If the pawn moved diagonally, then there was a capture and there must be fewer than 8 white non-pawn pieces. 14. A position in which the white king is checked by one black attacke
评论
    相关推荐
    • c/c++参考
      c/c++参考,非常全面
    • C/C++程序员面试宝典
      C/C++是最能体现程序员能力的语言之一,其功能强大,在IT行业的各个方面都有大量的应用。一名优秀的C/C++程序员无疑是众多企业所渴求的。本书写作的目的就是为C/C++程序员的求职提供一些参考,让他们能够正确地面对...
    • C语言/C++资料大全(谭浩强)
      含有C程序设计的书和其他资料。例子等。经典C语言程序100例。C语言技术文章。C语言函数大全。其他chm文档是一些关于C++的资料,包含MFC。
    • 希尔排序/c/c++
      希尔排序——希尔排序/c/c++insertionSort.tgz
    • C语言/C++资料大全 个人收集
      C语言C++入门,自学,进阶,这就是你想要的最全的资料。。提供打包下载
    • C/C++ Reference
      CC++参考手册, C/C++ Reference,挺有用的
    • c c++ c/c++ 课件
      c c++ c/c++ 课件 希望给大家帮助
    • C语言/C++集成开发环境 Dev-C++
      C语言/C++集成开发环境 Dev-C++。一款优秀的C/C++集成开发软件。
    • C语言/C++语言参考
      本资料是有关C语言C++语言学习的参考资料。希望能帮助大家搞好C语言
    • c/c++精彩实例,学习C/c++很有用
      c/c++精彩实例c/c++精彩实例c/c++精彩实例c/c++精彩实例c/c++精彩实例c/c++精彩实例