cheva in pataia

Also known as: straccia camicia, beggar-my-neighbour, pelagalletto, $other_italian_dialect_variation...

Cheva in pataia is an attempt to build a database of all possible games of the Italian variation of Beggar-my-Neighbour (the main differences are that Italian cards are used, so a deck is composed of 40 cards, and instead of using aces and court cards, the Italian variation uses the ace, two and three). For more information about the rules of the game, see Wikipedia (or, see the Italian page). The key feature you should know is that the game is purely deterministic: given a starting deck of cards, the players actually never have a decision to make, just rules to follow. Which means that the outcome of a game can be simulated very easily.

The main purpose is (now) to find all of the infinite games which exist in the Italian edition.

On the infinite games

Riccardo Zanotto, aka drago96, started the research many years ago building an engine in C++ of the Python equivalent for Beggar my Neighbour. The research proved successful, because as far as I could find it was indeed the first game of Straccia Camicia which eventually repeats and goes on forever.

After doing some preliminary research in order to answer my friend's question, (see below, in NSFAQ), I did some maths with the engine that I made (and optimised) to answer her questions. The engine I made was very efficient, and so I decided that building a full database of all the possible games, noting of all of the longest and infinite games possible, was going to be a very fun side project.

Engine benchmarks

$ ./camisa.test -test.run=NONE -test.bench=.
goos: linux
goarch: amd64
pkg: zxq.co/howl/chevainpataia/camisa
cpu: AMD Ryzen 7 PRO 4750U with Radeon Graphics
BenchmarkEachGameWithPlay-16             1000000              1976 ns/op
BenchmarkEachGame-16                    259035284                4.828 ns/op
BenchmarkPlay-16                         1459186               817.3 ns/op
BenchmarkPlayParallel-16                 8319580               125.6 ns/op
PASS

16 threads, 8 cores. So while the benchmarks are to be taken with a grain of salt¹, if we were to take the last benchmark it would mean that even just on my PC we could do millions of matches per second (8 million).

The total number of permutations possible is mathematically known as the "permutation of multisets." The reason this is not just 40 factorial is that when modelling the game, for the purpose of calculating the results we don't care for values other than 1, 2, 3 or 0 (0 being any other card with no special effect). So our deck comes out to be four 1 cards, four 2 cards, four 3 cards and twenty-eight 0 cards. With these repetitions (which mathematicians like to call "multisets"), we can determine how many games are possible: 40!/(28!*4!*4!*4!)

As our friend Wolfram demonstrates, 193 trillion is a big number... but, unlike some others I could speak of, it still stands in the realm of "understandable by a human brain". Like - we talk about US GDP in trillions of dollars, so 193 trillion starts to be the kind of number of things that you could give a bunch of PCs to solve them without spending too much money, especially when a single one of them can run through millions of them at a time.

Distributed computing

Of course, not having a supercomputer in the back of my house, I decided that in order to do this it would have been a good idea to distribute the workload that would have to be tackled so that I could potentially scale this horizontally with many servers. Which is where the real fun of this whole operation began.

The research is currently on-going. If you have computing power to donate, feel free to get in touch: Telegram, or email: the [at] howl [dot] moe.

The games are distributed by a central server which manages the results and the chunk database and a client which actually performs the computations. The client and server communicate via each other via GRPC on top of SSL/TLS for security.

The information we store is not exclusively about infinite games, but it includes the following:

• The number of games won by the first player
• The number of games won by the second player
• The distribution of games, per number of moves.
• The distribution of games, per configuration of the winning hand (ie. how many 1s, 2s and 3s it had)
• The specific decks of long (>3750 moves, a threshold calculated with a tool) and infinite games.

Server

The server distributes games from a custom-built index file, games.index, and stores the results encoded in protobuf in the results directory. Could I have used an existing database solution? Absolutely. Would it have been anything as fun? Absolutely not. Hence the Cheva in Pataia Game Index

All the games are split into 509,675 chunks, each containing 379,819,440 games. The index file stores all of the "starting keys" of each of these 509k chunks, which are mapped to a single uint64 value keeping track of whether the chunk was leased to a client or is resolved.

Client

The client then starts running the games on the chunk it has been assigned. (This will generally be done for as many threads as the host machine has). It computes the games to calculate using Aaron Williams' algorithm, as described in his 2009 paper "Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts". The algorithm is insanely efficient and a stand-alone implementation can be found here. For our purposes, it was reimplemented in Go in the engine subdirectory (camisa).

Hacking

You're welcome to explore the functioning of this remarkably overengineered research!

The code is split into a few packages: the camisa package contains the main implementation of the engine and the permutation algorithm. The gindex package contains the implementation of the index file, and the rpc package is simply the GRPC proto files to generate the server/client communication files. All the executables of the tools used are stored in the cmd sub-directory. :)

TLS set-up

(Mostly a reminder for myself if I need to do this again :) )

# https://github.com/FiloSottile/mkcert for installation
# do this in a separate directory on your computer, and then upload the
# certificates and keys accordingly to each server
# (i use ecdsa because the keys are shorter and i like them :) but you can use
# standard rsa as well)
export TRUST_STORES='none'
export CAROOT="$PWD"
mkcert -install -ecdsa
# if you update the following, change it in CP_SERVER_NAME below
mkcert -ecdsa cheva.zxq.co
mkcert -ecdsa -client host1.cheva.zxq.co

# executing the server and the client
CP_CA=path/to/rootCA.pem \
	CP_SERVER_CERT=path/to/cheva.zxq.co.pem \
	CP_SERVER_KEY=path/to/cheva.zxq.co-key.pem \
	go run ./cmd/chevanet-server
CP_CA=path/to/rootCA.pem \
	CP_CLIENT_CERT=path/to/host1.cheva.zxq.co-client.pem \
	CP_CLIENT_KEY=path/to/host1.cheva.zxq.co-client-key.pem \
	CP_SERVER_NAME=cheva.zxq.co \
	go run ./cmd/chevanet-server

Not-so-frequently asked questions

• Where does the name come from?
  The italian game has a variety of local names. Cheva in pataia (which you could pronounce as kevin pataya) is the name in the Modenese dialect.
• How did you start doing this?
  A friend of mine taught me the game a while ago, and asked "Wouldn't it be nice to calculate if the first or second player has more chances of winning". Wouldn't it indeed. Then, after calculating that the entirety of the matches were solvable in a reasonable timeframe (factorials are really dangerous), I started on this quest to find All the Infinite Games™️.
  (The answer is that the first player has slightly better chances)
• Are there any plans to do this on Beggar my Neighbour?
  Seeing as the engine is undoubtedly more efficient than the Python version which is currently on GitHub, an attempt to find an infinite game will undoubtedly be done, though a full-scale analysis like the current one is very unlikely seeing as the permutations on 52 cards are about 6 orders of magnitude larger.
  I will do some research with the final data trying to determine if a pattern can indeed be found to the infinite games, while also testing other non-existing variants with 20 and 10 cards.
• What's the license?
  GNU GPL.
• Are you insane?
  Maybe, maybe not.

See also

• https://sites.google.com/site/alessandrogentilini/pelagalletto-infinito-beggar-my-neighbour
• https://github.com/drago-96/cavacamisa

---

---

1. The test is the following. It tries to work closely to the real-world scenario by generating many different matches (the deck is regenerated every 16 runs), but obviously real-life performance, where we also need to worry about storing data and reporting it, is going to be a bit different. ↩︎