Dong-Ho Shin
email: dhshin@hnu.kr

Robert Hassink
email: hassink@geographie.uni-kiel.de

Jin-Keun Kim

O14 -Industrialization; Manufacturing; Service Industries; Tech Choice < O1

Keywords: cluster life cycle, shipbuilding industry, cluster life cycle, shipbuilding industry, South Korea JEL codes: O14 -Industrialization, Manufacturing, Service Industries, Tech Choice < O1 -

Although South Korean academics and policy-makers have applied industrial districts, regional innovation systems and clusters to study and to promote regional economic development, these concepts have little power to explain the changing economic landscape over time. This paper tackles this question with the help of the concept of cluster life cycle and shipbuilding as a case.

It concludes that the cluster life cycle concept is useful for analyzing and explaining spatial industrial dynamics in Korea, but the distinction between industry life cycle and cluster life cycle is not very relevant in the case of shipbuilding.

Introduction

Despite pronounced interest in the causes and policy lessons of South Korea's economic miracle, relatively little sound academic work has been done on the geography of its success from a theoretical and dynamic perspective [START_REF] Hassink | From Daedeok to Teheran-ro: The Genesis and Development of New Industrial Spaces in South Korea[END_REF]. Although South Korean academics and policy-makers have applied industrial districts [START_REF] Park | Kumi and Ansan: Dissimilar Korean Satellite Platforms[END_REF], regional innovation systems [START_REF]Building a National Innovation System through Regional Innovation Systems[END_REF] and clusters [START_REF]Balanced Development in Globalizing Regional Development? Unpacking the New Regional Policy of South Korea[END_REF] to study and to promote regional economic development, these concepts have little power to explain the changing economic landscape over time. This paper focuses on this question, namely the genesis, Earlier articles on the shipbuilding cluster in South Korea focused on the emergence of the cluster [START_REF] Hassink | South Korea's Shipbuilding Industry: From a Couple of Cathedrals in the Desert to an Innovative Cluster[END_REF] and potential lock-ins hindering its development in the future [START_REF] Eich-Born | On the battle between Shipbuilding Regions in Germany and South Korea[END_REF]. These articles did not deal with the full development course of the cluster life cycle, neither did they compare the industry and cluster life cycle, issues we will deal with in this paper. Moreover, in this article we will use the cluster life cycle concept to put the development of the shipbuilding in perspective in a similar vein to VAN KLINK and DE LANGEN'S (2001) work on the shipbuilding cluster in the Northern Netherlands, and also examine the validity of the core themes of path dependence and cluster life cycle, as described by [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF]. This paper will therefore not only contribute to understanding the spatial-industrial dynamics of South Korea, it will also put empirical flesh on the emerging conceptual bones around cluster life cycles. Moreover, in a broader perspective it will also contribute to the emerging paradigm of evolutionary economic geography [START_REF] Boschma | The aims and scope of evolutionary economic geography[END_REF] by analysing the similarities and differences between the industrial and cluster life cycle and by dealing with the role of national and regional industrial and cluster policy in an evolutionary perspective (see [START_REF] Hassink | Evolutionary approaches to local and regional development policy[END_REF].

The theoretical part of the paper (Section 2) will discuss recent work on clusters, cluster life cycles and cluster dynamics in an evolutionary perspective. Section 3, which comprises the main empirical part of the paper, will describe, analyse and explain the life cycle of the shipbuilding cluster in South Korea. This section will draw on existing work by the authors on the shipbuilding cluster in Gyeongnam [START_REF] Hassink | South Korea's Shipbuilding Industry: From a Couple of Cathedrals in the Desert to an Innovative Cluster[END_REF], expanded by recent publications, expert interviews with officers of the Korean Shipbuilding Association (KOSHIPA) and some policy planning institutions, such as the Korean Institute of Economics and Trade, local

Clusters from an evolutionary perspective

Before dealing with cluster life cycles and the characteristics of the different stages of development in a theoretical way, we will introduce the cluster concept and its critics in a nutshell.

1) Clusters

Much of the literature focuses on developing explanations for the rise of regions in order to contribute to regional economic development theories and learn policy lessons to apply to other regions [START_REF] Scott | New Industrial Spaces[END_REF]STORPER, 1997;STORPER and WALKER, 1989;OECD, 2001OECD, , 2007)).

Economists have also addressed the question of why internationally successful industries tend to concentrate in a few nations or regions [START_REF] Porter | Location, Competition, and Economic Development: Local Clusters in a Global Economy[END_REF].

Thus, geographical 'clustering' of firms in related industries and its implications for regional development have been debated for a long time now (ASHEIM et al., 2006;[START_REF] Cumbers | Introduction: Clusters in Urban and Regional Development[END_REF]. There have been intensive discussions about the extent of clustering at a regional level and the potential economic benefits that might be generated by clustering. It is well-known that the spatial co-localisation or 'clustering' of firms and other organisations in related industrial sectors has the potential for economic and innovation benefits. These benefits have been labelled variously as 'external economies of agglomeration', which support the cooperative and competitive relationships between firms and enable the effectual development and manufacture of products. STORPER (1997) argues that traded interdependencies may be based on upstream and downstream linkages between buyer and supplier firms and untraded Proximity is said to provide social solidarity and trust, face-to-face contact and a pool of skills and know-how.

According to PORTER (2000, p. 16) "a cluster is a geographically proximate group of interconnected companies and associated institutions in a particular field, linked by commonalities and complementarities." Important characteristics are economic interaction in a value chain, strategic inter-firm relations, specialisation, co-operative competition, innovation and diffusion and shared cultural context and interpretation schemes ( VAN KLINK and DE LANGEN, 2001). On the basis of theoretical thoughts on geographic clusters by [START_REF] Porter | Location, Competition, and Economic Development: Local Clusters in a Global Economy[END_REF] and [START_REF] Enright | Regional Clusters: What We Know and What We Should Know[END_REF], a rapidly increasing number of policy initiatives to support clustering of industries has emerged in many countries of the world (see for instance, [START_REF] Porter | Location, Competition, and Economic Development: Local Clusters in a Global Economy[END_REF]ASHEIM et al., 2006;OECD, 2001OECD, , 2007)).

2) Critical voices

Although many authors assume that geographic clusters create economic and innovation advantages, some arguments run counter to the 'benefits from localisation' thesis [START_REF] Enright | Regional Clusters: What We Know and What We Should Know[END_REF]. Potential disadvantages lie in labour cost inflation, inflation of land and housing costs, widening of income disparities, local congestion, environmental pressure, over-specialisation and, last but not least, lock-ins [START_REF] Martin | Deconstructing Clusters: Chaotic Concept or Policy Panacea?[END_REF][START_REF] Hassink | Locked in Decline? On the Role of Regional Lock-ins in Old Industrial Areas[END_REF]. [START_REF] Martin | Deconstructing Clusters: Chaotic Concept or Policy Panacea?[END_REF] are very critical of the ambiguities and identification problems surrounding the cluster concept. In fact, the concept bears many characteristics of what MARKUSEN (1999) [START_REF] Enright | Regional Clusters: What We Know and What We Should Know[END_REF], for instance, distinguishes between the geographical scope of clusters, the density (dense vs. sparse clusters), breadth of clusters (broad vs. narrow), the depth of clusters (shallow vs. deep clusters), the geographical span of sales (from local to global), the strength of competitive position, the innovative capacity and the ownership structure. Related to these typologies, clusters also vary in terms of their level of activity and self-realisation [START_REF] Enright | Regional Clusters: What We Know and What We Should Know[END_REF].

Another criticism concerns the fact that the cluster literature strongly focuses on how clusters function, but not so much on how they develop over time. One useful solution to these problems is to look at different dimensions of clusters and to use a typology of clusters based on development stages. By doing this we put the cluster in an evolutionary perspective.

3) Cluster Life Cycles

Although we share the concerns of [START_REF] Martin | Deconstructing Clusters: Chaotic Concept or Policy Panacea?[END_REF] and other critical voices, we agree with CHAPMAN et al. (2004, p. 394) who stated that: "Instead of simply 'dropping' clusters as rapidly and uncritically as the term was adopted [START_REF] Martin | Deconstructing Clusters: Chaotic Concept or Policy Panacea?[END_REF], we need to assess and 'unpack' the underlying concept, stepping back from the clusters label and the specifically Porterian assumptions and claims that underpin it. In moving beyond such 'deconstruction' to 'reconstruction', what seems to be required is not a single, overarching theory but the conceptual abstraction of key notions and relations which can then be subjected to detailed empirical scrutiny." We see the cluster life cycle idea and its relation to evolutionary economic geography [START_REF] Martin | Path Dependence and Regional Economic Evolution[END_REF][START_REF] Boschma | The aims and scope of evolutionary economic geography[END_REF][START_REF] Hassink | Relational and evolutionary economic geography: competing or complementary paradigms? Papers in Evolutionary Economic Geography # 09[END_REF] as such an approach towards reconstruction with a strong emphasis on empirical testing. [START_REF] Boschma R | New High-Tech Industries and Windows of Locational Opportunity: the Role of Labour Markets and Knowledge Institutions During the Industrial Era[END_REF] and path dependence and path creation [START_REF] Martin | Path Dependence and Regional Economic Evolution[END_REF], recent conceptual work on cluster life cycles has been done by [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF][START_REF] Press | A Life Cycle for Clusters? The Dynamics of Agglomeration, Change, and Adaption[END_REF][START_REF] Lorenzen | Why Do Clusters Change?[END_REF]. The latter asked three crucial questions, namely: why do clusters arise? why do clusters decline? and why do clusters shift to new economically viable development paths? Our paper can be considered as an empirical contribution to this recently developing theoretical literature.

Looking in detail at the different stages of a cluster life cycle, VAN KLINK and DE LANGEN (2001) exemplary distinguish between the development, expansion, maturation and transition stages of a cluster life cycle. Others, such as [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF], distinguish between emergence, growth, sustainment and decline (for similar classifications, see [START_REF] Gilsing | De Levensloop van Clusters[END_REF][START_REF] Lorenzen | Why Do Clusters Change?[END_REF][START_REF] Enright | Regional Clusters: What We Know and What We Should Know[END_REF].

In addition to distinguishing between different stages, authors also attach specific characteristics to the different stages of a cluster life cycle. VAN KLINK and DE LANGEN (2001) distinguish the following six differing characteristics through the life cycle of a cluster: character of the value chain, strategic relations, cluster dynamics (entrants, exits), co-operative domain, determinant for success and the role of the government (Table 1).

MENZEL and FORNAHL (2010) pay much attention to the changing character of knowledge through the life cycle of a cluster. According to them, the heterogeneity of knowledge in clusters changes through the life cycle of a cluster, as becomes clear in Fig. 1. It is very high in early stages of the life cycle and then decreases strongly through the life cycle. The way the heterogeneity of knowledge in particular is exploited forms the main difference between [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF]. The paradox of a cluster is that specialisation leads to homogeneity of knowledge, which facilitates synergies, whereas a large heterogeneity of knowledge facilitates continuous adjustment to changing external circumstances. Clustered firms show higher growth rates and are more innovative than nonclustered firms during the growth and sustainable stages of the life cycle (Fig. 2) [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF]. Geographic concentration increases in early stages but decreases in mature stages.

(FIGURE 1 ABOUT HERE)

(FIGURE 2 ABOUT HERE) (TABLE 1 ABOUT HERE)
There seems to be most disagreement about the explanation of the emergence of a cluster and about what happens after decline sets in. [START_REF] Krugman | Geography and Trade[END_REF] claims that the emergence of a cluster is often a historical accident, whereas [START_REF] Klepper | The Evolution of Geographic Structures in New Industries[END_REF] stresses that clusters emerge where companies with superior routines in older, related industries are located. Successful spin-offs, the main basis for the emergence of clusters, stem from these superior companies. A renewal or adjustment in the decline stage can take place through a "step back", which is only possible due to the generation of a new heterogeneity of knowledge, which also means a shift in the thematic boundary of the cluster. Increased heterogeneity of knowledge can then lead to a new growth stage (see Fig. 1) [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF]. path dependence can explain changes ex post, strong contingent factors also influence the development of a cluster ( VAN KLINK and DE LANGEN, 2001, p. 452). The actual dynamics of a cluster depend both on external contingent events as well as internal dynamics. According to [START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF], the development of a cluster is not from the left to the right, but a steady oscillation between left and right due to the changing heterogeneity of knowledge in the course of a cluster (Fig. 1). The crucial question is whether the heterogeneity of knowledge is put to use, and that, in turn, depends on the absorptive capacities of companies and organisations in a cluster. Moreover, a cluster does not evenly develop as a whole, but parts of a cluster can be in different stages.

The non-determinist character of clusters can be further elaborated on by comparing industry with cluster life cycles. Clusters follow different growth paths within the same industry (MENZEL and FORNAHL, 2010) (see for instance Silicon Valley vs. Boston elaborated in the study carried out [START_REF] Saxenian | Regional Advantage: Culture and Competition in Silicon Valley and Route 128[END_REF]. Clusters are therefore prone to peculiar local conditions.

To summarise, many authors have recently elaborated on the life cycle of clusters (STORPER and WALKER, 1989;[START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF][START_REF] Gilsing | De Levensloop van Clusters[END_REF][START_REF] Popp | Life Cycles, Contingency, and Agency: Growth, Development, and Change in English Industrial Districts and Clusters[END_REF]; VAN KLINK and DE LANGEN, 2001). They mainly agree on the characteristics of a growing cluster. There is, however, disagreement about how to explain the emergence of clusters and about the development of declining clusters. From these theoretical elaborations, we derived the following research questions, which we will be tackled in the following empirical part of this paper on the life cycle of the shipbuilding cluster in South Korea: sustaining similar levels by the 1990s. These changes created significant impacts on the industrial and social landscape of Korea, including the shipbuilding industry.

F
Korea emerged as a top ranking country in the merchant shipbuilding industry in the recent past [START_REF] Stopford | SMM 2008 Advance Press Conference[END_REF][START_REF] Stopford | Maritime Economics[END_REF][START_REF]Developmental States and the WTO: The Shipbuilding Industry in Korea[END_REF][START_REF] Cho | Changing Global Industry Leadership: The Case of Shipbuilding[END_REF]WOO, 2003;[START_REF]Shipbuilding Disputes: the WTO Panel Rulings and the Elimination of Operating Subsidy from Shipbuilding[END_REF] (Fig. 3).

While the country's traditional shipbuilding industry was scattered along the coastal areas of the whole country, a new path of modern shipbuilding activities was formulated around port cities of the southeastern region: Ulsan, Busan, Changwon, and Geoje, beginning from the early 1970s (Fig. 4). While the cluster was initiated by three major conglomerates, Hyundai was the first initiator and constructed a large shipyard in Ulsan, an industrial city located in the southeastern coastal area. Hyundai eventually became a dominant figure in building large vessels such as crude oil carriers, LNG (Liquefied Natural Gas) carriers, and drilling ships. Although it started with imported modern shipbuilding technologies from overseas [START_REF] Amsden | Asia's Next Giant: South Korea and Late Industrialization[END_REF]

The Stages of Developing Shipbuilding Industry in Korea

1) The Period Prior to the 1970s

Although Korea was active in building ships from the ancient period, its modern shipbuilding is a recent phenomenon. While a major step toward becoming a giant shipbuilder was made in the early 1970s, the roots of the Korean shipbuilding industry can be traced back to the 1880s. As

Japan is located as close as 240 Km away, the first Japanese shipbuilder, called Tanaka Steelship Corporation, established a shipyard in a coastal city, Busan, in the middle of the 1880s [START_REF] Koshipa | A History of Developing Korean Shipbuilding Industry[END_REF]. From this time on, the Korean shipbuilding industry benefited from the arrival and continuous growth of Japanese shipbuilders during the colonial period .

While the Japanese legacy was sustaining to the Korean shipbuilding industry even after its independence, no significant changes took place in the 1940s and the 1950s. Although there were small-scale shipbuilding activities scattered around port cities of the southeastern region, most of these were focused mainly on small and medium-sized ships and boats, and there were very few changes in the structure of the industry. Beginning from the early 1960s, the Korean government initiated a series of ambitious five-year economic plans to promote industrial growth in Korea, including shipbuilding. A drastic change was made in the 1970s, when the Korean government's industrial policies greatly emphasized machinery and heavy industries, including the automobile and shipbuilding industries [START_REF] Amsden | Asia's Next Giant: South Korea and Late Industrialization[END_REF]. From this time, a new path was set in motion in the Korean shipbuilding industry. The path was created by three major Chaebol companies:

Hyundai, Daewoo, and Samsung. The Chaebol group shipbuilding companies began to build large vessels, i.e., oil carriers and LNG ships, in the early stage; however, they greatly diversified their products based on advanced technology at later stages.

2) During the 1970s and 1980s

This new path in the Korean shipbuilding industry was led by the aggressive corporate leaders of Hyundai, Samsung, and Daewoo, and supported by strong governmental policies. While the Korean central government, as a part of its five-year economic plan policies, was geared to promote heavy industries, such as steel-making, machinery and shipbuilding during the 1970s when the international market for shipbuilding was rapidly expanding, some conglomerate leaders attempted to make use of the opportunities provided by the market and the government [START_REF] Hassink | South Korea's Shipbuilding Industry: From a Couple of Cathedrals in the Desert to an Innovative Cluster[END_REF]WOO, 2005;[START_REF]Spatial Concentration and Locational Characteristics of the Shipbuilding Industry in the South-East Region of Korea[END_REF].

For example, the earliest entrant, Hyundai, originally had a plan to build three medium-scale shipbuilding docks (for the scale of 100,000 GT (Gross Tonnage), 60,000 GT and 35,000 GT, respectively), in September 1970, but the company drastically changed its plan to construct super-large shipbuilding docks instead [START_REF] Koshipa | A History of Developing Korean Shipbuilding Industry[END_REF]. This was because the Korean government was strongly encouraging shipbuilders to go for large vessels to take advantage of the rapidly expanding international market. Eventually, Hyundai, whose owner was known for his aggressive business style, built shipbuilding docks with a capacity for ships as big as 500,000 Geoje, a traditional fishing town in the south was growing into an industrial city with Samsung and Daewoo. Among these shipbuilders, Hyundai was the leading power as it was able to make a deal with MetroStar, a Greek company, even during the period of building its shipyard. In this of Korean Shipbuilders, to provide the industry with various information related to domestic and international shipbuilding (see Table 2).

The Korean shipbuilding industry grew by 30% every year between 1976and 1985[START_REF] Koshipa | A History of Developing Korean Shipbuilding Industry[END_REF]. The employment effect was also significant as the number of employees in the industry tripled in the same period. During the late 1970s and the 1980s, however, the industry suffered from the Oil Shocks. Aggressive investment in the previous decade resulted in a significant burden on the industry. During the early 1980s, many international shipbuilders suffered greatly from downsizing international markets for large vessels. The problem was exacerbated by over investment in the previous years, making some production facilities and equipment redundant.

Korean shipbuilders suffered from the same problem. However, the three major Korean shipbuilding companies benefited from the growing international shipbuilding market in the mid- (TABLE 2 ABOUT HERE)

3) The Period since 1997

The growing shipbuilding industry in Korea encountered a major obstacle in the late 1990s.

The whole Korean economy was seriously affected by the Asian economic crisis in 1997, and the shipbuilding cluster was not an exception. While the Crisis forced shipbuilding conglomerates go through a process of critical changes, one of the three shipbuilders, Daewoo, which was one of the Daewoo Chaebol group companies, separated from the group and became independent. The Daewoo group as a whole, in fact, was broken into parts as the Chaebol was financially unsound with high debt ratio, as much as 526% (MINISTRY OF FINANCE AND ECONOMY, 1999, p. 144). Daewoo shipbuilding was allowed to be independent and survive the restructuring process. It was successful in overcoming the Crisis as the company was able to creep out from under the debt problem, recover a sound financial structure and demonstrate its ability to manage a large number of production orders from overseas shipping companies. In this way, the Crisis made Daewoo even more competitive (see Daewoo's performance in Table 2).

The restructuring process in the late 1990s contributed to making the Korean shipbuilding cluster more coherent by forcing less competitive companies out of business and by creating new and more competitive shipbuilders, mainly at the medium scale, often led by innovative entrepreneurs.

The Korean Shipbuilding Cluster

The Korean shipbuilding industry is heavily concentrated in the southeastern region of Korea and plays a very important role in the Korean economy. The industry developed from a couple of cathedrals in the desert into an innovative cluster with some Porterian characteristics [START_REF] Hassink | South Korea's Shipbuilding Industry: From a Couple of Cathedrals in the Desert to an Innovative Cluster[END_REF]. The industry as a whole provides nearly 120 thousand jobs, contributes 5% of the country's GDP, and constitutes 7.5% of overseas sales [START_REF] Koshipa | Shipbuilding Korea 2008[END_REF], where the shipbuilding industrial cluster plays a key role. The major cluster established in the southeastern region is composed of four major city-regions, centered on Busan, Ulsan, Changwon, and Geoje (Tables 3,4, Fig. 4).

(TABLE 3 ABOUT HERE)

Hyundai, Daewoo, and Samsung, all of which are located in the southeastern cluster area, have established strong linkages with their own sub-contractors, but loosely dedicated subcontractors also provide products and services independently to more than one large company.

While there are independent parts and materials and service providers (see [START_REF] Chang S | Technological Cooperation for Sustaining the First Rank in Shipbuilding in the World[END_REF][START_REF]Sustaining and Strengthening of the Competitiveness of Kyeongnam's Shipbuilding Industry[END_REF], these small companies are spread across three provincial level administrative The Korean shipbuilding cluster, however, is not exactly a complete cluster. Rather, it operates strong extra-cluster linkages. In fact, a lot of labor and materials are mobilized from outside: steel plates, a major material input to the cluster, is supplied mainly from a steel giant, POSCO (see [START_REF] Auty | The Impact of Heavy-industry Growth Poles on South Korean Spatial Structure[END_REF][START_REF]State, Steel and Strength: Structural Competitiveness and Development in South Korea[END_REF], located in the city of Pohang, while a considerable portion of engineering personnel and scientists are recruited from other regions, such as Seoul and Daejeon, where many of high-ranking universities are located. [START_REF] Martin | Path Dependence and Regional Economic Evolution[END_REF]. Based on the previous historical accounts of the Korean shipbuilding cluster, the following sub-sections will further illustrate the nature of the cluster by commenting on the themes of the cluster life cycle, such as genesis, development and change.

1) The Genesis

In addition to traditional shipbuilding technology, which was focused mainly on small and wooden boats without mechanical power, the Japanese introduced new shipbuilding technology to Korea during the colonial period, i.e., 1910-1945. The new technology made steel ships and medium scale ships with power engines. Even if such technology did not directly contribute to the modern shipbuilding industry in Korea, it helped the growth of the industry. The existing shipbuilding activities prior to the 1970s were a large foundation on which the current shipbuilding cluster could be grown, as they supplied parts and materials to the modern sector. Therefore, it can be said that the Korean shipbuilding cluster was not created from a vacuum; rather, it grew from the base of traditional shipbuilding, modernized by the Japanese influence especially after 1910.

Considering the Korean shipbuilding case, it is accurate to say that the new path was set by 2) The Stages of Development and Change VAN KLINK and DE LANGEN (2001) identified six criteria to examine the stages of cluster lifecycle: character of the value chain, strategic relation, cluster dynamics, cooperative domain, determinant for success and the role of government. In general, the Korean shipbuilding cluster seems to be moving from the 'developmental stage' to the 'expansion stage,' even if the details of its characteristics do not exactly match with the ones identified by VAN KLINK and DE LANGEN (2001). In terms of value chain, the Korean shipbuilding cluster is composed of three major categories of firms: large, medium, and small. The cluster hosts three very large firms: Samsung, Daewoo and Hyundai, while four medium-sized firms, such as STX and Daesan make the second tier of the hierarchical structure (see WTO (GLEN, 2006). These strategic relations are often maintained through business associations and professional meetings (Interview with Chong-Hyub Han, KOSHIPA, Dec 12, 2009). VAN KLINK and DE LANGEN (2001) In fact, the new cluster in the southwest can be said to be simply an extension of the existing one in the southeast. The new cluster's survival as a complete and independent cluster is in question The scope of activities of the shipbuilding cluster has also greatly expanded. Prior to the 1970s, Korean shipbuilding activities were concentrated on making wooden ships and fishing boats;

since then, product mix has been greatly expanded to produce many kinds of ships such as VLCCs, military ships, FPSOs and drilling ships (Interview with Jong-Soo Seo, Samsung

Industries, May 6, 2010 and Gyu-Bae Kim, Hyundai Heavy Industries, May 17, 2010). In regards to technology, the Korean shipbuilding cluster started with imported technology mainly from Japan and European countries prior to the 2000s and has been successful in internalizing this imported technology to advance its shipbuilding practice to compete at the international level. This change was systematic. In the early stage, they purchased shipbuilding technology from overseas through various means (see HASSINK and SHIN, 2005, p. 149-151). But they quickly internalized, advanced and eventually used the technology to expand production networks to the southwest and overseas (Interview with Jong-Soo Seo, Samsung Industries, May 6, 2010.).

Since the Asian crisis in 1997, major Korean shipbuilders have aggressively attempted to produce higher value-added ships, requiring advanced technology, and cruise ships, moving away from low cost, labor-intensive ships such as oil carriers and bulk carriers. To build and expand R&D activities within their own companies, large shipbuilders of the cluster aggressively invested money to acquire higher levels of shipbuilding technology, learned from foreign nationals, and purchased licenses from overseas. This was necessary as, after the crisis, cheap labor became increasingly difficult to find. In terms of determinant for success (see Table 1), the Korean shipbuilding cluster is viewed to be at the 'transition' stage, because it presents valuable new local know-how and organizing capacity from within the same cluster. For example, Hyundai Samho has developed a 'drydock' system, allowing manufacture of large vessels on land, rather than in the water, without using a traditional dock. This is special because conventional large ships could not be made without using a dock. Therefore, huge docks were necessary for a shipbuilder to make large vessels.

Hyundai Heavy Industries of Ulsan, for example, constructed two major docks since its initial stage in the early 1970s, one of which is as long as 300 M. The company also has expanded the scope of its work to build military ships. Beginning in 2003, Hyundai completed four major military ships, including submarines, battle ships, and destroyers, ranging from 3,000-6,000 tons.

Samsung has also developed an innovative assembling technique, called 'MegaBlock', which allows the building of large ships in blocks on land (Interview with Jong-Soo Seo, Samsung Heavy Industries, May 6, 2010). The large blocks of a very large ship ranging to more than 300 M long, are made on land; the blocks, each of which commonly weighs up to 3,000 tons, are transported to the water; they are assembled on the water to make a ship; and the ship eventually is launched into the water. While a ship was initially divided into 30 pieces to make the blocks lighter, Samsung has developed a technique that allows them to make 10 pieces of blocks for a large ship, which commonly weigh as much as 165,000 TEU (Twenty-foot Equivalent Tonnage). This is possible by introducing a huge crane that can move a single ship block as heavy as 1,200 tons. In January 2006, Samsung was able to build an oil-carrier for MetroStar that was 274 M long, 50 M wide, and weighed 26,000 Tons. In this way, Samsung is able to build many large ships at the same time since a traditional dock system is not required.

3) Linkages as a Factor of Change

As stated in the theoretical Section 2, the geographic concentration of firms in a cluster increases in the early stages but decreases in the mature stages of the cluster's life cycle. The increasing role of extra-regional and international linkages is also mentioned in literature on local buzz and global pipelines [START_REF] Bathelt | Clusters and knowledge: local buzz, global pipelines and the process of knowledge creation[END_REF].

Local dynamic relationships are also found among small-and-medium companies supplying inputs to the shipbuilding companies of the cluster. While some of these are solely dedicated Among the former, a few large shipbuilders, with local government's assistance, have developed industrial parks close to the shipbuilders to provide cheap land with easy access.

The industrial park of Shinhyun-Eup is an example developed by large shipbuilders such as Daewoo (see WOO, 2005). Some local governments have also developed industrial parks to promote the shipbuilding industry by providing less-dedicated parts suppliers with cheap land.

Gyeongnam Province in particular is very active in such activities, as seen in the industrial sites developed in Changwon (see [START_REF]Sustaining and Strengthening of the Competitiveness of Kyeongnam's Shipbuilding Industry[END_REF].

While a steel city, Pohang, provides steel plates to the shipbuilding cluster, Changwon, specialized in machinery, supplies engines and other mechanical engineering technology.

Engineers needed for this cluster are provided mainly by four major universities: Seoul National University, Busan National University, Korean Marine University and Bukyung National University. While many of these are located in Busan, Seoul National University is located a five hours drive away from the cluster area. R&D activities contributing to the cluster are also well scattered, forming extra-cluster linkages. While R&D related to design and production are concentrated on the production sites, such as Geoje and Ulsan, some of the R&D occurs from the governmental research laboratories of the Daedeok Science Park, located in the city of Daejeon, 300 Km away to the north (see [START_REF] Shin | An alternative approach to developing science parks: A case study from Korea[END_REF]. Other R&D activities are located in the Seoul region, another 150 Km away further to the north [START_REF] Hassink | South Korea's Shipbuilding Industry: From a Couple of Cathedrals in the Desert to an Innovative Cluster[END_REF][START_REF]Sustaining and Strengthening of the Competitiveness of Kyeongnam's Shipbuilding Industry[END_REF]. Geoje hosts two major shipbuilders: Daewoo and Samsung, each of which has employed more than 10,000 workers on the sites. The industrial city also contains some industrial parks that host subcontractors of the big players (see [START_REF]Sustaining and Strengthening of the Competitiveness of Kyeongnam's Shipbuilding Industry[END_REF]WOO, 2005). These industrial parks, in fact, provide the physical conditions to stimulate easy flow of materials and services between large shipbuilders and their sub-contractors. The extra-local linkages of the shipbuilding cluster are not limited to Korea, but extend to other countries. The international linkages are presented in the flow of final products, materials, parts, technology and labor. Korean shipbuilding activities strongly depend upon international markets, as domestic demand is highly limited. Korean shipbuilders also maintain international linkages to acquire parts and materials for two reasons: high quality and low costs. While Korean shipbuilders have been continuously attempting to cultivate higher value added products, some high quality parts and materials were unavailable locally.

Therefore, many of the new parts and materials needed for newer models have been imported from overseas. On the other hand, the Korean shipbuilders have been utilizing cheap foreign materials and parts to reduce production costs. Since labor costs in Korea have been increasing since the 1960s and large vessels are now made in block production systems, some parts of large ships could be mobilized from countries with lower labor costs -China, for example. In addition, the Korean shipbuilding industry also expanded production activities to overseas. Hyundai, for example, established shipyards in Vietnam (Hyundai Vinashin Shipyard)

and China (Hyundai Qindao Shipyard), while Samsung established a shipyard in Brazil (see Table 5, and also HONG, 2008, p. 32). Daewoo and Hanjin also moved in to Romania as early as 1997 and the Philippines respectively, while STX Group recently bought a major Norwegian shipyard, Aker Yards, and renamed it STX Europe. In this way, parts and materials not only for higher-end products but also for medium value-added ships tend to create extra-cluster linkages with the Korean shipbuilding cluster.

(

Conclusions

On the basis of the qualitative empirical analysis of the cluster life cycle, we can derive several conclusions related to the research questions posed at the end of Section 2. First, different characteristics (Table 1) of the Korean shipbuilding cluster can be seen as existing at different stages of the life cycle. While the value chain and dynamics of the Korean cluster are at the 'maturation' stage, the determinant for success and the government's role are in the 'transition' stage, leaving strategic relations at the 'expansion' stage. In a cluster as a highly complex system consisting of large enterprises with different strategies, small and medium-sized suppliers and different political actors at national and regional level, it is highly unlikely that all characteristics are positioned in the same stage of development. diversifying the heterogeneity of knowledge in the cluster. Finally, concerning the geographic concentration of firms through the life cycle of the cluster, there has been a strong tendency of geographic concentration of the cluster in the past, but recently the cluster disperses and even internationalises. Extra-local linkages destined for other parts of Korea have been developed to simply expand the scale of production, while new international production linkages with an advanced shipbuilding country, such as Norway, have also been developed to take advantage of accumulated technology there. It is interesting to note that the Korean shipbuilding cluster continues to expand its linkages with other countries to acquire advanced skills and know-how, not simply cheap labour and parts.

Overall, we can also conclude that in a relatively small country such as South Korea with an industry that is relatively spatially concentrated, such as shipbuilding, industry and cluster life cycle do not differ that much from each other. The emergence of the cluster was neither an

  Cluster life cycles: the case of the shipbuilding industry cluster in South Korea

  emergence and development of industrial clusters in South Korea. It analyzes the life cycle of the shipbuilding industry cluster over time and explains the different stages of development. Finally, it focuses on the factors affecting the life cycle of the cluster.

  interviews with managers and engineers of major Korean shipbuilders, such as Hyundai, Samsung, and Daewoo.

  bases, skills, technologies and governance agencies.

  1980s and were able to grow rapidly. Samsung, for example, expanded two major docks in 1979 and 1983, respectively. Despite the over investment of the 1970s, which led to a major restructuring process in the following decade, such aggressive investment is believed to have helped Korea to grow as a giant shipbuilder in the present era. The low value of the Korean currency and low labor costs that made the Korean shipbuilders more competitive, compared to Japan in particular, were temporary conditions that existed only in the middle of the decade.Nevertheless, this circumstance greatly helped the Korean shipbuilders to move to the top of the international shipbuilding industry (Interview with Chong-Hyub Han, KOSHIPA, Dec 12,2009.)The decade beginning in the mid-1980s was quite favorable for Korean shipbuilding. The main competitors in Japan were suffering from the expensive Japanese Yen. While the industry was dominated by a few large players, most of the companies were greatly expanding and stabilizing specialization, scale of production, diversity of product mix, and managerial and technological knowledge.

  south, including the Province of Gyeongnam and the metropolitan cities of Ulsan and Busan. This region, which includes Korea's second largest city, Busan, has been a center of petrochemical, machinery, and heavy industries, including refining crude oil, shipbuilding, automobile, and machinery. The whole region, stretching from Busan to Geoje, is home to about 8 million people and continues to play a key role in the modernization of the Korean economy since the colonial period under Japan.

  entrepreneurs' 'mindful deviation' under a specific context, consisting of unique governmental policies and market situations in that specific time and nation. While the Korean government pursued aggressive policies of industrialization during the 1970s and aggressive entrepreneur of Hyundai, Ju-Yung Chung, the founding father of the conglomerate took advantage of the policies and international market environment at that time by heavily investing in the shipbuilding industry. The new path was set not solely by entrepreneurs' mindful deviation, but also with the right context, which was the combination of market circumstance and governmental policies.

  also talk about cluster dynamics. In terms of cluster dynamics, the Korean shipbuilding cluster is also at the stage of 'maturation'. The number of large and medium-size shipbuilders rapidly grew during the 1970s and has steadily grown further during the recent decades. The Korean shipbuilding cluster is diversified in terms of geography, industry, and technology. While the modern shipbuilding industry started in Busan during colonial period and in Ulsan in the early 1970s, the industry expanded to the city-regions of Changwon and Geoje during the 1970s and the 1980s and further extended to the southwest, centered in the city of Mokpo in Jeonnam Province, beginning in the early 2000s. However, this new cluster is mainly focused on production activities, while higher levels of services, technological development and educational activities are supplemented from other areas, such as the southeast and Seoul area (Interview with Jin-Keun Kim, Gyeongnam Development Institute, May 17, 2010 and Hyung-Min Kim, Research Institute of Medium and Small Shipbuilding, May 17, 2010.)

  demand for ship production has drastically shrunk since the 2007 American Subprime Mortgage Crisis.

  market expansion, professionalizing suppliers, and stimulating neue Kombinationen. In the early stages, the national government in Korea designated the shipbuilding industry as a strategic industry. It provided guidelines to stimulate the industry and assisted in the formation of shipbuilding clusters by creating new industrial parks in Ulsan and Geoje. While local governments played very minor roles in the early stages, the roles of local governments in the southeastern and southwestern regions have become much stronger in recent years. The provincial government of Gyeongnam, located in the city of Changwon, for example, has successfully created a multi-million dollar package of central government financial assistance, under the name of 'Changwon Mechanical Engineering Cluster', core elements of which are identical to the shipbuilding industry. Under this program, networks of shipbuilding parts and components suppliers were going to be extended to surrounding areas of core industrial cities, making the cluster more dispersed (WOO, 2005; KIM, 2008). In addition, municipal governments of the southeastern and southwestern regions have also been very active in creating industrial parks to expand and solidify the cluster (Interview with Jin-Keun Kim, Gyeongnam Development Institute, May 17, 2010).

  shipbuilding conglomerate, others are less dedicated to a specific company.

  Future research is needed to elaborate more on this co-evolutionary question. Secondly, and related to the first research question posed at the end of Section 2, clustered firms have become more competitive than non-clustered firms in the middle stages of the cluster life cycle. Thirdly, as is stated in the conceptual literature, specialized in the past, but are more recently re-orientating and diversifying into high-end market segments. Fourthly, the development of the number of entrants and exits through the course of the life cycle does not mirror the typical development stated in the conceptual literature (from many entrants and no exits to a few entrants and a few exits to hardly any entrants and many exits). Partly due to the specific characteristics of the South Korean shipbuilding industry with a few, but relatively large firms from the start, both the number of entrants and exits has been very low from the beginning. Fifthly, concerning the role of the government through the course of the life cycle, the Korean state has done much more than providing information on local know-how and market expansion in early stages, as indicated in the conceptual literature; it has invested heavily in these stages, as shipbuilding was a targeted industry. Sixthly, the heterogeneity of knowledge in the cluster decreased during the 1980s and 1990s, but more recently the Korean shipbuilding industry has been successfully

  One way to solve this problem is to look at different dimensions of clusters.

	operationalization.
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	6

has coined a fuzzy concept, which is characterised by a lack of conceptual clarity, poor rigour in the presentation of evidence, unclear methodology and difficulties in

  The company was successful in building as many as five Very Large Crude Oil Carriers (VLCCs), all for export overseas. In addition, the company expanded dock capacity further to accommodate building a huge ship as big as 700,000 GT. In June 1974, Hyundai completed a

	GT. large dock of 383 M in length, 80 M in width and 12.7 M in height. This shipyard was also
	equipped with 1,050 M of painting walls, two Goliath cranes that could handle loads as heavy as
	450 Tons, and other modern shipbuilding machines and equipment, such as large N/C
	F (Numerical Control) cutters. In addition, Hyundai established a new company in 1975 that o r specialized in repairing large ships, called Hyundai Mipo Shipbuilding Company.
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	14

Samsung took part in the race by buying-out one of the existing shipbuilders, called Woojin, located in Geoje, Gyeongnam Province, and completing a major shipyard in 1977

[START_REF] Hassink | South Korea's Shipbuilding Industry: From a Couple of Cathedrals in the Desert to an Innovative Cluster[END_REF][START_REF]Spatial Concentration and Locational Characteristics of the Shipbuilding Industry in the South-East Region of Korea[END_REF]

. Another existing company, Korean Shipbuilding Corporation also constructed a major shipyard in Geoje in 1978 but it was merged into Daewoo.

  an employee overtook its managerial authority and ownership to create a comprehensive shipbuilder. The STX group as a whole has now grown to employ 51,500 people and operate many subsidiary companies, including shipbuilding, engines, heavy industries, energy and construction at various locations. In 2006, it made a major step toward being able to make cruise ships by acquiring a Norwegian cruise ship maker called Aker Yards (Interview with Jin-Keun Kim, Gyeongnam Development Institute, May 17, 2010).

	to survive,
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	17

STX, for example, was created by merging several less competitive, mediumscale shipbuilders, such as Daehan. While Daehan, a medium scale engine-maker, was unable

Table 3

 3 Interview with Gyu-Bae Kim, Hyundai Heavy Industries,May 17, 2010 and Jong- and transition. While LORENZEN (2005) raises questions about the reasons for the emergence of and changes in industrial clusters,[START_REF] Garud | Path Creation as a Process of Mindful Deviation[END_REF] argue that a new path is not created by "historical accident"; rather, it is created by entrepreneurs' mindful deviation (see also

	Soo Seo, Samsung Heavy Industries, May 6, 2010.)
	(TABLE 4 ABOUT HERE)
	6. Cluster Life Cycle
	As is pointed out in the theoretical part of this paper, MENZEL and FORNAHL (2010) and VAN

indicates that 76.7 % of the Korean shipbuilding firms and 88.4% of the workers are located in two major provincial level areas: Ulsan and Gyeongnam (Data for 2007, from KOREAN

NATIONAL STATISTICAL OFFICE, 2008)

. Shipbuilding activities clustered in the southeastern region are mainly characterized by production activities, while the Seoul and Daejeon regions, outside the cluster, provide higher quality resources, such as engineers, scientists and R&D services (

Table 2

 2 ). A drilling ship that Samsung focuses on is used in drilling holes under the sea to explore natural resources. It requires a structure that can sustain high speed winds and heavy waves, which can be as high as 16 M. Though Korean shipbuilders received overseas orders of 43 drilling ships prior to 2008, Samsung acquired 35 of them (see SAMSUNGSHIPBUILDING INDUSTRIES, 2009b). One drilling ship made by Samsung in 2008 is as tall as 100 M on the surface and can create a hole as deep as 10 Km under the sea floor. One drilling ship costs 400 million dollars, which is four times of the price of a common crude oil carrier. In terms of the value chain, therefore, the Korean shipbuilding cluster is clearly in the 'maturation' stage (Interview with Jong-Soo Seo, Samsung Heavy Industries, May 6, 2010). sign of pressure to reconfigure. Other relationships that need to be mentioned are the linkages among large corporations. Large shipbuilding companies share common interests among themselves, even if they compete with each other (Interview with Chong-Hyub Han, KOSHIPA, Dec 12, 2009.) They cooperate with each other for certain purposes in opportunistic ways, as in the fight against EU's legal accusation at

	). Prior to the 1990s, Korean

.

Samsung, for example, now focuses on building special ships, such as drilling ships, LNG carriers, and cruise ships, although it started its business with oil carriers (see SAMSUNG HEAVY In terms of strategic relations, it seems that the Korean shipbuilding cluster is at the 'expansion' stage but strategic relations have not yet fully matured. However, there are strong inter-firm relationships horizontally and vertically. Most of the large corporations in Korea, including shipbuilders, maintain subcontractors (see

WOO, 2005;[START_REF]Sustaining and Strengthening of the Competitiveness of Kyeongnam's Shipbuilding Industry[END_REF]

. The linkages between such subcontractors and their mother companies are very strong; however, these vertical relationships are exclusive to other conglomerates (Interview with Jin-Keun Kim, Gyeongnam Development Institute, May 17, 2010.) While there are very few linkages across Chaebol groups, the linkages within Chaebol groups and with their own sub-contractors are very strong.

Company, which is another subsidiary of the Hyundai group (Interview with Gyu-Bae Kim, Hyundai Heavy Industries, May 17, 2010.) These relationships have been well established but

TABLE 5

 5 At the present time, the firms contained in the cluster have not formed dynamic R&D networks; rather they interact only in a vertical way. Horizontal interactions are not well developed. Large shipbuilders, such as Samsung and Hyundai, do not actively interact with each other but compete. Therefore, it can be said that local buzz is limited to only certain levels, such as within conglomerate among the group formed by a large shipbuilding company such as Samsung and Hyundai, or certain local industrial parks. However, they exchange information and share common interests to take advantage of outside assistance, such as those from the government, universities, and public research organizations. They also cooperate to work for, or against, outside supporters, or competitors at home and overseas.

	ABOUT HERE)

Table 2 .

 2 nor played related industries located in the region play a decisive role. It was, instead, much more due to a deliberate central government strategy. As stated by[START_REF] Menzel M.-P | Cluster life cycles-dimensions and rationales of cluster evolution[END_REF] and[START_REF] Martin | Path Dependence and Regional Economic Evolution[END_REF], our case study confirms that a nondeterministic view on the life cycle of clusters is necessary. The exact course of a cluster life cycle and its characteristics vary from case to case and is therefore an empirical question. Amount of Shipbuilding Tonnage by Selected Korean Major Companies (Unit : GT) The number in ( ) in 2008 column means the number of ships built.

	historical accident, Page 31 of 48	Regional Studies
	F o r
	P
	e
	e r
		R
		e
		v i e
		w
		O n l
		y
		31

http://mc.manuscriptcentral.com/cres Email: regional.studies@fm.ru.nl WOO Y.-S. (2005) A Study on the Restructuring of Shipbuilding Industry and the Structure of Community Cooperation: The Case of Sinhyeon-eup in Geoje, Journal of the Korean Geographical Society 40 (4), 19-40 (in Korean). 40 Fig. 1. Interaction between size and heterogeneity of clusters over the life cycle Source: MENZEL and FORNAHL (2010, p. 218).

Fig. 2. Clustered and Non-clustered Companies during the Industry Life Cycle Source: MENZEL and FORNAHL (2010, p. 211). 43 Fig. 4. Major Locations of Shipbuilding Activities in Korea Source: own research, based on Koshipa, 2008.

Table 3 .

 3 Korea's Shipbuilding Activities by Regions Note: The 1997 data for Ulsan are 'Not Available' because Ulsan was a part of Gyeongnam Province prior to 1997. Census of the Manufacturing Establishments, Published by the Korean National Statistical Office, available from KOSIS (KOREAN STATISTICAL INFORMATION SYSTEMS, http://www.kosis.nso.go.kr)

	Regions			No of Establishments				No of Employees
	Regions		1994	1997	2000	2004	2007	1994	1997	2000	2004	2007
	Busan (%)		21.2	23.3	18.4	15.7	16.0	9.4	8.6	6.2	6.8	5.8
	Gyeongnam (%)	34.2	32.7	35.3	43.0	48.7	82.0	37.4	39.1	43.2	49.3
	Ulsan (%)		N.A.	4.2	10.6	14.3	12.0	N.A.	40.1	42.7	38.8	33.2
	Three Area Total
	(Busan, Gyeognam and	55.3	60.2	64.3	73.0	76.7	91.4	86.1	88.0	88.8	88.4
	Ulsan, %)
	Jeonnam (%)		13.6	14.3	12.0	14.7	12.1	2.9	10.1	7.7	8.7	8.7
	Other areas (%)	31.1	25.5	23.8	12.3	11.2	5.7	3.8	4.3	2.5	2.9
	Korea Total	Actual Number	1,101 1,205 1,301	1,100	1,628 64,979	77,892	81,502	94,197	121,534
		Percent (%)	100.0 100.0 100.0	100.0	100.0	100.0	100.0	100.0	100.0	100.0

Source:

Table 4 .

 4 Major Locations of Population Size and Shipbuilding Activities Numbers in brackets mean the share of the particular region. Source: Population statistics of the cities and provinces were obtained from a statistical book of Korean Residents' Registration, representing the data for 2007, while industry statistics from the Report on the Census of the Manufacturing Establishments (published by the KOREAN NATIONAL STATISTICAL OFFICE). Both are available from KOSIS (Korean Statistical Information System, www.kosis.nso.go.kr).

	Regions	Population (000)	No of Shipbuilding Companies	No of Shipbuilding Employees
	Seoul
	Busan Daejeon Pohang Ulsan Gyeongnam Changwon	10,201 3,564 1,461 508 1,112 3,225	260(16.0) 196 (12.0) 793 (48.7)	7.0 (5.8) 40.4 (33.2) 60.9 (49.3)
	Geoje	504
	Jeonnam	217 1,919	197 (12.1)	10.6 (8.7)
	Mokpo	246 508
	Dongkwangyang
	Korea Total	49,540	1628 (100.0)	1215 (100.0)

Note:

Table 5 .

 5 Overseas Investment of Korean Shipbuilders

	Companies	Overseas Investment
	Hyundai Heavy Industries (HHI)	Hyundai Vinashin Shipyard (HVS), Vietnam
		Hyundai Qindao Shipyard, China
	Samsung Heavy Industries (SHI)	EAS Shipyard, Brazilian
	Daewoo Shipbuilding & Marine	Daewoo Mangalia Heavy Industries Co., Ltd.
	Engineering (DSME)	(DMHI), Romania
	STX Group	STX Europe, Norway (Aker Yards)
		The Dalian complex, China
	Hanjin Heavy Industries &	Philippine Subic Bay Metropolitan Authority
	Construction (Hanjin)
	Source: HONG (2008, p. 33)

Page 48 of 48 http://mc.manuscriptcentral.com/cres Email: regional.studies@fm.ru.nl Regional Studies

http://mc.manuscriptcentral.com/cres Email: regional.studies@fm.ru.nlRegional Studies


Adrien Couëtoux

Mario Milone

Olivier Teytaud

Consistent Belief State Estimation, with Application to Mines

Keywords: Partially Observable Markov Decision Processes, Belief State Estimation, Monte-Carlo Tree Search, Upper Confidence Trees, Mines game

Estimating the belief state is the main issue in games with Partial Observation. It is commonly done by heuristic methods, with no mathematical guarantee. We here focus on mathematically consistent belief state estimation methods, in the case of one-player games. We clearly separate the search algorithm (which might be e.g. alpha-beta or Monte-Carlo Tree Search) and the belief state estimation. We basically propose rejection methods and simple Monte-Carlo Markov Chain methods, with a time budget proportional to the time spent by the search algorithm on the situation at which the belief state is to be estimated; this is conveniently approximated by the number of simulations in the current node. While the approach is intended to be generic, we perform experiments on the wellknown Mines game, available on most Windows and Linux distributions. Interestingly, it detects non-trivial facts, e.g. the fact that the probability of winning the game is not the same for different moves, even those with the same probability of immediate death. The rejection method, which is slow but has no parameter and which is consistent in a non-asymptotic setting, performed better than the MCMC method in spite of tuning efforts.

I. INTRODUCTION: BELIEF STATE ESTIMATION, FROM MINES TO MATHEMATICS

In Section I-A we present the Mines games, which is convenient as an experimental testbed and for introducing notations. In Section I-B we present the formalism of Markov Decision Processes and Partially Observable Markov Decision Processes. In Section I-C we formalize the problem of belief state estimation.

A. The Mines game

Consider the simple Mines game, which is well known for his free clones on several platforms (e.g. on Linux or Windows). Mines look like a simple game, sometimes equipped with a "hint" system, which helps you for finding a good move. However, this hint system is usually unable to solve more than simple cases, or cheats by using hidden information. Indeed, an exact choice of optimal move is far from being simple.

The rules of the game are as follows. This is a one player game. There are N mines, located randomly on a p × q grid. Mines are not visible. At each move, the player chooses one location in the grid. If there is no mine at this location, then the number of mines in the 8-neighborhood is displayed to the player; otherwise, the game is over. Usually, the score is the time before complete solving (i.e. all non-mines locations are played at least once) -the smaller, the better. No score in case of game over by playing on a mine.

We will here consider as score the number of (unique) moves before the game is over, divided by pq -N (so that 1 means complete solving). Figure 1 shows that the game is not trivial: which move would you play here ? All players know many cases in which a move can be played for free, because it is sure that there is no mine here -and many players know that sometimes, you can not be sure and must play with a non-zero probability of loosing the game. But not many players know that in such cases, sometimes, some locations are more likely than others to be mines. Specific examples, as preliminaries for the discussion on Belief State estimation below, are given in Fig. 2.

Some details on the rules: The Windows version of the game ensures that the first move is not on a mine (the mines are randomly distributed after the first move). Some versions on the game (Gnomine, default version on many Linux distributions) moreover ensure that the number of mines in the 8-neighborhood is 0. In our tests we will only consider the Gnomine version, which makes the game more subtle (the player is less likely to loose very early without having any chance of playing anything subtle).

B. Markov Decision Processes and Partial Observation

Let's now consider Markov Decision Processes (MDP) and Partially Observable MDP (POMDP) from a more abstract point of view. Fig. 2. Left: here, you can deduce that one of the remaining locations is a mine. If you play in the middle location, you have an expected number of (unique) moves before loosing which is, if you play perfectly, 1 (the three outcomes, loosing immediately, or loosing after 1 move, or completely solving the game, are equally likely) -whereas playing the top or bottom unknown location gives an expected number of (unique) moves 4/3 (with probability 1 3 , it's an immediate loss -otherwise, it's a complete solving). Middle: a situation with 50% probability of winning. Right: this situation is difficult to analyze mathematically; our program immediately sees that the top-right location (0,6) is a mine. However, this could easily (and faster) be found by a branch-and-bound optimization. More importantly, it also sees that the location just below [START_REF] Astrom | Optimal control of Markov decision processes with incomplete state estimation[END_REF][START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF] is good; but the real good point is that it can say which locations are more likely to lead to a long-term win than others.

A MDP or POMDP is a directed graph, each edge of each being equipped with a label (action) and a number (probability); the edge between vertex x and vertex y has label m and number r if the probability of switching from state x to state y, when choosing action m, is r. The sum of probabilities in outgoing edges from a state x and equipped with a label m should be 1. By definitions, legal actions in x are labels which can be found on at least one outgoing edge from x. Nodes with no outgoing edge are termed terminal nodes and are equipped with a reward (in some definitions, edges are equipped with a reward, or non-terminal nodes; this will make no difference for this work).

Additionally, in a POMDP, each node x is equipped with an observation o x . A MDP can be seen as a POMDP in which the observation is equal to the state or to a unique state identifier. A (possibly random) sequence of actions a 1 , . . . , a t , . . . defines naturally a random sequence of states x 1 , . . . , x t , . . . and observations o 1 , . . . , o t ; each state and observation is obtained from the previous one using actions and probabilities of transition.

A strategy is a (possibly random) mapping from a sequence of pairs (actions,observations) to actions. In a MDP, observations are uniquely determined as a function of states; so, equivalently, the strategy in a MDP can be defined as a mapping from sequences of pairs (actions,states) to actions (one can note that it is known that the mapping can depend only on the last state without loss of performance in optimal strategies). Basically and informally, a MDP is therefore a POMDP in which the player always knows in which state she is. Given a MDP or POMDP, and a strategy, a random sequence of states and observations is defined, as well as a random reward. The Mines game is a priori a POMDP; mines are not visible. Yet, it can be rephrased as a MDP; we'll see this in the next section.

C. POMDP transformed into MDP: the problem of belief state estimation

A POMDP can be rephrased as a MDP. This can be done as follows. Consider a POMDP P . The MDP M rephrasing P is built as follows:

• The state space of M is the set of sequences of pairs (actions,observations) in P ;

• In M , action a in state ((a 1 , o 1 ), . . . , (a t , o t )) leads to ((a 1 , o 1 ), . . . , (a, o t+1 ))
where o t+1 is the random observation obtained when applying action a in state s where s is the t th state, randomly drawn according to observations (o 1 , . . . , o t ) and actions (a 1 , . . . , a t ). This transformation (originating in [START_REF] Astrom | Optimal control of Markov decision processes with incomplete state estimation[END_REF]) has the advantage of being consistent; a good strategy for M is a good strategy for P -the distribution of rewards is exactly the same. It has the drawback that it leads to a much bigger state space; possibly, M is infinite whenever P is quite small. Moreover, the conditional law above can be very hard to sample -we have to sample the next observation, conditionally to all past observations. The key part of this sampling is the sampling of s t , the state after t -1 actions and observations, conditionally to past actions and observations. This is known as the problem of belief state estimation.

There are several methods for this:

• Simple rejection methods: randomly sample s and reject s unless it is accepted, which happens with probability proportional to its likelihood conditionally to observations. This is very slow, but mathematically consistent. This is summarized in Alg. 1. • Markov-Chain Monte-Carlo (MCMC) [START_REF] Gilks | Markov Chain Monte Carlo in Practice[END_REF] can be used as well; e.g. Metropolis-Hastings, the simplest version of MCMC.

• Randomly extend the observations in order to get a complete state; this is possible in some games, and widely used in e.g. phantom-games or dark chess which are a quite difficult challenge in terms of partial [START_REF] Cazenave | A phantom-go program[END_REF], [START_REF] Cazenave | Golois wins phantom go tournament[END_REF]. This is certainly not consistent in general (i.e. this approximation of M is not equivalent to P ), unless the random choice of the completion in a very specific manner -this is certainly not usual. The purpose of this paper is to propose new consistent methods for belief state estimation. The main claim of the paper is that, even on an a priori simple game like Mines, a rigorous belief state estimation can provide significant improvements on a simple constraint satisfaction problem. By "consistent" methods, we mean methods which, at least at the limit of infinite computational power, lead to perfect estimates; POMDP algorithms based on this algorithm should, as a consequence, be consistent in the sense that they find, at the limit of an infinite computational power, an optimal strategy; this will be formalized in the rest of this paper.

II. NEW METHODS AND THEIR CONSISTENCY

In section II-A we present Monte-Carlo Tree Search (that will be used in our experiments),

A. The rigorous approach: Monte-Carlo Tree Search with rejection

All our experiments are performed using a Monte-Carlo Tree Search (MCTS) implementation, from the Mash project. It uses the Upper Confidence Tree (UCT) formula from [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. MCTS became famous in the game of Go [START_REF] Coulom | Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search[END_REF], [START_REF] Chaslot | Progressive Strategies for Monte-Carlo Tree Search[END_REF], [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], [START_REF] Lee | The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments[END_REF], and UCT is a classical variant of it.

However, we need something for estimating transition probabilities -as our MDP comes from a POMDP setting (see section I-C), this is not straightforward. We have to merge the MCTS algorithm with the rejection method (Alg. 1).

The algorithm is as shown in Alg. 2. As this paper is more devoted to belief state estimation than to UCT, we refer to [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF] for more information on UCT. n(s) is the number of simulations including state s, and n(s, a) is the number of simulations including action a in state s; they are all initialized to 0. Indeed, the implementation that we use (from the Mash project) is slightly more sophisticated and uses progressive widening [START_REF] Coulom | Computing elo ratings of move patterns in the game of go[END_REF], [START_REF] Couetoux | Continuous Upper Confidence Trees[END_REF]; this is not relevant for this paper.

B. Faster methods

As mentioned above, it is somehow natural to use Metropolis-Hastings as an algorithm for sampling the current Algorithm 2 The BSR-UCT algorithm (UCT with Belief State estimation by Rejection method). This is a mathematically consistent algorithm for finite horizon problems (i.e. asymptotically in the computation time it finds an optimal strategy), because UCT is consistent on MDPs with finite horizon and the rejection method is consistent for transforming a POMDP into a MDP.

BSR-UCT algorithm. Input: a POMDP, a state S, a time budget. Output: an action a. while time budget permits do s = S. // starting a simulation while s is not a terminal state and n(s

) > 0 do For action a legal in S Compute Q ⊕ U CT (s, a) Q ⊕ U CT (s, a) = Q U CT (s, a) + log(1+n(s)) 1+n(s,a)
Select action a with maximal Q ⊕ U CT (s, a) Randomly draw complete state z conditionally to observations s, by Alg. 1. Let s ′ be a state reached from z when choosing action a. s ← s ′ end while while Time horizon is not reached do Select action a uniformly in A // random episode Let s ′ be the state reached from s when choosing action a. s = s ′ end while Let R be the reward in s For all visited (s, a) during the above simulation, Update the average reward:

Q U CT (s, a) ← Q U CT (s, a) + 1 n(s,a)+1 [R(s) -Q U CT (s, a)]. Increment n(s, a) Let n(s) = a n(s, a) end while
Return the action a which was simulated most often from S.

state conditionally to past observations; just choose an initial point, and then randomly, at each iteration, choose a mutation of it (by some transition kernel), accepting it or not thanks to the Metropolis-Hastings formula. With a symmetric transition kernel, the algorithm boils down to Alg. 3, i.e. the Metropolis version.

This can be further extended by introducing inheritance: the initial point is not randomly chosen in the domain, but is extracted from the last Metropolis run (we have one Metropolis run for each transition of the MCTS algorithm); while it is probably possible to have more sophisticated algorithms, we just decided to proceed as shown in Alg. 4.

III. EXPERIMENTAL RESULTS

We first performed some sanity check, as discussed in Fig. 2 (right). We then tested the approach above on the Mines games, with the rule that the initial location can not be close to a mine (we ensure, as in the Linux/Gnome implementation, that there's no mine in the 8-neighborhood of the first move). We experimented two board sizes, as follows.

The BSR-UCT version of the algorithm uses the MCTS implementation from the Mash project, based on the UCT formula, with a rejection algorithm for estimating the transition probabilities (see Alg. 2). The fastened version is the one proposed in Alg. 4, with as initial point the final point of the last run of Metropolis' algorithm in the same MCTS run Algorithm 3 The Metropolis algorithm, specialized to our case. The number of trials, for us, is simply the number of simulations in the current state; this means that the computational effort for rigorously estimating the belief state in a node is increasing linearly with the number of simulations in the node.

Choose an initial state x while my number of trials is not exhausted do Randomly draw x ′ , with a distribution p(x) such that the probability of drawing x ′ from x is the same as the probability of drawing x from x ′ . Let r ← likelihood of x ′ divided by likelihood of x. and with transition kernel a random choice of each Mine with probability inverse of the length of x, namely: ∀i ∈ {1, . . . , length(x)},

(
x ′ i = random with probability 1/length(x);

x ′ i = x i otherwise.
The number of Metropolis transitions for estimating the belief state in s is equal to the number of MCTS simulations through the node s. We tested many variants of formulas above with no better results.

A. Small board: 4x4, 6 mines

In 4x4, the Mines game, with the constraint as in Gnomine that the first move has no mine in its neighborhood, is a forced win. The computer essentially reaches perfect play at 6 seconds per move. The algorithm is provably optimal at the limit of a large number of simulations because (i) the consistency of the transformation of the POMDP into a MDP is ensured by the rejection method (ii) UCT is consistent in the limit of a large number of simulations. We provide experimental results in Table I, averaged over 30 runs on a 2.83 GHz core.

B. Big board: 7x7, 11 mines

We provide in Table II experimental results on the bigger size 7 × 7, with 11 mines. Each run is performed only once, we will average results later on; it is on the same 2.83 GHz core as above. This board size with 11 mines is not trivial at all; the good results for long thinking time are not easy to reproduce for humans. Fig. 2 (middle) shows a case in which we have 50% probability of winning.

We compare the two columns of row numbers from Table II in Fig. 3. Basically, the fast version is a trade-off -it provides a lower quality approximation of the belief state (it is only consistent asymptotically in the number of iterations of the Metropolis algorithm), but this approximation is faster, leading to greater numbers of simulations.

IV. CONCLUSIONS

Rigorously estimating the belief state is a big challenge in partial observation problems. This turns out to be important even in simple games like Mines: Fig. I shows that approximate belief state estimation is necessary for exact optimal play.

There are several tools for estimating belief states. First, there are non-asymptotic approaches, which provide a consistent belief state estimation: typically, rejection methods. A second tool is based on asymptotically consistent approaches, like MCMC. We tested MCMC in a simple settings:

• the Metropolis version, with symmetrical transition kernel; • number of iterations of MCMC in state s proportional to the number of visits of state s by MCTS; • inheritance (the initial state of the MCMC is the last sample from the previous MCMC). We tested variants of it with no better results. The slow rejection method was in fact better, as it has no bias in its sampling. It is clear that a specialized approach, using constraint propagation methods for exactly computing the probability of death, is natural for Mines; e.g., counting for each possible next location the number of hidden states compliant with observations and leading to an immediate death, as an exact evaluation of the probability of death. This approach is simple and would be computationally much faster. We point out however that this would not lead to optimal results: for example, in 4x4 mines with 6 mines, the first move, with this approach, can be played anywhere on the domain (all moves have the same probability of death, which is zero!), whereas our approach plays optimally, which means in this small case 4x4 with 6 mines and for the initial move in the central square. That might be surprising for humans, but the best strategy does not only consists in playing a move with minimum probability of immediate death (see Fig. 2), and our algorithm, in spite of drawbacks (it's slow for easy cases), has the strength of, asymptotically, playing optimally these subtle cases. This example (first move in 4x4 board) might look like an artificial counter-example, but Fig. 2 (left) shows that such non-trivial phenomena also occur late in the game. This second example can be sovled manually, but it is certainly hard for humans to solve cases like Fig. 2 (right) without a tool like our algorithm, and constraint programming does not provide a solution to this. Moreover, an important feature of our experiments is that they are all problem-independent; we tested on Mines but probability of immediate death is minimum (for an example of this subtle difference which can be mathematically analyzed exactly, see Fig. 2, left). This paper did not get good results for asymptotic approaches for estimating conditional distributions; this does not mean that such asymptotic approaches can not do a good job, with a different implementation or a different parametrization. Nonetheless, we conclude that the simple rejection method has the advantage of being directly consistent; it will take as much time as necessary for providing a rigorous estimate. We do not conclude that only the rejection method should be considered, but we conclude that comparing with the rejection method or other slow but consistent methods might be a good idea in POMDP. For sure, in many real-world cases, the rejection method is just impossible, making it hard to propose the rigorous way we use here.

We guess that such a rigorous approach might be important in two-player games as well, at least with moderate size; this is a first natural further work. This is far more complicated as in two-player games we have no direct estimate of the likelihood. Moreover, in many games, the state space is huge, making it hard to get rid of heuristics [START_REF] Yen | Modark wins chinese dark chess tournament[END_REF], [START_REF] Cazenave | A phantom-go program[END_REF], [START_REF] Cazenave | Golois wins phantom go tournament[END_REF].

As a second further work, a direct application of this work is also the test on industrial POMDPs; we guess that neglecting the PO part or handling it in a computationally fast but statistically irrelevant way might lead to serious troubles in real world cases.

Fig. 1 .

 1 Fig. 1. A case in which choosing the next move is non-trivial.

Fig. 3 .

 3 Fig. 3. Left: indicator function of improvement (of fastened version compared to the BSE-UCT version), with a moving average of window size 10: we see that the fast version is better for small thinking time, but is outperformed for large thinking time. Right: performance of the fast method minus performance of BSE-UCT: there is improvement only with small thinking time (the moving average with window size 10 is also shown on the plot). The average of the results for thinking time ≤ .256 (first half) and > .256 (second half) are statistically significantly > 0 and < 0 respectively.

  The Metropolis algorithm with initial point, for use inside a Monte-Carlo Tree Search implementation.

	given observations)
	Randomly draw u in [0, 1].
	if u ≤ r then
	x ← x ′
	end if
	end while
	Return x.
	Algorithm 4 (given observations)
	Randomly draw u in [0, 1].
	if u ≤ r then
	x ← x ′
	end if
	end while
	Return x.

Let x be the last state of the last call to this function; if first call, randomly choose x. while I have time left do Randomly draw x ′ , with a distribution p(x) such that the probability of drawing x ′ from x is the same as the probability of drawing x from x ′ . Let r ← likelihood of x ′ divided by likelihood of x.