Tak environment

[ViliamVadocz]

Tak

Tak is an abstract strategy board game similar to Go, except pieces can stack on top of each other into the third dimension. There is an active community that plays this game, makes bots and other resources, and hosts tournaments.

I am using Tak as a research environment because it has some interesting challenges for RL. These include a large action space (grows exponentially with board size), situational moves (smashes) that likely require some form of exploration to learn well, and an endgame that becomes more complicated over time instead of simplifying.

I have successfully trained the currently strongest bots using AlphaZero, but I hit a wall when trying to train agents for larger board sizes. I could definitely benefit from a GPU-accelerated implementation of the game so I could eliminate GPU/CPU synchronization (seemingly the bottleneck) in search.

Resources

Rules: https://ustak.org/play-beautiful-game-tak/ Where to play: https://playtak.com/ Analysis board: https://ptn.ninja/ Tak Discord: https://discord.gg/m6su6Bmzwy

Existing Bots (not exhaustive)

Wilem: https://github.com/ViliamVadocz/tak TilTak: https://github.com/MortenLohne/tiltak Taktician: https://github.com/nelhage/taktician Crum: https://github.com/Allybag/takbag Topaz: https://github.com/Jakur/topaz-tak

Reference implementation

Each bot uses their own implementation, but I have previously published mine here:

• https://crates.io/crates/fast-tak/
• https://pypi.org/project/takpy/

Other implementations

Cutak: https://github.com/jpmartin2/cutak Tak-AI: https://github.com/jachiam/tak-ai Schwenger/Tak: https://github.com/Schwenger/Tak RTak: https://reddit.com/r/Tak/s/tJ5pg1LShL TakWeb + TakServer: https://github.com/chaitu236/TakWeb https://github.com/chaitu236/TakServer Tak-sim: https://github.com/akshaykgupta/Tak-sim taklib: https://github.com/Daenyth/taklib tak-game: https://github.com/TehShrike/tak-game tak.hs: https://github.com/Delapouite/tak.hs AI-TakBot: https://github.com/Aditi-Singla/AI-TakBot TakBot: https://github.com/akshittyagi/TakBot node-tak: https://github.com/tak-stuff/node-tak the-game-of-tak: https://github.com/jlink/the-game-of-tak vfridell/Tak: https://github.com/vfridell/Tak gotak: https://github.com/icco/gotak ruby-tak: https://github.com/pusewicz/ruby-tak htak: https://github.com/z0isch/htak

[sotetsuk]

Hi, thank you for requesting a new environment! 👍

I felt like Tak is an interesting game. Right now, we are not placing a significant emphasis on adding new games (instead, we are spending time on writing documentation and adding training examples). However, if Tak proves to be a genuinely new challenge for RL, we may consider adding it to the team's higher priority list. Particularly, it would be preferable if the game has features that are difficult to study with the games currently implemented in Pgx. For example, you mentioned the size of the action space; is it larger than that of Chess? Are there any research papers addressing the difficulty of mastering the Tak environment?

[ViliamVadocz]

For example, you mentioned the size of the action space; is it larger than that of Chess?

Tak is played on several board sizes. At the moment the competitive sizes for humans are 6x6 and 7x7. The action space for each board size is given below:

n       action space
 3               126
 4               480
 5              1575
 6              4572
 7             12495
 8             32704
 9             82863
10            204700
11            495495
12           1179504
13           2768727
14           6422332
15          14745375
16          33554176

To compare, the action space for Chess is 4672. I don't think humans will find sizes beyond 8x8 interesting because the games become very long, but for bots it could be interesting (and also very difficult).

I think it's also important to distinguish between action space (the number of possible actions collectively in any any position), and the branching factor (how many actions are possible on average in a position). For tak, the branching factor increases as the game progresses, starting around 100 and climbing to around 200 by the time we reach 100 plies (for 6x6 in games between higher-rated humans). Comparing to chess, it has a branching factor around 30-40. I think a more useful comparison is Go, which has a branching factor of n^2 for some board size n. Tak has a strictly higher branching factor for a given board size, but of course Go is played on much larger board sizes.

Are there any research papers addressing the difficulty of mastering the Tak environment?

I have not found any, but I am working on one. It will establish the SOTA in Tak as well as contribute a starting point for using Tak as a research environment. The Tak community has produced several bots and puzzle databases which provide a useful benchmarks.

[sotetsuk]

Thank you for your response! As you mentioned, Tak has huge action space. It's interesting. Tak may be a good benchmark for studying huge (discrete) action space.

However, as our human resources are limited, we may attach high priority to Tak after one or two research papers are published (in 1st tier conferences).

[sotetsuk]

Add Tak to the new game candidate list https://github.com/sotetsuk/pgx/issues/980#issuecomment-1806686466 and close this issue