Game playing computers & artificial intelligence go Bang – The Game


Download 490 b.
Sana07.12.2017
Hajmi490 b.


GAME PLAYING COMPUTERS & ARTIFICIAL INTELLIGENCE

  • Go Bang – The Game

  • Presented to:

  • Pascal Hitzler

  • &

  • Sebastian Bader

  • Presented by: Zulqernain Akhter


GOBANG(Go-moku)

  • Introduction ( History )

    • Go Bang(Go-moku)
    • Renju
  • Description of the Games

    • Classification of Game Type
    • Rules of Game
    • How to Play
    • Variant (Other Row-Games)
    • Computer as an opponent


GOBANG(Go-moku)



INTRODUCTION

  • History:

    • It is very old five-in-a-row game kakugo ( year 100 A.D. )
    • In Japan they played on a 19x19 Go-board since about 700 A.D.
    • when Go was introduced in Japan from China.
    • The ancient Chinese game of wutzu as prototype of the Five-In-A-Row games.
    • Winner is known as Japanese “Meijin” named in game “Renju”, means “five pearls in a row“.
    • In 1931 Nobel prize winner Yasunari Kawabata "The Master of Go“, proposed the change from Go-board from 19x19 to 15x15
    • intersections.
    • COMPUTER OLYMPAID GAMES in the year 2000 predicted Go-Moku as a Solved Game.


RULES OF GAME

  •   



HOW TO PLAY

  • Players may decide how many cells of the

  • lattice may be used for the game.

  • For example:-

  • A 10x10 lattice (100 cells)

  • or

  • The entire 15x15 lattice (225 cells).

  • Each player in turn moves one stone one

  • space to the next empty cell either horizontally,

  • vertically, or

  • diagonally.



VARIANT (OTHER ROW GAMES) Row or Mill Games - Morris - Linea - Tabula – Mühle-TTT

  • Free-style Go-moku:

  • An overline (six consecutive moves) win.

  • Standard Go-moku:

  • Only five stones as win.

  • Tic-Tac-Toe(333-game):

  • Three consecutive markers on a restricted 3x3 board.

  • Othello 8x8 as variant of Gobang(Go-moku).



COMPUTER AS AN OPPONENT



SEARCHING STRATEGY

  • ALPHA-BETA SEARCH



PROOF NUMBER SEARCH

  • DECISION

    • Best-First search method
    • Cost function used for decision (which node to expand next) to prove the goal.
  • If empty point can make x 5 in a line, computer moves and wins. Game over.

  • Else if there was a empty point which can make o 5 in a line, then computer

  • moves the step to the point.

  • Else Calculate all the values of empty points:

  • Plus100 to value of the empty point which can make opponent 4 in a line.

  • Plus 90 to value of the empty point which can make computer 4 in a line.

  • Plus 80 to value of the empty point which can make opponent 3 in a line.

  • Plus 70 to value of the empty point which can make computer 3 in a line.

  • Plus 60 to value of the empty point which can make opponent 2 in a line.

  • Plus 50 to value of the empty point which can make computer 2 in a line.



Three different definitions of a solution

  • Three different definitions of a solution

  •      Ultra-weakly solved: the game theoretic value of the initial position has been determined.

  •  

  •    Weakly solved: for the initial position, a strategy has been determined to achieve the game-theoretic values against any opposition.

  •  

  •       Strongly solved: such a strategy has been determined for all legal moves.

  •  



The Category-3 games are solved by a combination of expert knowledge, threat-space search, threat-sequence search, proof-number search,as well as alpha-beta search.

  • The Category-3 games are solved by a combination of expert knowledge, threat-space search, threat-sequence search, proof-number search,as well as alpha-beta search.

  • For both free-style and standard Go-moku, Allis [Ref. VU, NL] established that the game theoretic value is a first-player win.

  • Go-moku & Renju have same State-space and Game-tree complexities.



  • Future Research can be splitted into three areas

  • Leftovers of current investigations.

  • Selection of fragment, player wants to play in.

  • Question remains: Is a long-term strategy computable by a machine?

  • Weakly solve the remaining variants of Connect Five – different board-sizes, different rules – including:

    • free-style and standard Go-moku on smaller boards.
    • Go-moku with new Opening Rules, including swapping.
    • Renju with opening rules.
  • 4th Computer Renju Tournament (2004) and Solving Problems Competitions.

  • Discover minimax-win solutions from opening positions.

  • Strongly-solve weakly-solved games.



  • Computer Olympaid Games in the year 2010 predicted:

    • Awari, Othello, and Checker(8x8) as Solved Games.
    • In Scrabble, computers are believed to be closed to perfect play.
    • Lines of Action (LOA)
    • Amazons
  • The Prospects of both are rather different.

  • LOA has complexity similar to Othello.

  • LOA is a game, for which interest only arose recently.

  • At the fifth Computer Olympaid three strong LOA programs participated.

  • Expectation for LOA game not to be solved before 2010.

  • Assumption of weak solution is possible, but

  • Best Solution is expected in the year 2010.



Amazons is a game with a Complexity comparable to that of Go.

  • Amazons is a game with a Complexity comparable to that of Go.

  • For Competitive programs, simple evaluation functions work quite reasonable.

  • Due to variety of possible moves and branching factor, Amazons will only be solved on relatively small boards,

  • Since a game starts with 8 Amazons and every move exactly fills one empty square, the initial position on m x m boards with odd m favours the First Player.

  • The Second Player has an advantage IF m is even.

  • Conclusion:

  • Many additional games with Mathematical properties recently have come to the attention of Computer Scientists.




Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling