[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 59 KB, 350x304, xiangqi.jpg [View same] [iqdb] [saucenao] [google]
4759536 No.4759536 [Reply] [Original]

So we know computers can beat the best human at chess or at least western chess, but what about other variants, like Chinese chess, go etc?

>> No.4759540 [DELETED] 

>implying the chinese aren't human
well after seeing that person run over that baby and that chinese/malaysian mother beat her toddler with a pillow...

>> No.4759548
File: 18 KB, 140x122, 1338914292869.png [View same] [iqdb] [saucenao] [google]
4759548

>>4759540
coolstorybro, gb2 /pol/

>> No.4759550

It's just a matter of better predictive power. I don't know how much more complex Go is compared to chess.

>> No.4759552

>>4759540
This is about chinese chess and other variants of chess, not about chinese people, you dense fucking retard.

>see the word chinese in a post
>DERP HERP MUST TALK ABOUT CHINESE PEOPLE

No one cares about the people, now fuck off before you derail this thread into some /pol/ shit.

>> No.4759570

>>4759550
Very complex. Right now computers are -alright-, but light years from beating the best human players.
Of note are the somewhat surprising performances of zen, which is 5d kgs right now.

http://gogameguru.com/man-machine-showdown-board-game-go/
http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/

We still need crazy advances in programming if we want them to be equal. Merely giving them more computational power only works for chess.

>> No.4760615
File: 41 KB, 300x225, aarima basic.jpg [View same] [iqdb] [saucenao] [google]
4760615

Arimaa was invented specifically to be hard for computers to play.
Good topic, get in here anon!

>> No.4760627

I think winning and losing is only part of the process of playing a game like this. Chess and Go are fantastic ways for understanding how the other thinks and there is more than right and wrong, but numerous combinations of styles. They deal with expectation, adaptation and awareness of the other. Computers are not really trained to play these games "well", but to beat the other. It's like handling a gun to a martial artist, it won't make him the best martial artist...

I don't see the appeal in playing with computers.

>> No.4760630

Computers don't play chess. The software that runs on the computers does. Of course, the hardware needs to be capable running such said program.

Since nobody has invested the time, energy and resources into developing a program to rival top human Chinese chess players, the answer to your question is no.

>> No.4760633

>>4760627
A very valid point. Beasley in The Mathematics of Games (excellent read, by the way) specifically mentions the paradox of the fact a game of pure strategy can only truly be considered a "game" if both players are sufficiently incompetent.

>> No.4760641

>>4760630
People don't play chess, the memories, procedures, and likely groups of neurons devoted to playing chess stored in the brain play chess. Of course, the hardware needs to be capable of processing such things.

>> No.4760645

>>4760633
Exactly! I'll check that book.

>> No.4760655

There was a chart showing the progress of AI for various games. Keep bumping the thread until someone posts it.

>> No.4760675

Draughts was weakly solved. It has a game-tree complexity of <span class="math">10^31[/spoiler]. It took Chinook's team 18 years worth of analysing data to do that. How faster would a quantum computer (in principle, of course) have solved it? According to wikipedia, "applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires roughly <span class="math">2^{n/2}[/spoiler] invocations of the underlying cryptographic algorithm, compared with roughly <span class="math">2^n[/spoiler] in the classical case". This is a very hand-wavy assumption, but we can think of weakly solving a game as checking all strategies and finding the single best one, much like checking all possible codes and finding the only one that works. As such, a quantum computer (if we replace all the bits by qubits) has the power of a classical computer squared, and in 18 years, a game with tree complexity of <span class="math">10^62[/spoiler] could be solved. Again, very hand-wavy, but an interesting thought.

>> No.4760676

>>4760641
10/10

>> No.4760679

>>4760630
>Computers don't play chess. The software that runs on the computers does.

Holy shit, you're literally autistic.

>> No.4760684

>>4760630
-1/10

>> No.4760697
File: 76 KB, 495x1013, game_ais.png [View same] [iqdb] [saucenao] [google]
4760697

>>4760655
it was xkcd

>> No.4760703

>>4760697
>seven minutes in heaven
i lol'd

>> No.4760719

>>4759570
deep blue beat kasparov line 15 years ago
Making a computer good enough to play chess is just a matter of raw power to calculate the best possible move. Its really simple.

>> No.4760723

>>4760719
Finding best possible move isn't simple

>> No.4760725

It'd be much easier for computers to win at games like GO b/c they're simpler.

>> No.4760726

>>4760697
>starcraft

Lol, the AI cannot beat an average player unless it cheats (extra money, omniscient vision, etc)

>> No.4760731

>>4760723
In the purest brute force algorithm its simple as fuck. Its very heavy and resource demanding, but simple.

Of course, if you want to find the best move in an efficient, fast way, then its complicated. But that is a mathematics problem, not a computing one.

Its like people forget that computing is nothing but discrete maths done really fucking fast.

>> No.4760737

>>4760726

talking about the built in ai from 1998, or bots?

>> No.4760764

>>4760725
Define "simpler".

>> No.4760767

>>4760725
What? No. Go is harder to program AI for.

http://en.wikipedia.org/wiki/Computer_Go#Why_humans_are_.28still.29_better_at_Go

>> No.4760776

>>4760731
> The purest brute force algorithm.

The purest brute force algorithm would involve calculating the entire game tree of chess. We still haven't done that. We can't do that. Algorithms require need some way to estimate the strength of a position. This requires thought.

>> No.4760800

>>4760776
>calculating the entire game tree of chess
And that's just a matter of computational power.

Anyway, you can limit the depth and breath of the tree, and just determine the value of each branch via some parameter like number of your pieces vs his piece or something.

>> No.4760804

>>4760800
> And that's just a matter of computational power

Computational power we still don't have.

>> No.4760810

>>4760800
That wouldn't work. Simplistic heuristics like that fail against decent players.

>> No.4760858

>>4760804
You could compute the tree offline and just navigate thru it online. That would be way better

>> No.4760863

>>4760858
What are you talking about, it would take a really long time to even generate the tree once

>> No.4760888

>>4760863
What a really long time?
1 day?
1 month?
5 years?

All doable.

>> No.4760918

>>4760888
Computing the entire tree is impossible, since there are infinitely large branches. Even if we cap the game to (2 x) 50 turns. Then there is still a tree of size (# of moves)^100. On average, a player has significantly more choices than 10, but lets round down (initially it's 16, 2 choices per pawn, in the mid and late game the queen alone will have more than 10 choices). Then the tree is of size 10^100. Assume an extremely powerful computer that can compute a 100,000 steps/second. Then it'll take you 10^95 seconds. That's 10^87 years. Good luck.

>> No.4760949

It's amazing how such simple games can lead to such complex problems.

That nearly sounded like philosophy...

>> No.4760959

>>4760888
You are really stupid.

>> No.4760961

>>4760697
>no othello

>> No.4760997

>>4760918
You do realize its just a matter of time before we have computers that can do that in 1 second, right?

Moore's law

>> No.4761005

>>4760997
That will take a fuck-ton of time with Moore's Law.

>> No.4761009

>>4760997

You honestly don't know how big that number is, do you?

>> No.4761010

>>4760997
The number of configurations of chess pieces is larger than the number of atoms in the universe. If you can even calculate the tree, you litterely can transform all matter of the universe into disk space, and still not have enough space.
Lrn2combinatorics.

>> No.4761022

>>4760961
>implying othello wasn't a dumb marketing name for reversi

>> No.4761020

>>4761005
And? Its not like we're in a hurry.

We can wait.

>> No.4761036

>>4761022
>implying it isn't the other way around

>> No.4761037

>>4761020
Even if Moore's law continues, at a rate of 50% more computing power per year, it'll take more than half a millenium to reach that type of speed. (Take the base 1.5 log of 10^95.)
And that was the optimistic estimate of only 10 moves per turn. In reality, it's more like 30 moves per turn. In which case it'll take you over 1500 years of waiting for technology to develop.
I would like to point out that energy consumption of chips has also been increasing at a similar rate, and that such a chip would consume over 10^30 times more energy then is used world wide today.

>> No.4761040

>>4761010
compression

>> No.4761048

>>4761040
Google shannon entropy.
Also, refrain from talking about shit you don't understand, and listen to those who do understand.

>> No.4761055

>>4761037
Waiting 2000 years and getting enough computing power to compute the whole chess tree or the number of atoms in the universe seems pretty good to me.

The energy might be an issue, specially if we hit peak oil.

>> No.4761071

The only chance we have for tasks like this is quantum computing.

>> No.4761075

>>4761055
The point is that it's a contradiction. I don't know the solar engergy output, but I'm guessing the ballpark is about the same as the potential chip would use to operate. It's not possible.

>> No.4761082

>>4761075
Its not as if in 2k years there's gonna be any kind of paradigm shift or major invention that will change how computers work or how hardware draws power.

Its not as if it happened at least 3 times in the last 80 years.

>> No.4761089

>>4761082
You don't know what you're talking about, do you?
You want to use Moore's law, then use it properly.
None of the paradigm shifts have essentially changed the energy output per computation (perhaps several factors, but not billions of factors, like computational power).
You need to invest energy for state changes. We are already at atomic level. We can't go much further. What do you want? Less than a Planck energy per computation?