Grid Computing for Artificial Intelligence

- Grid Computing for Artificial Intelligence.
- Scientific computing, calculation of the accurate value of π, search for Mersenne prime numbers, analysis of protein molecular structure, weather dynamics, data analysis, business data mining, simulation are examples of application for grid computing.
- On the other hand, grid computing using idle resources on the Internet may be running on the reasonable cost..
- They are not only a popular game but also a target in the research of artificial intelligence..
- It is described by Dan (4) that the grid systems for Shogi is effective in reduction of computational complexity with collaboration from computational resources on the Internet.
- A solution to next move problems as artificial intelligence systems will be discussed in more detail in the chapter..
- The chapter introduces the history and current state of computer Shogi systems, and the applicaion of grid computing for thinking routines for next move problems, then proposes an idea of the interaction between human and grid computing in game theory.
- Moreover, we suggest possibility of the human grid computing for artificial intelligence systems.
- It is described that the present situation of computer Shogi systems and the possibility of the human grid computing which assists the position evaluation function with human intuition..
- Proposed model in the chapter seems to be applied to any other efficient systems.
- While the design of the human grid computing is only proposed, the development and the implementation of that are left open..
- In the autumn of 2010, the grid system for Shogi is going to challenge against a human expert player of Shogi.
- Not only the human grid computing organized by amateur Shogi players but also the grid computing system constructed on the Internet may win against Meijin before 2015, when we predict as the X day..
- Grid technology is applied to large-scale computing, such as numerical simulation and data analysis not only in the academic research but also in the business world.
- Idle resources of a large number of computers on the internet can realize high performance computing equivalent to supercomputers.
- We can say that we have already had an inexpensive supercomputer on the Internet..
- Natural sciences have been based the framework of mathematics to describe phenomena in the physical world.
- Almost all of the models of natural phenomena can be described for the corresponding ordinary or.
- On the other hand, there are many unsolved models of differential equations even in the classical physics.
- Newton succeed in solving two body problems in gravitational fields, however, he were faced the difficulty in solving many body problems in the same framework.
- Differential equations know the motion of the Sun and the Earth interacting by gravitation, they cannot provide the clear solution with fundamental functions to the problem of the motion of the Sun, the Earth and the Moon exactly.
- We know the reason why mathematical analysis has these limitation in the existence of chaos which often appear in the nonlinear phenomena..
- In the latter half of twentyth century, scientific comupation was made in a variety of fields..
- According to the progress of computers, we can use a large scale of computation for artificial intelligence based on the model of natural sciences.
- Moreover, the number of computers on the Internet has grown like hotcakes, we obtain another choice for grid computing.
- There is possibility of high performance grid computing for artificial intelligence than cluster system in the present time..
- In the following sections, we describe the history of research in artificial intelligence, construction of grid computing, and the application to the battle against human intelligence..
- What are we able to do by grid technology? In other words, what does grid technology enable to do anything impossible so far? An answer proposed in the work of Dan (4) is to implement computer Shogi systems as artificial intelligence by human-computer interactions.
- There are ten researchers interested in the study of machine intelligence, artificial newral networks and automata theory.
- The CSA has motivated the leading researchers in the field and provided place to exchange ideas at academic symposiums such as the series of Game Programming Workshops..
- However, it is not enough to run programs which need a plenty of resources on the computers in decades ago.
- Hence, we will have more effective performance when we brush up the algorhithm or discover new algorithm for solving difficuties in the research of high performance computing including artificial intelligence..
- Table 1 shows the history of main events in the artificial intelligence researches..
- This was a major success for computer game-playing and a milestone in the history of computer sciences..
- to a maximum of forty plies in some situation, although the system speed varied widely, depending on the specific characteristics of the positions being searched.
- No one in the world can win against the strongest computer chess system even on ordinary PC at the present time..
- Iida, Sakuta and Rollason in (10) described the current state of the art for this game..
- Finally, one of the crucial difference between chess and Shogi is the complexity of game-trees, which is significantly higher in Shogi than in chess.
- 30 in Shogi, and B ( j ) for j ≥ 3 depends on the previous move and the present position.
- In the newest research, it is expected that computer Shogi systems will defeat Meijin in 2015 at the earliest..
- The core algorithms for thinking routine of computer Shogi systems are analysis of the game tree and pruning using the alpha-beta method from min-max tree for evolutionary sequence of positions.
- Given position information including array of pieces on the board, pieces in hands and the next player, the position evaluation function returns the value of the position forward several steps..
- When initial position is given, all legal hands of the next player are genarated, say h 1 and h 2 for the hands.
- In order to select the best hand, all legal hands of the opposite player are genarated by recursive call.
- Although a computer program seeks as many positions as possible, almost all of the evolutionary sequence seems not to be valid clearly even for amateur players.
- There is a pseudo-code for the thinking routine of min-max method by recursive call in the appendix..
- Position evaluation functions return values from the status of position including array of pieces on the board, pieces in hands and the next player given as arguments..
- The value for each pieces on the board is important factor to estimate the position.
- where p denotes the array of position of all pieces on the board, h pieces in the hand of both players, t which is the next turn.
- mean the status of check mated for each player, which is used in the program like this: For every evaluated real number v, v <.
- although a player decrare to finish the game before that in the real play..
- Opening game, middle game and end game are different each other in evaluation, computers feel difficulties in the evaluation of middle game.
- They are not good at overlooking on the board in the global point of view, however, almost perfect opening game for a huge scale of databases and end game for logical thinking..
- 4.3 Shogi using grid computing.
- Marsland and Popowich (13) proposed the parallel implementation of the alpha-beta search algorithm of game trees on distribution systems as a methematical model..
- A grid system is like a supercomputer but uses with computational resources on the Internet..
- Grid computing is a possible technology solution for deeper search of the algorithms for computer Shogi systems.
- Although each computer does not have so high performance, the total performance of the connected computing resources surpasses super computers, when each individual computer is properly allocated to appropriate jobs..
- If initial state of the Shogi position has B possible hands, one more deeper search will become possible by the B grid computers, two more deeper search by the B 2 grid computers.
- On the other hand, T = G/ρ where G in (1) is the number of node of game tree and ρ is the ability to calculate the position evaluation function per unit time, say ρ for Deep Blue..
- Grid computing attains high throughput in enormous search of the optimized solution, however, it keeps bottleneck that the case of clearly misdirected search is not different from that without grid computing.
- Figure 5 shows a next move problem in the Meijin title match held on 17 June, 2008.
- In the real play, Yoshiharu Habu use a pieces in hand near opposite King on the board which is not so easy, but there are many misdirected plies seen even if amateur Shogi players.
- 4.4 Human grid computing.
- This system is proposed for chess by Althofer in 1980, which is stronger than the person who is selecting one of the opinions proposed by two other advisors..
- The computer Shogi by grid systems throws jobs to client computers on the internet.
- Such client computers run the position evaluation functions, as they display the process and the result of calculation, and then return the value of the evolutionary sequence of positions back to the grid server.
- It improves efficiency in enormous search of the next move, if amateur Shogi players in front of the screens dismiss negative results..
- where M is the number of amateur Shogi players, regardless of the correctness.
- On the other hand, evaluation system for human intuition is indispensable.
- Although there are lots of computing resources on the Internet, we do not use that without the permission of their owners.
- The performance of grid systems depends on the number of computational resources on the Internet..
- Let us consider the number of computing resources constructed for grid systems, following from the discusstion on the growth of social networks according to Dan (5).
- Let N be the total number of the computing resources on the Internet to be estimated which is a positive constant for a while in our discussion, n ( t ) be the number of active computing resources for use which is also a function of time t.
- According to the process, the probability of the growth is proportional to both n ( t ) and N − n ( t.
- In the right hand side of this equation, teh terms n ( t ) and N − n ( t ) denotes incoming and outgoing effect respectively.
- The differential equation (6) is derived from our model for the growth of the number of computing resources on the Internet..
- Integrating both side of the equation, we have 1.
- which is known as one of the logistic curves.
- If the total number of the Internet is not constant, say does increase, then we should consider another differential equation for the spread of grid computing.
- Because of the comparison of growth rates, that is, dn ( t.
- It is constructed for a council system of four different Shogi programs on 169 Intel Xeon CPUs with 676 cores in the University of Tokyo as a cluster system.
- On the other hand, Ichiyo Shimizu is the top of the woman Shogi players who takes the match against Akara 2010.
- The goal of the project is the day when Akara defeats the human Shogi champion as Deep Blue did in 1997.
- Since Akara won against Shimizu, we can see the challenge with Akara 2011 in the next chance..
- The chapter suggests the progress of the grid computing and the possibility of human grid computing for artificial intelligence systems for Shogi.
- It is described that the present situation of computer Shogi systems and the possibility of the human grid computing which assists the position evaluation function using human intuition.
- In the most advanced systems, position evaluation functions are constructed by the parameters which are determined by the technology of machine learning.
- Deep Blue had an extreme performance in the search of game trees in chess specially for the human champion, so that the full-width search was very efficient at the challenge to Kasparov..
- We also introduced Akara 2010 in the project of game computing in Japan, which is expected as the first computer program to win against the human champion of Shogi.
- Computing performance have grown up in the exponential rate of Moore’s law, so that it is certain to exceed the strength of human abilities, although the information systems for Shogi need to process astronomical number of combinations of possible positions to move..
- Grid computing has difficulties in the growth of performance efficiently, however, we expect to gather a large number of computing resources in the Internet.
- Grid computing faces at the limitation we estimated in the theory of growth, or logistic curve generalized..
- On the other hand, human grid computing cannot be a pure artificial intelligence system..
- However we expect the reduction of the game tree search or investigation in Shogi.
- While the design of the human grid computing is proposed, the development of that remains open..
- Shiro Uesugi for useful suggestions and improvements on the earlier version of the work at the ITeS workshop.
- of the 2008 International Symposium on Applications and the Internet (SAINT 2008) in Turku, Finland.
- He also thanks Takehiro Moriya for fruitful discussion on the most advanced grid computing technology..
- Proceedings of The Game Programming Workshop, Computer Shogi Association, pp