I am testing various rating systems (Elo rating and some alternatives). I need a"world" with computer players participating in championships. Computer players are characterized by two parameters:
(1.1) Depth of search (probability to search yet another ply deeper)
(1.2) Probability to remember the outcome in their previous games. (Relatively high)
(1.3) Probability to learn from "published games". (Relatively low)

I tried tic-tac-toe, but there are two problems:
(2.1) Players learn too fast. (Decreasing learning rate turns it in a toss-a-coin)
(2.2) Ply count is granular. The difference between "can/cannot see a fork" or "can/cannot see opponent's fork/one move win is huge.

A battleship game doesn't have complete information. A game like chess or five in a raw would require prohibitively large amount of memory to remember all possible combinations.


closed as too broad by Philipp, Vaillancourt, Kromster says support Monica, Josh Jul 11 '16 at 15:57

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ I don't understand why you need to remember all possible combinations. \$\endgroup\$ – Tryss Jul 10 '16 at 2:22


I don't know where you're drawing the line for a 'prohibitively large' data set, but a quick and naive consideration (read: definitely not even optimal) can store a board state in a maximum of 264 bits, and most will be far shorter. (Don't store info for captured/removed tokens.)

Your tree will be pretty big but storage requirements are pretty lightweight.

There's also various toothpick games like the one described at https://answers.yahoo.com/question/index?qid=20070410190739AAa18a3 . Such games are generally more complex than tic tac toe, but still very manageable.

  • \$\begingroup\$ Can you please explain? For checkers you have (64!)/(24!*40!) ~250649105469666120 possibilities for positions. It would require some ~250649Tb per player and I don't think I can afford that... I will definitly look in toothpick games, than you for the advice!. spots to place my checkers. Opponent's checkers have about as many possibilities. \$\endgroup\$ – sixtytrees Jul 9 '16 at 23:54
  • \$\begingroup\$ That particular game is actually more simple than tic-tac-toe.... \$\endgroup\$ – sixtytrees Jul 10 '16 at 0:53
  • \$\begingroup\$ Checkers is indeed big. You can trim the numbers you have a bit (not all 64 spaces can hold a token) but yeah, still out of reach for the kind of analysis you're thinking of. It's an interesting stepping stone for later though, considering how much simpler the rules are than for chess. \$\endgroup\$ – UserNotFound Jul 10 '16 at 1:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.