algorithm - 计算国际象棋 Material 组合数量的简单方法

Question

在国际象棋中，一名棋手可以拥有不同的 Material 组合，例如:

“1后，2车，2马，2象，8兵+王”是一个组合

如果玩家失去一名主教:

“1后，2车，2马，1象，8兵+王”是另一种组合

..之后，如果一个棋子晋升为骑士，那么:

“1后，2车，3马，1象，7兵+王”是另一种组合

好的，以下组合无效:

“5个后，5个车，5个马，5个象，2个兵+国王”

因为你缺乏可以推广的棋子。 (5 个皇后 = 需要 4 个棋子)(5 个车 = 需要 3 个棋子)，等等，所以需要 4 + 3 + 3 + 3 = 13 个棋子。由于棋盘上有 2 个棋子，那么最多可以升级 6 个棋子。无效。

有多少种有效的 Material 组合？ 我使用以下 C 代码计算了 8694 个组合。问题是:

您是否找到更简单/高效的算法来计算它？ (更少的周期、更少的计算、更清晰的代码等)...甚至是数学公式？

total = 0;
for (queens=0;queens<=9;queens++)
for (rooks=0;rooks<=10;rooks++)
for (bishops=0;bishops<=10;bishops++)
for (knights=0;knights<=10;knights++)
for (pawns=0;pawns<=8;pawns++)
{
    pawnsRequested = 0;
    if (queens>1) pawnsRequested += queens - 1;
    if (rooks>2) pawnsRequested += rooks - 2;
    if (bishops>2) pawnsRequested += bishops - 2;
    if (knights>2) pawnsRequested += knights - 2;
    if (8-pawns < pawnsRequested) continue;
    total++;
}
printf("%i\n",total); 

Answer 1

如果棋子类型是独立的，那么我们可以直接相乘:皇后的 10 种可能性乘以车的 11 种可能性，等等。但是，我们需要跟踪典当的使用情况。有一个数学技巧叫做 generating functions我们可以将车的可能性编码为

3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8,

其中x的幂表示使用的棋子数量，系数表示可能性的数量。这里，存在三种不需要升级棋子的可能性(0,1,2)，一种需要一个升级棋子(3)，一种需要两个升级棋子(4)，等等。现在我们可以将每个因子相乘(分别为后、车、象、马、兵)。

  (2 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (3 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)
* (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)

这是来自 Wolfram Alpha .

1 到 x^8 的系数，它们是 0 到 8 的可能性数量所需棋子为 54、135、261、443、693、1024、1450、1986、2648，总计 8694。