20171008

The Quest For Ultimate Game Between Humans And Computers


I think Game Theory is one of the main branches of Computer Science.
A lot is known about theoretical and practical complexity of common games like Chess, Go, Checkers, Backgammon, Poker and their so many possible variants. Like how hard they are for classical (and quantum?) computers in basic brute force search view point, or in multiple general smart search algorithms view points, or in best known customized search points of view.

In recent years there were multiple big game matches between human grand masters and classical computer software (set of algorithms) running on various types of computers, with different processing speed, number of processors, number of processing cores, memory size and speed. First I heard was a then-world-champion human lost to a (classical) computer in Chess. Later I heard about a human grand master lost to a (classical) computer in Go.

One may think humans eventually will lose against classical computers in any given game, and for against quantum computers (which are much more powerful) humans will never have any chance.
But if we look at the current situation closer I think it is still unclear.

Are those famous Chess and Go matches between human grand masters and classical computers were really fair for both sides?
I think not. In both cases both software analyzed countless historical matches and became expert on every move of those matches.
Which human grand masters have such knowledge/experience and would be able to recall any of them at any moment in a game they are playing? Can there be any more fair way?

What if a Chess/Go software (intentionally) started the game matches, with having no knowledge of any other past game matches other than its own (games it played against itself)? And also isn't it obvious a human grand master would best recall the games he/she played himself/herself in the past? Wouldn't a Chess/Go match between a human grand master and a computer be much more fair with such a constraint for the computer side?

Can we make game matches between humans and (classical) computers even more fair?

I think humans lost at Chess first, because number of possible future moves does not increase (exponentially) fast enough, so a classical computer of today is able to handle it well.
In Go however, number of possible future moves does increase (exponentially) fast enough. The computer software used a deep learning ANN software, instead of relying on its ability to check so many possible future moves. So unlike in Chess, the computer did not have powerful future foresight ability. But is this mean, computers would eventually beat any human at any similar board game, using an ANN and/or future foresight ability?

I think it is possible ANN approach worked successfully for Go because its rules are much simpler than Chess as an example. I don't think there is any evidence (at least not yet) ANN approach would always work against any board game. Also consider board size for chess (8 by 8) is much smaller than Go (19 by 19), which means number of possible future moves does increase much faster for Go, so a (classical) computer cannot handle it.

How about we try combine the strength of Go (against future foresight) with rule complexity of Chess? For example there is a variant of Chess called Double Chess that is played on a 12 by 16 board. I think we could reasonably expect a game match between a human (grand) master and any classical computer (hardware + software), to be much more fair for both players than any past matches. I think because number of possible future moves should increase similar to Go (if not even faster) because of closer board size and usage of multiple kinds of game pieces (which are able to move in different ways). Also consider how many high quality past game examples would be available to learn/memorize for both sides, which I am guessing should not be so many for Double Chess.

So if we used Double Chess for game matches between humans and computers, can we find out the ultimate winner for sure? What if the computer wins again, would that really mean the end for human side for sure?

Assuming we lost again, what if we created an even more complex (for both humans and computers) variant of Chess by using an even larger board? Like if we turned Double Chess into Double Double Chess?
And/or what if we added few of the proposed new chess pieces to the game? Could then we really create a board game that no classical computer (hardware + software) could ever beat a human master player?

Why this is important?
Because I think the question actually goes far beyond deciding the final outcome of a friendly and fair battle between the creators and their creations. What is human brain really? It is an advanced classical computer or a quantum computer or an unknown kind of computer? How human grand masters of Chess/Go play the game compared to computers? Are humans rely only on past knowledge of the game playing and future foresight as much as they can manage?
Or humans have much more advanced algorithms running in their brain compared to computers? I think how a human player decides game moves is definitely similar to how an ANN algorithm does it but it is still beyond that. Think about how we make decisions in our daily lives in our brains every moment. Any given time we have a vast number of possibilities to think about. Do we choose what to think about every moment randomly? If there are certain probabilities (which depends on individual past life experiences), how we make choices between them every moment, again and again, fast. I think most reasonable explanation would be if our brains are, not classical, but quantum computers. (So neurons must be working like qubit registers.)

And if that is really true, it would mean no classical computer (hardware and software) could ever beat a human brain in a fair game.

(Also if human brain is a quantum computer, how about the rest of human body? The possibilities would be Quantum Computer (QC), classical computer (Turing Machine (TM)), Pushdown Automaton (PDA), Finite State Machine (FSM). To decide, I think we could look at (Functional) Computer Models of biological systems. Are they operate like FSM, PDA, TM, QC? Do their algorithms have conditional branches, conditional loops like a program for a TM? Or they always use simple state transitions like a FSM? I don't know much about how those modelling algorithms work; My guess is they are like TM (which would mean human body (except brain) operate like a classical computer.))

https://en.wikipedia.org/wiki/Game_theory
https://en.wikipedia.org/wiki/Computer_chess
https://en.wikipedia.org/wiki/Computer_Go
https://en.wikipedia.org/wiki/List_of_chess_variants
https://en.wikipedia.org/wiki/Double_Chess
https://en.wikipedia.org/wiki/Automata_theory
https://en.wikipedia.org/wiki/Finite-state_machine
https://en.wikipedia.org/wiki/Pushdown_automaton
https://en.wikipedia.org/wiki/Turing_machine
https://en.wikipedia.org/wiki/Quantum_computing
https://en.wikipedia.org/wiki/Modelling_biological_systems

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.