michi

[hgm]

I'm curious if any work has been done on Pente:

https://en.wikipedia.org/wiki/Pente

You win by getting five stones in a row OR capturing five pairs of enemy stones. I'm not sure how one would balance the two possible objectives.

Capturing five pairs takes a relatively long time compared to the more short term five-in-a-row threats.

There was a competition on what is called 'Outer-Open Gomoku', which seems a very similar game. It had five participants.

[Ajedrecista]

Hello:

Actually, 8x8 checkers was "weakly solved" by Chinook in 2007 as being a draw with best play.

http://spectrum.ieee.org/computing/soft ... ers-solved

jm

What a miss! I completely forgot about Chinook. The web of the project is here:

http://webdocs.cs.ualberta.ca/~chinook/

You can read all about Chinook in the book, 'One Jump Ahead' written by Jonathan Shaeffer.
This really is a very good read, and this book should be in the library of every serious zero-sum game programmer.

Regarding One Jump Ahead Computer. Perfection at Checkers, the revised edition of 2009 has the following index:

Code: Select all

========
CONTENTS
========

I Feel I Can’t Lose                                                    1

The Opening Game                                                       3

1 This Was Going To Be Easy                                            5
2 Bottomless Well                                                     25

The Middle Game                                                       35

3 Valuable Lessons                                                    37
4 The Illusion of Intelligence                                        55
5 A Nobel Turing Trio                                                 73
6 Didn’t Samuel Solve That Game?                                      87
7 The Case for the Prosecution                                        99
8 As Close to Perfection As Humanly Possible                         123
9 You Look Like a Checkers Player                                    131
10 The Fudge Factor                                                  143
11 I Feel Like a Teenager Again                                      169
12 Gentlemen, Start Your Engines                                     197
13 Trust Me                                                          223
14 A Wake-Up Call                                                    231
15 Prelude to Disaster                                               247
16 Programmed by God                                                 275
17 Divine Intervention                                               299
18 Dissension Within the Ranks                                       323
19 Home Away From Home                                               347
20 It’s a Draw!                                                      365
21 Let Me Suggest the Unthinkable                                    377

The End Game                                                         405

22 Gentlemen’s Agreement                                             407
23 I’m Ready to Go                                                   417

The Game Score                                                       427

24 As Good As God                                                    429
25 The Final Frontier                                                439
26 Quiet Satisfaction                                                459
27 As Close to Perfection as Computationally Possible                475
28 I Know I Can’t Lose                                               491
29 Past and Present                                                  511

The Game Players                                                     515

30 Sluicing for Gold by Robert Lake                                  517
31 A Long Journey by Paul Lu                                         523
32 Recollections and Reflections by Norman Treloar                   525
33 Personal Recollections by Martin Bryant                           531
34 Solving the Problem of a Checkers Solving Program by Neil Burch   535
35 Checkered Past by Rebecca Schaeffer                               539
36 Checkered Out by Steph Schaeffer                                  543

The Game Stats                                                       547

Appendix A: Further Reading                                          549
Appendix B: Tinsley’s Record                                         553
Appendix C: CHINOOK’s Record                                         557
Appendix D: CHINOOK Technical Specifications                         559
Appendix E: Tinsley–CHINOOK games                                    561
Appendix F: Proof Statistics                                         573

I hope this index of contents will encourage someone to read the book.

------------------------

I see that Fabien registered on http://laatste.info and that he shared the games of Scan, which will be open source.

Happy to see that there is more life beyond chess in computer AI games! Even 2048 game had its place in ICGA Leiden 2015.

Regards from Spain.

Ajedrecista.

[lucasart]

You don't have to go so outlandish as Go.

Xiangqi and (mini-)Shogi are already more interesting. And at least some of the familiar techniques, such as alpha-beta, are still useful there. And of course there is Draughts, in which real progress is still possible, as Fabien has now demonstrated.

Other games that are of interest to AI researchers and have competitions in the ICGA Olympiad are Amazons, Clobber and Surakarta. And you could of course try to do Arimaa.

There are thousands of obscure variants that almost nobody plays. Not much fun doing a program that can play some "made up" game that almost nobody plays. That takes care of Amazons, Clobber, Surakarta and Arimaa (and thousand others).

Xiangqi: I don't know.

Shogi: I fell asleep half-way through the wikipedia page that explains the rules, the myriad of special cases and variants. My brain is not big enough to store all the possible moves and special rules. I'm not even talking about all the crazy variants, like Taikyoku Shogi. Not interested. The true beauty is when you create infinite complexity with simple rules: that is what makes Go beautiful and Shogi comparably ugly, in my opinion.

Checkers: I never found that game interesting. I learnt checkers when I was a kid, and my uncle told me: checkers is what we teach children, when you grow up I'll teach you chess. He was right. I find the game uninteresting. As for computers: 8x8 is solved, and 10x10 computer are playing quasi perfect on a completely different scale as humans. It's more fun if there are still some humans stronger than the best program. It's a challenge to beat humanity, more interesting than to beat another tuned to death program that uses the same algorithm with some micro differences.

[zamar]

Go seems really more interesting.

I fully agree! In the field of computer go there are a plenty of ideas to be explored.

Just for fun I've written my own simple computer go program. It's just MCTS + patterns + some basic tactical checks. On 9x9 board it's a bit stronger than gnugo.

I'd love to start seriously working on it, but because my time is very limited, it's likely not going to happen in the near future...

One of the interesting topics is around combining MCTS and local tactical searches (alpha-beta or proof-number) in a clever way...

[Bloodbane]

You can read all about Chinook in the book, 'One Jump Ahead' written by Jonathan Shaeffer.
This really is a very good read, and this book should be in the library of every serious zero-sum game programmer.

I've read 'One Jump Ahead' as well, it really was a great book. I especially liked the random parts explaining the limitations of the hardware back then. It's one thing to hear "oh, we had 16MB of RAM back then" and another to understand what that actually meant in practice.

You don't have to go so outlandish as Go.

Xiangqi and (mini-)Shogi are already more interesting. And at least some of the familiar techniques, such as alpha-beta, are still useful there. And of course there is Draughts, in which real progress is still possible, as Fabien has now demonstrated.

Other games that are of interest to AI researchers and have competitions in the ICGA Olympiad are Amazons, Clobber and Surakarta. And you could of course try to do Arimaa.

There are thousands of obscure variants that almost nobody plays. Not much fun doing a program that can play some "made up" game that almost nobody plays. That takes care of Amazons, Clobber, Surakarta and Arimaa (and thousand others).

Xiangqi: I don't know.

Shogi: I fell asleep half-way through the wikipedia page that explains the rules, the myriad of special cases and variants. My brain is not big enough to store all the possible moves and special rules. I'm not even talking about all the crazy variants, like Taikyoku Shogi. Not interested. The true beauty is when you create infinite complexity with simple rules: that is what makes Go beautiful and Shogi comparably ugly, in my opinion.

Checkers: I never found that game interesting. I learnt checkers when I was a kid, and my uncle told me: checkers is what we teach children, when you grow up I'll teach you chess. He was right. I find the game uninteresting. As for computers: 8x8 is solved, and 10x10 computer are playing quasi perfect on a completely different scale as humans. It's more fun if there are still some humans stronger than the best program. It's a challenge to beat humanity, more interesting than to beat another tuned to death program that uses the same algorithm with some micro differences.

My thoughts almost exactly. I have a friend who likes Xiangqi and has tried to get me to play it, but the game is seems to be far less beautiful than chess or go in my opinion.

[hgm]

Shogi: I fell asleep half-way through the wikipedia page that explains the rules, the myriad of special cases and variants. My brain is not big enough to store all the possible moves and special rules. I'm not even talking about all the crazy variants, like Taikyoku Shogi. Not interested. The true beauty is when you create infinite complexity with simple rules: that is what makes Go beautiful and Shogi comparably ugly, in my opinion.

The rules of Shogi are hardly more complex that those of international Chess. One could even argue they are simpler. (It does not have castling or e.p. capture, for instance, no special initial moves like the Pawn double-push, and every piece captures as it moves.) It is played by millions of people, and generally considered a better game than international Chess by those who know both (like Larry Kaufman...).

As for the variants: there are literally orders of magnitude more variants of international Chess than there are of Shogi. It is silly to judge a game, or your ability to learn it by how many variants people made on it.

Go is a good game, but looks very alien to a Chess player. My experience is that Shogi looks very natural to a Chess player, especially if you have some bughouse experience. Much more so than Xiangqi. From a programming perspective Shogi is very similar to Chess, although it poses some problems unique to it, which require creative solutions rather tna mindless implementation of existing algorithms.


As to relative obscurity of some of the game-theoretically interesting games: you will have many more enthousiastic and grateful users even for an AI that plays obscure games than when you build the umptieth Chess engine that is more than 100 Elo behind the #1.

[Evert]

As to relative obscurity of some of the game-theoretically interesting games: you will have many more enthousiastic and grateful users even for an AI that plays obscure games than when you build the umptieth Chess engine that is more than 100 Elo behind the #1.

I can second this (and third, fourth...)
Hell, I have had more positive feedback on the fact that Sjaak plays Maharaja and the Sepoys than on the chess-playing ability of any program I ever wrote.

[Isaac]

The true beauty is when you create infinite complexity with simple rules: that is what makes Go beautiful and Shogi comparably ugly, in my opinion.

In my opinion the rules of the game of Go are extremely complex, in particular the counting part. There are many rules for counting (Japanese rules, Chinese rules, etc.) and I don't think they are easy at all. Most go programs aren't programmed to count with Japanese rules for instance (or when they do, they have bugs that makes them lose in the end, that happens for Zen for example).
Even pachi doesn't even know what's a seki and it will suicide if you give it a final position where it's in seki.
As of now we don't have a program that tells you who wins with 100% certainty in a final position, unlike chess where the rules are, IMO, much easier to learn and understand.

I'm ranked 4 kyu in KGS (slightly below the average player) and I don't even know how to count in the game of go (I once tried to understand bent 4, super ko and stuff like that that's required for one to say "I know the rules" but I failed).

[zamar]

In my opinion the rules of the game of Go are extremely complex, in particular the counting part. There are many rules for counting (Japanese rules, Chinese rules, etc.) and I don't think they are easy at all. Most go programs aren't programmed to count with Japanese rules for instance (or when they do, they have bugs that makes them lose in the end, that happens for Zen for example).
Even pachi doesn't even know what's a seki and it will suicide if you give it a final position where it's in seki.
As of now we don't have a program that tells you who wins with 100% certainty in a final position, unlike chess where the rules are, IMO, much easier to learn and understand.

I'm ranked 4 kyu in KGS (slightly below the average player) and I don't even know how to count in the game of go (I once tried to understand bent 4, super ko and stuff like that that's required for one to say "I know the rules" but I failed).

1) Have you heard of "the logical rules of go"?
- http://tromp.github.io/go.html
These are extremely close to Chinese rules

2) Superko = Don't repeat the previous position. (Positional superko = Only the position matters. Situational superko = Position + side_to_move matters)

3) I agree that counting for a human during the game is difficult (My kgs top rank is 3 kyu, but nowadays I rarely play at all, so my current rank is around 5-6 kyu), but for a program it's straightforward.

[Isaac]

In my opinion the rules of the game of Go are extremely complex, in particular the counting part. There are many rules for counting (Japanese rules, Chinese rules, etc.) and I don't think they are easy at all. Most go programs aren't programmed to count with Japanese rules for instance (or when they do, they have bugs that makes them lose in the end, that happens for Zen for example).
Even pachi doesn't even know what's a seki and it will suicide if you give it a final position where it's in seki.
As of now we don't have a program that tells you who wins with 100% certainty in a final position, unlike chess where the rules are, IMO, much easier to learn and understand.

I'm ranked 4 kyu in KGS (slightly below the average player) and I don't even know how to count in the game of go (I once tried to understand bent 4, super ko and stuff like that that's required for one to say "I know the rules" but I failed).

1) Have you heard of "the logical rules of go"?
- http://tromp.github.io/go.html
These are extremely close to Chinese rules

2) Superko = Don't repeat the previous position. (Positional superko = Only the position matters. Situational superko = Position + side_to_move matters)

3) I agree that counting for a human during the game is difficult (My kgs top rank is 3 kyu, but nowadays I rarely play at all, so my current rank is around 5-6 kyu), but for a program it's straightforward.

1)No, I haven't. Interesting, I didn't know. Are those rules what programs are usually using?
2)I'm not understanding the difference(s) between a super ko and ko, but I could fix this by searching on the web.
3)I don't know how to count in the game of go at all. If it wasn't for the automatic counting at the end, I would be lost. I basically play with intuition only and I have no idea whatsoever in terms of points how good/bad moves are.


Also I don't know the details of bent 4 (nor what it is) and how Chinese and Japanese rules deal with it. I don't think these concepts are easy to grasp for people new to the game.
Overall my point is that chess rules are simpler to learn and understand than go rules even though they may appear somewhat arbitrary (for instance the en passant rule or the fact that pawns may move 2 squares ahead for their first move).