当前位置：文江博客话题详情

洗牌并发一副有限制的牌

发布于 2024-10-19 13:34:05 字数 375 浏览 5 评论 0原文

首先是事实。

桥牌游戏中有 4 个名为 North、South、East 的玩家西方。
所有 52 张牌均发给 13 张牌给每个玩家。
有一个荣誉计数系统。 Ace=4 点，King=3 点，Queen=2 点点和 Jack=1 点。

我正在创建一个具有约束条件的“发牌者”，例如，您可能会说向北发牌的手牌必须恰好有 5 张黑桃，并且荣誉计数点在 13 到 16 之间，其余手牌是随机的。

如何在不影响“随机性”的情况下以最佳方式实现这一点并且还具有有效的代码？

我正在使用 C# 和 .Net 进行编码，但使用伪代码的一些想法会很好！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夏日浅笑〃 2024-10-26 13:34:05

由于有人已经提到了我的 Deal 3.1，我想指出我在该代码中所做的一些优化。

首先，为了获得最灵活的约束，我想向我的经销商添加完整的编程语言，这样您就可以使用不同类型的评估器和规则生成完整的约束库。我使用 Tcl 来开发该语言，因为我已经在工作中学习它，并且在 1994 年 Deal 0.0 发布时，Tcl 是嵌入到 C 应用程序中最简单的语言。

其次，我需要约束语言运行得相当快。约束在循环的深处运行。我的经销商中的相当多的代码都很少使用查找表等进行优化。

最令人惊讶和最简单的优化之一是在检查该席位的约束之前不向该席位发牌。例如，如果您希望北匹配约束 A，南匹配约束 B，并且您的约束代码是：

 match constraint A to north
 match constraint B to south

那么只有当您到达第一行时才填写北手。如果失败，您将拒绝整个交易。如果通过，接下来填写南手并检查其约束。如果失败，就放弃整个交易。否则，完成交易并接受它。

我在进行一些分析时发现了这种优化，并注意到大部分时间都花在随机数生成器上。

有一种奇特的优化可以在某些情况下发挥作用，称为“智能堆叠”。

 deal::input smartstack south balanced hcp 20 21

这会为南手生成一个“工厂”，需要一些时间来建造，但随后可以非常快速地填充南手以符合此标准。由于条件概率问题，智能堆叠一次只能应用于每笔交易的一手牌。 [*]

智能堆叠采用“形状类”（在本例中为“平衡”）、“保持评估器”（在本例中为“hcp”）以及保持评估器的一系列值。 “持有评估器”是应用于每个花色然后求和的任何评估器，因此 hcp、controls、losers 和 hcp_plus_shape 等都是持有评估器。

为了使智能堆叠有效，持有评估器需要采用一组相当有限的值。智能堆叠如何工作？这可能比我在这里发布的时间要多一些，但它基本上是一组巨大的表格。

最后一点评论：如果您真的只想要这个程序用于投标练习，而不是模拟，那么很多这些优化可能是不必要的。这是因为练习的本质决定了不值得花时间去练习极其罕见的叫牌。因此，如果您遇到的情况在十亿笔交易中只出现一次，您可能真的不想担心它。 :)

[编辑：添加智能堆叠细节。]

好的，一套花色中正好有 8192=2^13 种可能的牌。按长度和荣誉数对它们进行分组：

 Holdings(length,points) = { set of holdings with this length and honor count }

现在

 Holdings(3,7) = {AK2, AK3,...,AKT,AQJ}

列出与

 h(length,points) = |Holdings(length,points)|

您的形状条件匹配的所有形状（黑桃 = 5）：

 5-8-0-0
 5-7-1-0
 5-7-0-1
 ...
 5-0-0-8

请注意，所有可能的手形状的集合的大小为 560，因此这个列表并不大。

对于每种形状，通过列出每种花色的荣誉点，列出获得所需总荣誉点的方法。例如，

 Shape    Points per suit
 5-4-4-0  10-3-0-0
 5-4-4-0  10-2-1-0
 5-4-4-0  10-1-2-0
 5-4-4-0  10-0-3-0
 5-4-4-0  9-4-0-0
 ...

使用我们的集合 Holdings(length,points)，我们可以计算获取每一行的方法数。
例如，对于行 5-4-4-0 10-3-0-0，您可以：

h(5,10)*h(4,3)*h(4,0)*h(0,0)

因此，根据计数的相对概率随机选择其中一行，然后对于每种花色，从正确的 Holdings() 集合中随机选择一个控股。

显然，手形和点的范围越广，需要预先计算的行数就越多。再多一点代码，您仍然可以使用一些预先确定的牌来完成此操作 - 如果您知道黑桃 A 或西方的整手牌或其他什么。

[*] 理论上，您可以解决多手智能堆叠的条件概率问题，但该问题的解决方案仅对极其罕见的交易类型有效。这是因为工厂表中的行数大致是一只手堆叠的行数乘以另一只手堆叠的行数的乘积。此外，h() 表必须以将 n 张牌划分为手牌 1、手牌 2 和其他手牌的方式数量为关键，这会将值的数量从大约 2^13 更改为 3^13 个可能值，大约大两个数量级。

Since somebody already mentioned my Deal 3.1, I'd like to point out some of the optimizations I made in that code.

First of all, to get the most flexibly constraints, I wanted to add a complete programming language to my dealer, so you could generate whole libraries of constraints with different types of evaluators and rules. I used Tcl for that language, because I was already learning it for work, and, in 1994 when Deal 0.0 was released, Tcl was the easiest language to embed inside a C application.

Second, I needed the constraint language to run fairly fast. The constraints are running deep inside the loop. Quite a lot of code in my dealer is little optimizations with lookup tables and the like.

One of the most surprising and simple optimizations was to not deal cards to a seat until a constraint is checked on that seat. For example, if you want north to match constraint A and south to match constraint B, and your constraint code is:

 match constraint A to north
 match constraint B to south

Then only when you get to the first line do you fill out the north hand. If it fails, you reject the complete deal. If it passes, next fill out the south hand and check its constraint. If it fails, throw out the entire deal. Otherwise, finish the deal and accept it.

I found this optimization when doing some profiling and noticing that most of the time was spent in the random number generator.

There is one fancy optimization, which can work in some instances, call "smart stacking."

 deal::input smartstack south balanced hcp 20 21

This generates a "factory" for the south hand which takes some time to build but which can then very quickly fill out the one hand to match this criteria. Smart stacking can only be applied to one hand per deal at a time, because of conditional probability problems. [*]

Smart stacking takes a "shape class" - in this case, "balanced," a "holding evaluator", in this case, "hcp", and a range of values for the holding evaluator. A "holding evaluator" is any evaluator which is applied to each suit and then totaled, so hcp, controls, losers, and hcp_plus_shape, etc. are all holding evalators.

For smartstacking to be effective, the holding evaluator needs to take a fairly limited set of values. How does smart stacking work? That might be a bit more than I have time to post here, but it's basically a huge set of tables.

One last comment: If you really only want this program for bidding practice, and not for simulations, a lot of these optimizations are probably unnecessary. That's because the very nature of practicing makes it unworthy of the time to practice bids that are extremely rare. So if you have a condition which only comes up once in a billion deals, you really might not want to worry about it. :)

[Edit: Add smart stacking details.]

Okay, there are exactly 8192=2^13 possible holdings in a suit. Group them by length and honor count:

 Holdings(length,points) = { set of holdings with this length and honor count }

 Holdings(3,7) = {AK2, AK3,...,AKT,AQJ}

and let

 h(length,points) = |Holdings(length,points)|

Now list all shapes that match your shape condition (spades=5):

 5-8-0-0
 5-7-1-0
 5-7-0-1
 ...
 5-0-0-8

Note that the collection of all possible hand shapes has size 560, so this list is not huge.

For each shape, list the ways you can get the total honor points you are looking for by listing the honor points per suit. For example,

 Shape    Points per suit
 5-4-4-0  10-3-0-0
 5-4-4-0  10-2-1-0
 5-4-4-0  10-1-2-0
 5-4-4-0  10-0-3-0
 5-4-4-0  9-4-0-0
 ...

Using our sets Holdings(length,points), we can compute the number of ways to get each of these rows.
For example, for the row 5-4-4-0 10-3-0-0, you'd have:

h(5,10)*h(4,3)*h(4,0)*h(0,0)

So, pick one of these rows at random, with relative probability based on the count, and then, for each suit, choose a holding at random from the correct Holdings() set.

Obviously, the wider the range of hand shapes and points, the more rows you will need to pre-compute. A little more code, you can still do this with some cards pre-determined - if you know where the ace of spades or west's whole hand or whatever.

[*] In theory, you can solve these conditional probability issues for smart stacking with multiple hands, but the solution to the problem would make it effective only for extremely rare types of deals. That's because the number of rows in the factory's table is roughly the product of the number of rows for stacking one hand times the number of rows for stacking the other hand. Also, the h() table has to be keyed on the number of ways of dividing the n cards amongst hand 1, hand 2, and other hands, which changes the number of values from roughly 2^13 to 3^13 possible values, which is about two orders of magnitude bigger.

回复收藏 0 原文

薄凉少年不暖心 2024-10-26 13:34:05

由于这里的数字非常小，您可以采取启发式方法：随机发牌，评估约束条件，如果不满足则再次发牌。

回复收藏 0 原文

咆哮 2024-10-26 13:34:05

根据您的计算机的速度，执行此操作可能就足够了：

重复：
- 进行随机交易
直到董事会满足所有约束条件

与所有性能问题一样，要做的就是尝试一下并看看！

编辑我尝试了一下，发现：

done 1000000 hands in 12914 ms, 4424 ok

这没有考虑任何优化 - 它每秒产生 342 手，符合您的标准“北有 5 黑桃和 13-16 荣誉点”。我不知道您的申请的详细信息，但在我看来这可能就足够了。

Depending on how fast your computer is, it might be enough to do this:

Repeat:
- do a random deal
Until the board meets all the constraints

As with all performance questions, the thing to do is try it and see!

edit I tried it and saw:

done 1000000 hands in 12914 ms, 4424 ok

This is without giving any thought to optimisation - and it produces 342 hands per second meeting your criteria of "North has 5 spades and 13-16 honour points". I don't know the details of your application but it seems to me that this might be enough.

回复收藏 0 原文